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

Đang mở
  • Có gì không ổn?
#2,537 1 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 1 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
3/5
Thời gian dự kiến
1-2 ngày
Mức phù hợp với người mới
67/100
Loại issue
Lỗi
Độ rõ ràng
Đặc tả rõ ràng
Mức độ hoạt động
Sôi nổi
Công nghệ
cpp
Lĩnh vực
computer-graphics

Hướng nghiên cứu

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.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

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

Ngôn ngữ chính
C++
Star
1.2k
Fork
305
Merge trung bình
3 ngày 2 giờ
Pull request đã merge (30 ngày)
11

Chuẩn bị môi trường

Dự án này không cung cấp dev container, Dockerfile hay hướng dẫn đóng góp, nên bạn cần tự thiết lập môi trường: hãy bắt đầu từ README và xem hướng dẫn đóng góp lần đầu của chúng tôi để biết các bước chung.

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của KLayout/klayout

Tất cả issue của KLayout/klayout

Issue tương tự

Thêm issue về C++

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.