0

CuttingEarsTriangulator possible bug

Anonymous 10 years ago 0
This discussion was imported from CodePlex

baucez wrote at 2013-04-19 16:03:

Hi! I'm using CuttingEarsTriangulator to draw complex polygons.
It works almost all the time but I found some cases in which method Triangulate gives me null even if the polygons is valid.

One of this cases is when I pass the following list of points:
0,0
0,1.894
-2.536,1.42
-5.072,1.42
-5.072,2.84
-10.144,2.84
-10.144,0

How can I get my triangles? Is there a workaround?

RobPerkins wrote at 2013-04-22 23:05:

I haven't studied the code in the Helix stack, but I've gotten very good Cutting Ear results from the archived CodeProject project at:

http://www.codeproject.com/Articles/8238/Polygon-Triangulation-in-C

The code is conveniently in C# and contains no dependencies on anything except .NET (probably .NET 1.1, so it would be good for any .NET stack)

objo wrote at 2013-04-26 22:23:

baucez: thanks for the example polygon - I will add a unit test for this case
RobPerkins: thanks for the link, I will have a look at that implementation, and possible use it to verify results

objo wrote at 2013-04-30 23:09:

the following code
           var polygon = new[]
                              {
                                  new Point(0, 0),
                                  new Point(0, 1.894),
                                  new Point(-2.536, 1.42),
                                  new Point(-5.072, 1.42),
                                  new Point(-5.072, 2.84),
                                  new Point(-10.144, 2.84),
                                  new Point(-10.144, 0)
                              };
            var result = CuttingEarsTriangulator.Triangulate(polygon);
gives the result
{0 1 2 3 4 5 6 0 2 3 5 6 6 2 3}
which looks correct to me...

baucez wrote at 2013-05-02 10:21:

Objo.. you are right!
I looked better at my code and I found that the list of points that I gave you was approximated.

If you try this code will fail:
  {
            var polygon = new[]
                {
                    new Point(0, 0),
                    new Point(0, 2.97),
                    new Point(-2.389999999999997, 2.97),
                    new Point(-2.389999999999997, 1.4849999999999999),
                    new Point(-4.7799999999999976, 1.4849999999999999),
                    new Point(-4.7799999999999976, 2.97),
                    new Point(-9.5599999999999987, 2.97),
                    new Point(-9.5599999999999987, 0),
                };

            var result = CuttingEarsTriangulator.Triangulate(polygon);
            Assert.IsNotNull(result);
        }
The problem is caused by double arithmetic approximations.
In particular (but I'm not sure is the only place in the code) the problem is in the comparisons at the end of CuttingEarsTriangulator.InsideTriangle method

objo wrote at 2013-05-08 15:28:

thanks! I have checked in the fix