`Region#delaunay` with `min_b` 1.2 never finishes and grows memory without limit

Abierto
  • ¿Algo no está bien?
#2,537 1 comentario 0 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 1 día

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
3/5
Tiempo estimado
1-2 días
Aptitud para principiantes
67/100
Tipo de issue
Error
Claridad
Bien especificado
Estado de actividad
Activo
Stack tecnológico
cpp
Área
computer-graphics

Línea de trabajo

Start in dbPLCTriangulation.cc and read the refinement loop and its max_iterations parameter; the issue identifies the missing stuck-iteration check. Reproduce with the supplied Region#delaunay examples at min_b 1.2, then verify the loop terminates with a bounded error or result and memory use no longer grows without limit.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

Region#delaunay with min_b from 1.2 never finishes on simple polygons, and its memory grows without limit (about 1.7 GB after 15 s), although its documentation says "The algorithm is stable up to roughly 1.2".

import klayout.db as kdb
L = kdb.Region(kdb.Polygon([kdb.Point(0, 0), kdb.Point(2000, 0), kdb.Point(2000, 300),
                            kdb.Point(300, 300), kdb.Point(300, 2000), kdb.Point(0, 2000)]))
print(L.delaunay(0, 1.15).count())  # 16, in 0.1 s
print(L.delaunay(0, 1.2).count())   # doesn't finish

The same for a triangle with a 30° corner at min_b 1.2 (354 triangles at 1.1), and for kdb.Box(0, 0, 1000, 200) at 1.25 (6 triangles at 1.2).

The refinement loop in dbPLCTriangulation.cc runs while (nloop < parameters.max_iterations) with max_iterations = std::numeric_limits<size_t>::max (), below // TODO: break if iteration gets stuck. A finite default limit, or a stop when an iteration makes no progress, would turn this into an error or a result.

KLayout 0.30.12 (Python module), macOS. The loop is unchanged on master (06b8ff4909).

Lenguaje dominante
C++
Estrellas
1.2k
Forks
305
Merge medio
3 d 2 h
PR fusionados (30 d)
11

Preparar el entorno

Este proyecto no incluye contenedor de desarrollo, Dockerfile ni guía de contribución, así que la configuración corre por tu cuenta: empieza por su README y consulta nuestra guía para la primera contribución para los pasos generales.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de KLayout/klayout

Todos los issues de KLayout/klayout

Issues similares

Más issues de C++

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.