Falls on 10000 random points on Win32 on stack overflow: about poly2tri HOT 16 CLOSED

Falls in SweepContext::MeshClean() calling itself a lot of times.

If this gets fixed soon, I may test this more massively. Up to 1M of points for 
performance and also with data generating floating-point round-off errors like 
commented in code above.

just took a quick glance at the code.

When adding steiner points they must be inside the rectangle polygon.
Since you use the point set to find max an min x,y values there should be a 
chance that one of the points in the set will be on the edge of the rectangle 
you create, maybe this is your problem.

The triangulation algorithm assume that given polygon isn't self intersecting 
or touching and that steiner point are inside the polygon and not on the edge 
or outside.

Well.. not only a chance, atleast 2 points would be on the corner or edge of 
the rectangle. Try growing the rectangle a tiny bit and see if it works better.

Did this suggestion solve your problem? Want to know if I can close this issue 
:)

Adding these lines after min-max finding:
  minx -= 100;
  miny -= 100;
  maxx += 100;
  maxy += 100;

Didn't solve the problem - I note that values generated are from 0 to approx. 
32K so adding 100 to boundary should be more than enough.

Ah I think I know the issue. 

The MeshClean algorithm is recursive. It traverse the triangle graph 
recursively in a polygon until it finds an edge. Since we only got a rectangle 
with 4 edges and a massive amount of internal triangles the recursive depth can 
get really big.

I know someone rewrote MeshClean to be nonrecursive: see bottom of this issue

http://code.google.com/p/poly2tri/issues/detail?id=12&can=1

this is not the c++ version but I guess you could just port it. I agree that 
current MeshClean is a weakness and probably should be rewritten.

Well I think you should really fix that in c++ version. I have switched to use 
q-hull library for delaunay triangulation as even when you fix the issue, I'm 
not quite sure that your algorithm is really stable.

Well this lib is excellent for triangulating polygons with valid input. eg. no 
duplicate points, touching or intersecting edges. For that I'd say it is really 
stable. Thats what it was written for originally.

qhull is a nice lib, so unless you need constrained triangulation it is 
probably a better solution.

Well yes, the qhull is really working, but the interface is terrible. Our 
company would however also use stable constrained triangulation (surface 
remeshing, etc...). But my point is that anyone who downloads the code will 
test it like I did and stack overflow errors on first run isn't probably the 
image of library you would like to have.

The c++ version is a simplified port of the java version I wrote. The java 
version separates polygon and pointset triangulations and have different 
MeshClean functions so this problem never arise. 

I have notified mason and hopefully he can implement a non recursive mesh clean 
for the c++ version. I think most have used this lib as a polygon tesselator 
and not used that many steiner points.

I can fix this, although I need to make the time. This is a hobby project for 
me, not used professionally, and I have too many other side interests I'm 
pursing at the moment. 

I have a week off from work over the holidays, and will commit several hours to 
finding a good solution.

With 10000 random points, you may have some duplicate points. You need to 
provide poly2tri with a valid input set to work correctly, and all the points 
should be contained within your constrained edges.

I will add a non-recursive version of MeshClean for good measure.

Well my code is obviously removing the duplicated points so that's not the 
problem.

I have the same problem: With around 20000 Steiner points (the limit varies), I 
get a stack overflow in SweepContext::MeshClean. I make sure that there are no 
duplicate points.

Could you please provide the promised non-recursive version of MeshClean? Would 
help me a lot.

Well I worked out a replacement for MeshClean, using a std::stack instead of 
the "real" stack. I tested it with 300,000 Steiner points, it worked. For 
10,000 Steiner points, the destruction of the CDT object takes exactly the same 
time with your and my version (both 750 msec). Your testbed also runs without 
errors.

I wonder if this could be implemented more efficiently - destruction of a CDT 
object with 300,000 Steiner points takes as long as 38 sec (but at least there 
is no overflow :) ).

Attached you'll find the code.
* added  #include <stack>
* new version of SweepContext::MeshClean
* (no other changes)

Well instead of calling destructor allocate on custom memory managed heap and 
throw the memory in heap away (without calling destructors).