jhasse / poly2tri

2D constrained Delaunay triangulation library
BSD 3-Clause "New" or "Revised" License
429 stars 89 forks source link

Stack overflow by endless recursion #41

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:

image