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

Aperta
  • Qualcosa non va?
#2,537 1 commento 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
3/5
Tempo stimato
1-2 giorni
Idoneità per principianti
67/100
Tipo di issue
Bug
Chiarezza
Specificata chiaramente
Stato di attività
Attiva
Stack tecnologico
cpp
Ambito
computer-graphics

Direzione di ricerca

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.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

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).

Lingua principale
C++
Stelle
1.2k
Fork
305
Merge medio
3g 2h
PR unite (30g)
11

Preparare l'ambiente

Questo progetto non fornisce container di sviluppo, Dockerfile né guida per i contributori, quindi l'ambiente è a tuo carico: parti dal suo README e consulta la nostra guida al primo contributo per i passaggi generali.

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di KLayout/klayout

Tutte le issue di KLayout/klayout

Issue simili

Altre issue su C++

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.