Overlapping triangles generated during triangulation #1062
Description
Thanks for this library! I've been using version 1 for years on very large polygons, and finally moved over to Clipper2Lib to use its new triangulation feature.
It's been generally well-behaved even on some scary complex polygons, but I've occasionally been getting some odd results from it which maybe I'm noticing more than other folks since I've been trying to join the generated triangles together into a solid mesh with connectivity data between the triangles.
The weirdness is that on complicated triangulation jobs, it seems to often generate at least one pair of partially or fully overlapping triangles; triangles which share two vertices, but are both on the same side of the shared edge.
In any case, the overlapping triangles in this test case are triangles number 35 and 57, and the shared vertices are:
Tri 35 -> vertex 0: 30155148,47024808
Tri 57 -> vertex 0: 30155148,47024808
Tri 35 -> vertex 2: 30493492,48924492
Tri 57 -> vertex 2: 30493492,48924492
And the mismatched vertices on the triangles are:
Tri 35 -> vertex 1: 30201650,47060500
Tri 57 -> vertex 1: 30258540,46491468
(there may be other cases of overlapping triangles in this test case, but I stopped looking after hitting the first ones!)
Apologies for the size of this test case, this is actually cut down a huge amount from where I began with it! (originally it had more than 300 holes in this large polygon! I got it down to just these two while still triggering the misbehaviour, so hopefully it isn't too much to throw at you all at once!)
Is there more that I can do to help track down what's going wrong here?
Clipper2Lib::Paths64 polys = {
{
{37905940,38275460}, {37910048,38329120}, {37932480,38342692},
{38024372,38341952}, {38036352,38318980}, {38027692,38302340},
{39274280,38577580}, {39272812,38676148}, {39298968,38692848},
{39374360,38680600}, {39400748,38621300}, {39390060,38603140},
{40421468,38830860}, {40408560,38843492}, {40389152,38921168},
{40405920,38936288}, {40492040,38916380}, {40500000,38892848},
{40478980,38843560}, {41353300,39036600}, {41331900,39106700},
{41351136,39125940}, {41456060,39107320}, {41467108,39079500},
{41460008,39060160}, {42309388,39247700}, {42351108,39295980},
{42377708,39289920}, {42387832,39265008}, {42942760,39387540},
{42882808,40444728}, {42351900,40896588}, {42350732,40895220},
{42323052,40901368}, {42310448,40931860}, {39440892,43374200},
{38841212,42663232}, {38572392,42459248}, {36975932,42011768},
{36734688,42957568}, {36903560,43524960}, {37069180,43546652},
{37069000,43547432}, {37072340,43561908}, {37079388,43576200},
{37085420,43580600}, {37096520,43583836}, {37104260,43578180},
{37105140,43564312}, {37099908,43550680}, {37360000,43584760},
{38167500,44267260}, {38251332,44386660}, {37256900,45233040},
{37169300,45341412}, {37157580,45337432}, {36405892,45302508},
{35429860,45162432}, {34447972,45259352}, {33569032,45533188},
{32784500,45548520}, {32529690,45484780}, {32153798,45907540},
{32010258,46323340}, {32048420,46560324}, {32042600,46581220},
{32045668,46585732}, {32052890,46588128}, {32086960,46799660},
{32424418,47162832}, {33209480,47327720}, {33904352,47160380},
{34268920,46851152}, {35334160,46557272}, {36423952,46587508},
{36428448,46588532}, {36428128,46592012}, {36441588,46614020},
{36465740,46612832}, {36472528,46609468}, {36473712,46598808},
{37137640,46749580}, {38453700,49880780}, {36598340,51842072},
{36586760,51838700}, {36517928,51898712}, {36517620,51914704},
{36523780,51920888}, {33495080,55122540}, {31846060,54686660},
{31463880,53506380}, {31060200,51600360}, {31692980,51360580},
{32533320,51275600}, {32957400,51116860}, {33193740,50893216},
{33994752,50526908}, {34468532,50122596}, {35522260,49579932},
{35836720,49091180}, {35836720,48583280}, {35650060,48259980},
{35211180,48006592}, {34469540,48034520}, {33975820,48305080},
{33181398,49059084}, {31843220,49658540}, {30691750,49860620},
{30511680,49010372}, {30516690,49005488}, {30522290,48967640},
{30498860,48924448}, {30493492,48924492}, {29867610,45969256},
{30690472,44411840}, {30797230,44079008}, {30831700,43824620},
{30836170,43841088}, {30901210,43902192}, {30925030,43894092},
{30952460,43799468}, {30933898,43778940}, {30866170,43771720},
{30833460,43811668}, {31425860,39441168}, {31905600,39235292},
{31906120,39297228}, {31929780,39309560}, {32022430,39261300},
{32024580,39232020}, {31996918,39196100}, {32144920,39132592},
{32142610,39148048}, {32154060,39187820}, {32163310,39197920},
{32174700,39196300}, {32193310,39187560}, {32196150,39178888},
{32192900,39156112}, {32183930,39133112}, {32175200,39125520},
{32167950,39122700}, {34185628,38256840}, {34129620,38635528},
{34242420,39592760}, {34219120,40424272}, {34095992,41096400},
{34236580,41896268}, {34639840,42289620}, {34772740,42483120},
{34765380,42488320}, {34748740,42526548}, {34725920,42531688},
{34707548,42554132}, {34696480,42614188}, {34743548,42644500},
{34795108,42638348}, {34797540,42633148}, {34816068,42641040},
{34864720,42617040}, {35044540,42878864}, {35523268,42511440},
{35400440,41788820}, {35472472,40874728}, {35660868,40422660},
{35575100,40339460}, {35728120,39702328}, {35734352,39433480},
{35998920,38157000}, {35858880,38061508}, {35864232,37824680}
},
{
{30154670,47015412}, {30155148,47024808}, {30201650,47060500},
{30210820,47058492}, {30230630,47035180}, {30233010,46995952},
{30201508,46976680}, {30190080,46974952}
},
{
{30216202,46463664}, {30212320,46468180}, {30215682,46504800},
{30220540,46507912}, {30239450,46507080}, {30258540,46491468},
{30254270,46468760}, {30250200,46462760}
}
};
polys = Clipper2Lib::Union(polys, Clipper2Lib::FillRule::NonZero);
Clipper2Lib::Paths64 sol;
Clipper2Lib::TriangulateResult retval = Clipper2Lib::Triangulate(polys, sol, true);
REQUIRE( retval == Clipper2Lib::TriangulateResult::success );
REQUIRE( sol.size() > 57 );
printf( "Tri 35 -> vertex 0: %d", sol[35][0] );
printf( "Tri 35 -> vertex 1: %d", sol[35][1] );
printf( "Tri 35 -> vertex 2: %d", sol[35][2] );
printf( "Tri 57 -> vertex 0: %d", sol[57][0] );
printf( "Tri 57 -> vertex 1: %d", sol[57][1] );
printf( "Tri 57 -> vertex 2: %d", sol[57][2] );