Triangulation, rare infinite loop #1058
Description
Hi,
I've been fuzz testing the triangulation feature and have encountered an infinite loop within Clipper2Lib::Triangulate. Apologies for the length of the test case - most simpler examples are working perfectly. The infinite loop occurs within Delaunay::Execute, where it repeatedly calls ForceLegal on clipper.triangulation.cpp line 1053.
My test creates random self-intersecting polygons, takes the Union (as per the docs), then triangulates. In the case below, Triangulate does work when triangulating the individual polygon pieces output by Union, but fails when triangulating the entire thing at once.
I'm running a Clipper2 git clone from Jan 19 2026. I'm compiling on
Apple clang version 17.0.0 (clang-1700.0.13.5)
Target: arm64-apple-darwin24.6.0
// C++ test case.
// A polygon with a lot of self-intersection.
Clipper2Lib::Paths64 poly1 = {{
{6251161,332856160}, {840876097,97496650}, {976400933,140787098},
{330832885,702363622}, {524959570,901562500}, {283075095,283198665},
{682169472,407971968}, {341184383,906937707}, {885255988,51653123},
{679161444,348752493}, {110729587,243797389}, {175478881,936371388},
{884834543,92623405}, {830335767,487305557}, {381715781,603651314},
{429388870,750813644}, {183632134,133019917}, {748295100,710325195},
{736200816,526977435}, {265700863,815231128}, {267777137,451565516},
{932290823,419938943}, {881163203,459777725}, {46306602,10129599},
{52939203,969104432}, {15564105,724992816}, {826186121,204403883},
{168323587,84596478}, {330051681,190436576}, {910281595,436345833},
{579089233,926825204}, {409518567,421262563}, {907897616,740612275},
{943299290,731351779}, {220519408,944234682}, {397472466,978974872},
{478544665,67011261}, {492508035,881036163}, {869736187,774199458},
{738244055,744934646}, {744662274,427823310}, {841438346,988766232},
{614037581,326952247}, {1868663,40207860}, {308127932,719137146},
{258010101,520371199}, {418166295,915065961}, {49983486,843699463},
{526874162,817456881}, {41058475,738741192}, {727641385,611946004},
{338496075,630157593}, {691414735,818968108}, {49426629,734590805},
{149386829,315107107}, {537222333,388854339}, {79101039,347162131},
{576707064,71330961}, {712674406,422581668}, {929289005,867002665},
{913051643,149224610}, {65254363,479593145}, {694329570,11130378},
{913734201,50414969}, {654447184,797671163}, {130981529,731710403},
{331099632,659944678}, {619403370,520436929}, {19628661,496649629},
{61993195,185722653}, {714388595,163372694}, {615296901,93286726},
{830312146,332917500}, {994042869,607637909}, {784366896,187042198},
{200105950,610383617}, {826144101,905199409}, {24835788,324705858},
{277723420,728522750}, {630447729,937469734}, {221564719,91059621},
{548009742,327404397}, {227909712,840292896}, {542525953,664345792},
{875391387,975232306}, {829573197,125234027}, {332393412,80824462},
{137298543,537715464}, {439096431,641313184}, {203515829,441692082},
{205715688,667575336}, {416227233,414575851}, {838344120,95970179},
{976010983,268810085}, {183789536,362685970}, {490023328,406886322},
{357540544,401985157}, {70912036,799416867}, {587931344,340081589},
{500905973,96873619}}};
// Take the union of poly1.
Clipper2Lib::Clipper64 clipper;
Clipper2Lib::Paths64 poly2, poly3;
clipper.AddClip(poly1);
clipper.Execute(ClipType::Union, FillRule::NonZero, poly2);
// Now the polygon is split into 92 non-self-intersecting pieces, with the
// following numbers of vertices: 3, 4, 40, 63, 3, 3, 3, 20, 48, 3, 3, 14,
// 250, 3, 3, 5, 4, 3, 3, 3, 5, 23, 3, 3, 159, 3, 4, 11, 4, 3, 3, 3, 4, 3, 3,
// 4, 3, 15, 3, 3, 4, 3, 3, 4, 4, 3, 3, 3, 4, 6, 11, 4, 3, 3, 4, 22, 3, 47,
// 3, 3, 4, 3, 3, 3, 3, 3, 3, 3, 7, 4, 4, 26, 3, 3, 3, 3, 3, 3, 17, 4, 4, 3,
// 3, 4, 4, 3, 10, 4, 4, 3, 3, 3
// Triangulate poly2. This never returns:
Clipper2Lib::Triangulate(poly2, poly3, true);