IncrementalDelaunayTriangulator needs logic to handle frame
dr-jts opened this issue · 0 comments
The IncrementalDelaunayTriangulator is missing some key logic to handle the "frame" correctly.
This bug results in non-convex triangulations being produced for some situations where the convex hull of the input points has a narrow width relative to the frame size. #477 contains examples of this.
The bug also causes failure cases in the ConcaveHull algorithm, which relies on the input triangulation being convex:
PR #931 was an attempt to handle this by increasing the frame size. But it is inherently limited, since no fixed frame size works in all situations.
Required Logic
The logic required is some additional checks when determining whether to flip an edge to maintain the Delaunay condition (at this point in algorithm):
- If the edge is part of a frame triangle, do not flip it (a frame triangle is one of the 3 containing a frame edge)
- If the edge contains a frame vertex AND it creates a concavity in the triangulation boundary, flip it
- If an edge separates the newly inserted point from a frame vertex, do not flip it.
The reason this code was not included in the original development of IncrementalDelaunayTriangulator is that it is not mentioned in most descriptions of the algorithm. The logic is described in this blog post, and also appears in the triangle code (lines 8592-8614).