search

greenm01 / poly2tri

Automatically exported from code.google.com/p/poly2tri
Other
337 stars 85 forks source link

Stack overflow by endless recursion #116

Open andriy-andreyev opened 2 years ago

andriy-andreyev commented 2 years ago

Library stack overflow occurs in case of triangulation of some geometry.

Endless recursion backtrace: .... _poly2tritest.exe!p2t::Sweep::FlipScanEdgeEvent(p2t::SweepContext & tcx, p2t::Point & ep, p2t::Point & eq, p2t::Triangle & flip_triangle, p2t::Triangle & t, p2t::Point & p) poly2tritest.exe!p2t::Sweep::FlipEdgeEvent(p2t::SweepContext & tcx, p2t::Point & ep, p2t::Point & eq, p2t::Triangle t, p2t::Point & p) poly2tritest.exe!p2t::Sweep::FlipScanEdgeEvent(p2t::SweepContext & tcx, p2t::Point & ep, p2t::Point & eq, p2t::Triangle & flip_triangle, p2t::Triangle & t, p2t::Point & p) poly2tritest.exe!p2t::Sweep::FlipEdgeEvent(p2t::SweepContext & tcx, p2t::Point & ep, p2t::Point & eq, p2t::Triangle t, p2t::Point & p) poly2tritest.exe!p2t::Sweep::FlipScanEdgeEvent(p2t::SweepContext & tcx, p2t::Point & ep, p2t::Point & eq, p2t::Triangle & flip_triangle, p2t::Triangle & t, p2t::Point & p) poly2tritest.exe!p2t::Sweep::FlipEdgeEvent(p2t::SweepContext & tcx, p2t::Point & ep, p2t::Point & eq, p2t::Triangle * t, p2t::Point & p) poly2tritest.exe!p2t::Sweep::FlipScanEdgeEvent(p2t::SweepContext & tcx, p2t::Point & ep, p2t::Point & eq, p2t::Triangle & fliptriangle, p2t::Triangle & t, p2t::Point & p) ....

Test case:

std::vector<p2t::Point*> outlinePtr = {
new p2t::Point(450 , 2250),
new p2t::Point(450 , 1750),
new p2t::Point(400 , 1700),
new p2t::Point(350 , 1650),
new p2t::Point(350 , 500),
new p2t::Point(1050, 1700) };

std::vector<std::vector<p2t::Point*>> holesPtr = {{
new p2t::Point(980, 1636),
new p2t::Point(950, 1600),
new p2t::Point(650, 1230),
new p2t::Point(625, 1247),
new p2t::Point(600, 1250),
new p2t::Point(591, 1350),
new p2t::Point(550, 2050) }};

p2t::CDT cdt(outlinePtr);
for (const auto& holePtr : holesPtr)
    cdt.AddHole(holePtr);
cdt.Triangulate();

Geometry looks like:

test_img

andriy-andreyev commented 2 years ago

@greenm01 can you please advise what can lead to that problem? I can make tests and create PR with fixes.