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

Open
  • Is something wrong?
#2,537 1 comment 0 reactions 0 assignees View on GitHub

Maintainers usually reply within 1 day

Nobody has claimed this yet.

Assessment

Difficulty
3/5
Estimated time
1-2 days
Newbie friendliness
67/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Active
Tech stack
cpp
Domain
computer-graphics

Research direction

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.

Written by the indexing model from the issue text.

Description

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

Dominant language
C++
Stars
1.2k
Forks
305
Avg merge
3d 2h
Merged PRs (30d)
11

Getting set up

This project ships no dev container, Dockerfile or contributing guide, so setting up is up to you: start from its README, and see our first-contribution guide for the general steps.

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from KLayout/klayout

All issues in KLayout/klayout

Similar issues

More C++ issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.