This adds logic to IncrementalDelaunayTriangulator to ensure that the triangulation boundary is always convex (as per specification). This is required because the "frame" created to contain the triangulation construction is not infinitely distant from the input points. This has been causing robustness failures in cases where a site lies very close to the convex hull of the input.
The logic required is additional checks when determining whether to flip an edge to maintain the Delaunay condition :
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).
This is a more robust solution than the frame size increase in #931.
This adds logic to
IncrementalDelaunayTriangulatorto ensure that the triangulation boundary is always convex (as per specification). This is required because the "frame" created to contain the triangulation construction is not infinitely distant from the input points. This has been causing robustness failures in cases where a site lies very close to the convex hull of the input.The logic required is additional checks when determining whether to flip an edge to maintain the Delaunay condition :
The reason this code was not included in the original development of
IncrementalDelaunayTriangulatoris 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).This is a more robust solution than the frame size increase in #931.
Fixes #1002. Fixes #477.
Also fixes various issues reported for ConcaveHull ( https://github.com/libgeos/geos/issues/719, https://github.com/libgeos/geos/issues/946)