Infinite recursion with invalid polygons

[j-cano]

Hi,

With the attached example there is an infinite recursion problem in the EdgeEvent function.

I know poly2tri doesn't test for invalid input, but I would expect a reasonable exception, like it is usually the case. However, in this case you get a stack overflow in Debug and, even worse, in Release and due to compiler optimizations, an infinite loop.

I tried to understand the problem reading the paper poly2tri is based on and following the code, but I got lost at EdgeEvent, so I just did a very ugly check of pointers to try to avoid this. I hope someone with a deeper knowledge about the algorithm can improve this, maybe just adding some checking following backtracking style to avoid several EdgeEvent recursion with the same parameters if this should not happen (which I think it should be the case, but since I don't fully understand what is happening here...).

Thanks.

polygon.txt

[pierre-dejoue]

Hi @j-cano,

I reproduced your error (see branch on my fork: polygon-infinite-loop)

There is an infinite loop with four EdgeEvent calls that repeat themselves, due to three consecutive points of the input data that are considered COLLINEAR by Orient2d, although they are not. The three points are:

p2t::Point(-0.018708692216939, -0.401255684648273)
p2t::Point(-0.018668203838252, -0.401249612987052)
p2t::Point(-0.018659298457706, -0.401248286336634)

If you change the EPSILON constant in poly2tri, for example from 1e-12 to 1e-16:

const double EPSILON = 1e-16;

Your test case will pass with flying colors!

Result in testbed:

BTW, your test case coud be interesting to add to the testbed data. Would you agree to that? Any suggestion for a filename, or reference that could be given for that data? This looks like a city landscape.

Going back to the issue itself, I wonder if we should try to improve the handling of COLLINEAR points in EdgeEvent, or change Orient2d. We have other use cases where the COLLINEAR case leads to errors that can be circumverted simply by tuning the EPSILON constant (e.g. The test case with the narrow quad which I added recently).

One option could be to get rid of the EPSILON constant in Orient2d, and keep it in InScanArea (the only other function where that constant is used, I think rightfully because on the FlipScan event,, we want to exclude collinear points with the triangle the flip originated from).

[j-cano]

Hi @pierre-dejoue,

Yes, I agree to adding the data to the testbed and yes, as you said, it is a city.

About the issue, after some more work with poly2tri I found two other similar problems (infinite recursion/stack overflow):

• One problem is related with FlipEdgeEvent. I solved it like the EdgeEvent problem, detecting in some dirty way that the problem is happening.

• The other problem is related with Fill*EdgeEvent methods. In this case, I changed the returned value of several functions from void to bool indicating if the input has been changed. Before the recursive call you can check if you have changed the input and throw an exception if it hasn't changed, since that would result in an infinite loop.

I could try to find examples for both cases if you are interested.

As with my first solution, these are dirty tricks since I don't fully understand what is happening, I see you have a deeper knowledge of the algorithm and your solutions would be better. Surely get rid of EPSILON or adapt it to the input of the function would be an improvement and provide more triangulations.

For me, the even bigger issue here is not only that the polygon is not triangulated, although it would be nice if possible, but that the problem can't be handled (stack overflow and/or infinite loop). My current global solution is: I assume some input will not be triangulated (maybe not well cleaned, maybe not cleaned at all, maybe I did something bad to it in runtime) and I am happy if this just throws an exception, I will catch that exception, log a warning and triangulate it with another more robust algorithm (not Delaunay, ugly triangles, but probably enough to keep working). Can you think of a pretty solution for this? For example, throwing an exception for the city data in the right place.

Thanks.

[pierre-dejoue]

Hello,

With the latest changes on the libbrary, notably the patch on the collinearity check (#40), this data set is now passing correctly. I created a PR #45 to add the file to the list of test files in the project.