Triangulate fail with useDelaunay=true #1075
Description
The triangulate fails in this example with Clipper2_2.0.1. I also tried the latest clipper2 master. It also fails in master.
const Clipper2Lib::Path64 polygon_vertices = {
{148846174, -8532576, 603510}, {147360289, -8327287, 602403}, {145874404, -8121997, 600407},
{144388521, -7916708, 597649}, {142902639, -7711419, 594286}, {141416758, -7506130, 590414},
{139930879, -7300841, 586196}, {138445000, -7095553, 581741}, {136959121, -6890264, 577183},
{135473242, -6684975, 572672}, {133987362, -6479687, 568306}, {132501482, -6274398, 564248},
{131015601, -6069109, 560606}, {129529718, -5863820, 557515}, {128043835, -5658530, 555124},
{126557950, -5453241, 553536}, {125072064, -5247951, 552906}, {123574419, -5178904, 551926},
{122075337, -5126544, 548716}, {120576260, -5074184, 543579}, {119077190, -5021824, 536748},
{117578126, -4969465, 528607}, {116079069, -4917105, 519403}, {114580016, -4864746, 509450},
{113080966, -4812387, 499089}, {111581917, -4760028, 488553}, {110082866, -4707670, 478217},
{108583813, -4655310, 468330}, {107084755, -4602951, 459208}, {105585691, -4550592, 451191},
{104086620, -4498232, 444507}, {102587542, -4445872, 439546}, {101088459, -4393512, 436548},
{99899974, -4352000, 435773}, {99949948, -2865903, 616698}, {99996073, -1494267, 777064},
{101495224, -1544722, 776713}, {102994375, -1595177, 775718}, {104493526, -1645631, 774178},
{105992675, -1696086, 772160}, {107491825, -1746541, 769771}, {108990974, -1796996, 767094},
{110490122, -1847450, 764209}, {111989270, -1897905, 761223}, {113488418, -1948360, 758203},
{114987567, -1998815, 755250}, {116486715, -2049270, 752454}, {117985864, -2099724, 749890},
{119485014, -2150179, 747665}, {120984164, -2200634, 745847}, {122483315, -2251089, 744541},
{123982466, -2301544, 743833}, {125461110, -2496226, 743416}, {126914912, -2865621, 740880},
{128368708, -3235015, 735929}, {129822497, -3604407, 728937}, {131276276, -3973797, 720249},
{132730048, -4343185, 710158}, {134183812, -4712571, 699074}, {135637571, -5081955, 687237},
{137091327, -5451339, 675069}, {138545083, -5820723, 662846}, {139998841, -6190107, 650917},
{141452605, -6559493, 639659}, {142906374, -6928880, 629326}, {144360152, -7298269, 620348},
{145813939, -7667661, 612965}, {147267734, -8037054, 607587}, {148721535, -8406450, 604531},
{149312960, -8556724, 603862},
};
Clipper2Lib::Paths64 solution;
const Clipper2Lib::TriangulateResult result =
Clipper2Lib::Triangulate({polygon_vertices}, solution, /*useDelaunay=*/true);
CHECK_EQUAL(result, Clipper2Lib::TriangulateResult::fail);
Here is what I got from claude
Root Cause: Duplicate locMinStack push due to collinear vertex at local minimum
The triangulation fails because of a bug in Clipper2's AddPath() method (clipper.triangulation.cpp:1110-1166) when a collinear vertex immediately follows a local minimum.
The chain of events:
1. Vertex 35 (99996073, -1494267) is the polygon's local minimum (bottommost point / largest Y).
2. Vertex 36 (101495224, -1544722) is exactly collinear with vertex 35 and vertex 37:
CrossProductSign(v35, v36, v37) = 0
3. In AddPath's for(;;) loop (line 1110), each iteration starts with locMinStack.push(vPrev). When the collinear check at line 1122 fires for v36, the continue statement restarts the loop without advancing vPrev. This causes v35 to be
pushed to locMinStack twice.
4. In Execute() (lines 911-928), the orientation correction pops all entries and flips each vertex's innerLM flag:
- First pop: v35.innerLM = !true = false
- Second pop: v35.innerLM = !false = true ← flipped back!
5. The double-flip leaves v35.innerLM = true incorrectly. During the main vertex sweep, v35 is treated as an inner local minimum that needs a connecting edge to an active edge below it.
6. CreateInnerLocMinLooseEdge(v35) (line 959) searches for an active edge below v35. Since v35 is the bottommost vertex, no such edge exists → returns nullptr → TriangulateResult::fail.
Fix
The for(;;) loop in AddPath should guard against duplicate pushes. The simplest fix is to move the locMinStack.push(vPrev) call after the collinear skip check, or guard it with a check that vPrev hasn't already been pushed. For example,
restructuring lines 1112-1126 so the collinear skip continue happens before the locMinStack.push.
The patch from claude is
Here's the patch:
--- a/CPP/Clipper2Lib/src/clipper.triangulation.cpp
+++ b/CPP/Clipper2Lib/src/clipper.triangulation.cpp
@@ -1109,16 +1109,16 @@
for (;;)
{
- // vPrev is a locMin here
- locMinStack.push(vPrev);
- // ? update lowermostVertex ...
- if (!lowermostVertex ||
- vPrev->pt.y > lowermostVertex->pt.y ||
- (vPrev->pt.y == lowermostVertex->pt.y &&
- vPrev->pt.x < lowermostVertex->pt.x))
- lowermostVertex = vPrev;
-
iNext = Next(i, len);
+ // skip collinear vertices before pushing to locMinStack,
+ // otherwise a locMin can be pushed multiple times causing
+ // its innerLM flag to be double-flipped during orientation
+ // correction, leading to TriangulateResult::fail.
if (CrossProductSign(vPrev->pt, path[i], path[iNext]) == 0)
{
i = iNext;
@@ -1126,6 +1126,14 @@
}
+ // vPrev is a locMin here
+ locMinStack.push(vPrev);
+ // ? update lowermostVertex ...
+ if (!lowermostVertex ||
+ vPrev->pt.y > lowermostVertex->pt.y ||
+ (vPrev->pt.y == lowermostVertex->pt.y &&
+ vPrev->pt.x < lowermostVertex->pt.x))
+ lowermostVertex = vPrev;
+
// ascend up next bound to LocMax
while (path[i].y <= vPrev->pt.y)
{
The fix moves the locMinStack.push(vPrev) and lowermostVertex update after the collinear skip check. This way, when a collinear vertex triggers continue, the loop restarts at the collinearity check (now at the top) without pushing vPrev
again. The push only happens once, right before the ascending edge-building phase begins.