CuttingEarsTriangulator possible bug

Apr 19, 2013 at 2:03 PM
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?
Apr 22, 2013 at 9:05 PM
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)
Coordinator
Apr 26, 2013 at 8:23 PM
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
Coordinator
Apr 30, 2013 at 9:09 PM
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...
May 2, 2013 at 8:21 AM
Edited May 2, 2013 at 8:25 AM
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
Coordinator
May 8, 2013 at 1:28 PM
thanks! I have checked in the fix