Triangulation, rare infinite loop

[Evenedric]

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);

[shaolo1]

I love the idea of this being fuzz tested. Can you share how you implemented this and how it might be integrated?

[AngusJohnson]

Thanks. There are several issues here that will need fixing. Stay tuned 😁.

Edit: I know where the problem is, it's in Delaunay::CreateInnerLocMinLooseEdge().
But while the purpose of that code block is very simple to understand, doing it reliably / safely is unfortunately really tricky. So I'm still waiting to have the time and brainspace to fix it.

And please note that this triangulation code is labeled as a Beta Release because I anticipated finding a few residual bugs.

[undefined06855]

I can confirm I'm also getting an infinite loop sometimes with delaunay, since clipper2-ts has apparently been fixed, would the fix be able to be put onto the c++ clipper2 repo?

[baobaotuo]

Wonder if this PR can help #1077
@undefined06855

[jpt]

I can confirm I'm also getting an infinite loop sometimes with delaunay, since clipper2-ts has apparently fixed, would the fix be able to be put onto the c++ clipper2 repo?

@AngusJohnson I could write some notes on the changes I made in clipper2-ts for the different triangulation issues in case they are applicable/useful? some changes addressed multiple issues. I'm not sure if what I ended up with made the best performance/correctness tradeoffs, or if they are how you're thinking about developing the algorithm though, so it could be that my "fixes" will later change to match your own 😅 either way, happy to share what I ran into

[ryi3r]

Hi, I'm encountering the same issue with:

Clipper.Triangulate(new PathsD(
    [
        [
            new(352.07, -1.02),
            new(330.13, 21),
            new(471, 21),
            new(471, 321),
            new(237.91, 321),
            new(198.45, 389.35),
            new(-61.35, 239.35),
            new(22.5, 94.11),
            new(-72.19, -0.22),
            new(139.53, -212.76),
        ],
        [
            new(33.868, -0.424),
            new(117.303, 82.696),
            new(116.096, 82),
            new(41.096, 211.904),
            new(171, 286.904),
            new(246, 157),
            new(146.183, 99.37),
            new(246, -0.824),
            new(139.734, -106.69),
        ],
        [
            new(246, 96),
            new(246, 246),
            new(396, 246),
            new(396, 96),
        ]
    ]
), 0, out var _);

This never seems to return.