-
Notifications
You must be signed in to change notification settings - Fork 6
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Infinite loop due to reaching outer half-edge #2
Comments
Debugging further, it seems that the constrained segment that makes things fail is near a region with successive boundary edges, for which Delaunator creates a very thin triangle overlapping one constraint edge. This leads to the intersection call:
visualized there: https://www.geogebra.org/calculator/zayn3rkp This returns as intersecting, and then the opposite edge Note that the constraint is Those very thin triangles don't matter in my code, because I rule out all very thin triangles in the post-processing I do (since I don't need triangles outside my enclosing polygon). But I wonder if you assumed to keep the convex hull by construction (whereas I do not).
|
Thank you for finding this issue.
This should not be an issue. The algorithm doesn't care about the shape that the constrained edges forms, other than that they may not intersect each other. Constraining edges on the hull is also not (supposed to be) a problem.
It is assumed there that Culling triangles on the hull won't work either, since that will break the Constrainautor too. It seems that indeed
The above code solves the issue (on my end), but I am somewhat hesitant to switch over to that implementation as it will incur a dependency on several packages, and has a small but measurable performance impact. |
Thanks for confirming the problem and finding a solution! While the "throw" may not solve my problem directly, having a guard in the code that throws an error upon detecting such invalid case would be good. It's definitely better than an infinite loop when debugging. |
- Added documentation for internal intersect methods, which can be overridden to fix robustness issues. - Added test files from the [Interesting Polygon Archive](https://github.com/LingDong-/interesting-polygon-archive)
…gments, inCircle, and segPointDistSq from the API documentation (which bumps major version). Replaced segPointDistSq with isCollinear, based on robust predicates.
I've been looking for a solution as simple as the one this library is providing to get constrained Delaunay where the constraint is basically a polygon outline.
However, is the current implementation making specific assumptions about the point distribution? e.g. that there are no points inside of the constrained shape?
If not, then there may some missing edge cases. Here is a test case that fails because of an infinite loop:
In the above, the regular integer coordinates are basically an internal grid, and all the irregular ones are points around those.
The constraints are basically on those irregular points that form an outer polygon.
Several edge constraints are part of the convex hull (and thus with outer half-edge
-1
). But the samples you showed at https://observablehq.com/@fil/polygon-triangulation seem to have such conditions (except they seem to never have internal points).Debugging what's happening in the code, it fails at
constrainOne(segP1, segP2)
withsegP1=173
andsegP2=174
, which is the third constraint edge.There, it ends up with
conEdge=1311
, and it enters your posterior loop:with
adj=-1
, and then the rest goes crazy because we're then indexing the typed arrays at negative indices, which gives undefined, and eventuallyNaN
with the rest of the operations ... and we're stuck.I'm not clear exactly what that part of the algorithm is, but I wonder if the loop should not check that
adj
is not-1
.The text was updated successfully, but these errors were encountered: