Stack overflow on 204 point simple polygon input (C++)

[GoogleCodeExporter]

What steps will reproduce the problem?
1. Triangulate a particular point set

What is the expected output? What do you see instead?
Stack overflow leading to segfault. 

What version of the product are you using? On what operating system?
Most recent code base, Linux 2.6.32-33-generic x86_64. I will test with MinGW 
compiled version soon. 

Please provide any additional information below.

Included file contains a double array where rand_test[2*i] is poly[i].x and 
rand_test[2*i+1] is poly[i].y

I encountered this stack overflow when running a stress test on my convex 
decomposition code. I generated a complex polygon by stringing together 
entirely random points in the range -2000 to 2000 in both x and y, and used a 
custom polygon simplification algorithm to extract the perimeter of the 
polygon. 

If you examine this test case you will notice that it is a completely valid 
polygon without extreme angles anywhere, it just has a few small triangular 
features. In any case there should not be a stack overflow here. Here is 
relevant part of stack trace: 

#93544 0x0000000000427d44 in CDT_testRoutine (data=0x6b3f80, 
    length=408) at Polygon.cpp:318
318     cdt.Triangulate();
(gdb) 
#93543 0x000000000047ff97 in p2t::Sweep::Triangulate(p2t::SweepContext&) ()
(gdb) 
#93542 0x000000000047fddc in p2t::Sweep::SweepPoints(p2t::SweepContext&) ()
(gdb) 
#93541 0x000000000047f5a9 in p2t::Sweep::EdgeEvent(p2t::SweepContext&, 
p2t::Point&, p2t::Point&, p2t::Triangle*, p2t::Point&) ()
(gdb) 
#93540 0x000000000047f18e in p2t::Sweep::FlipEdgeEvent(p2t::SweepContext&, 
p2t::Point&, p2t::Point&, p2t::Triangle*, p2t::Point&)
    ()
(gdb) 
#93539 0x000000000047f18e in p2t::Sweep::FlipEdgeEvent(p2t::SweepContext&, 
p2t::Point&, p2t::Point&, p2t::Triangle*, p2t::Point&)
    ()
(gdb) 
#93538 0x000000000047f18e in p2t::Sweep::FlipEdgeEvent(p2t::SweepContext&, 
p2t::Point&, p2t::Point&, p2t::Triangle*, p2t::Point&)
    ()
(gdb) 
#93537 0x000000000047f18e in p2t::Sweep::FlipEdgeEvent(p2t::SweepContext&, 
p2t::Point&, p2t::Point&, p2t::Triangle*, p2t::Point&)
    ()
(gdb) 

Good luck!

Original issue reported on code.google.com by stevenlu...@gmail.com on 19 Dec 2011 at 10:49

Attachments:

• poly2tri_stackoverflow.c

[GoogleCodeExporter]

Yeah I have seen that lib. But it doesn't support Java ;)

Original comment by thahlen@gmail.com on 4 Jan 2012 at 2:01

[GoogleCodeExporter]

Here you have the source for my SweepLine LineSegment intersection lib.
It's an eclipse project.

I will create a repository later so it will be easy to track changes.

Original comment by thahlen@gmail.com on 5 Jan 2012 at 2:24

Attachments:

• poly2tri-intersection-alpha-0.1.zip

[GoogleCodeExporter]

Thanks! Unfortunately I don't think i can spare the time to port that to C++ 
just yet but a proper line segment intersection algorithm will make my code 
much more optimal than it currently is. 

I wanted to check in with you and see how it's going with the fixing of the 
stack overflow issue with the CDT. 

Original comment by stevenlu...@gmail.com on 25 Jan 2012 at 11:48

[GoogleCodeExporter]

I also have a question for you: Does poly2tri handle "islands"? What I mean by 
this is shapes contained within holes (I know it handles holes). 

I guess it's simple enough to determine if an island is valid (non intersecting 
with the rest of the holes/edges) and then just treat it as a separate 
triangulation. Well, nevermind then. 

Original comment by stevenlu...@gmail.com on 25 Jan 2012 at 11:54

[GoogleCodeExporter]

Computational geometry is fraught with floating point inaccuracies. Poly2tri 
works well with proper data sets that consist of non-repeating points.

Always keep in mind epsilon, and try scaling points to -1/1, as Thomas 
suggested.

When points are given with floating point coordinates, and when computations 
are done with floating point accuracy, there may often be rounding errors that 
cause problems. Provide a robust input set to poly2tri, and it does a 
remarkable job of providing good results.

Original comment by mason.gr...@gmail.com on 4 Feb 2012 at 9:31

• Changed state: WontFix

[GoogleCodeExporter]

I'm pretty certain that my test files do not have repeating points, and they do 
not have points that are within epsilon of each other. 

Do you think it's possible to look into the issue and provide a fix that will 
resolve the situations I encountered into the throwing of an exception rather 
than a stack overflow? As a first hack, maybe a check to see if recursion has 
repeated across the same points some number of times, then just simply throw an 
exception (since at that point it would be clear that stack overflow will occur)

Original comment by stevenlu...@gmail.com on 4 Feb 2012 at 9:48

[GoogleCodeExporter]

Sorry I should have accepted this as a confirmed issue.

This is an algorithmic issue. Yes is fail due to precision but a slightly 
different algorithm should handle these cases. 

I have tried to rewrite the algorithm but haven't got it working quite yet. I 
have been busy with other things the past two week. But this is an issue I'm 
working on.

This attached image describes the issue. The points ABC and D are on a single 
line. Due to epsilon precision the orient2d test says that ABD are not 
collinear but BCD is. This will cause the flipscan algorithm to think that it 
can flip the triangles between ABCD but when it tries with BCD it will fail. 
This will result in a endless loop trying to flip the triangles between ABCD in 
both down and up direction. In a perfect world without float precision the 
algorithm would work fine but now it needs some tweaking to handle these cases.

Since steven is clipping polygons these cases can occur when multiple polygons 
cut an edge resulting in several points being aligned on a line. This is the 
first time this issue has been noted. The flip-scan algorithm has to be 
rewritten so it traverses the triangles in triplets instead of scanning for the 
next point.

Original comment by thahlen@gmail.com on 5 Feb 2012 at 12:47

• Changed state: Accepted

Attachments:

• flip_scan.gif

[GoogleCodeExporter]

As you suggested I guess we could add a recursive counter to the triangulation 
context and set an upper limit and throw an exception if it is reached as a 
temporary thing until I get a new improved algorithm working. I think I have 
never seen a recursive depth deeper than 9 when profiling so a depth of 20 
should be enough.

Original comment by thahlen@gmail.com on 5 Feb 2012 at 1:13

[GoogleCodeExporter]

Has there been progress on this issue? 

Thanks

Original comment by stevenlu...@gmail.com on 9 Jun 2012 at 5:39

[GoogleCodeExporter]

Hi,

We have recently run into this problem with our game using the c++ port.  (To 
see how we use it, see issue 74).  

Is there any way that we could help with getting this fixed?  There was 
reference above to creating a 'separate repository' to track changes with 
getting it fixed.  Does that exist somewhere?

Thanks!

Original comment by buckyballreaction on 24 Oct 2013 at 9:33

[GoogleCodeExporter]

I realised that rewriting the algorithm can not solve this problem fully just 
improve the float precision so you might get less problems. I kept it open to 
remember that I want to improve this if I get the time.

One way to get around this issue should be to lower the precision for 
intersection points.
So lets say you intersect a line with a triangle and get two intersection 
points. You might get these points with 15 decimal precision then round them to 
like 12 decimals or less. You shouldn't see much of a change in your polygons 
but these kind of error should hopefully go away.

So if you can live with lesser decimal precision. Round all point values to 12 
decimals or less after you have preformed intersection operations.

You can get a similar precision issue with a very simple example.
Just take a square polygon with two square holes.

Hole 1: a,b,c,d : [0,0.00000000000001],[1,0.00000000000001],[1,1],[0,1]
Hole 2: e,f,g,h : [2,0],[3,0],[3,1],[2,1]

This look like a very simple and straight forward polygon to triangulate.

The bottom edge of the holes just differs in the 15th decimal. During the 
triangulation poly2tri will try to form a triangle between a,b and e all these 
three points it pretty much on a straight line and poly2tri will fail.

These problems can arise between three or more points that are to close to a 
straight line in any direction.

So try to round the point values to less than 12 decimals after intersections 
and see if that helps!

I assume that all values are in the range [-1,1] when using 12 decimals.

Original comment by thahlen@gmail.com on 24 Oct 2013 at 10:13

[GoogleCodeExporter]

Just adding a little random wiggle to the intersection points would have the 
same result

Original comment by thahlen@gmail.com on 24 Oct 2013 at 10:23