Incorrect Triangulation of simple 4 point set

[GoogleCodeExporter]

What steps will reproduce the problem?
1.Triangulate unconstrained pointset (0 0, 0 1, 1 1, 2 1)

What is the expected output? 

Two triangles

What do you see instead?

1 Triangle, not including all points

What version of the product are you using? 

Poly2Tri C# latest download 2010

On what operating system?

Windows 7

Please provide any additional information below.

If I perturn the last vertex to have a Y of say 2, it works correctly.
If I perturn slightly to say 2.1 it still fails

Original issue reported on code.google.com by de...@primethought.biz on 20 Aug 2010 at 6:15

[GoogleCodeExporter]

I'm maintaining the java version but this might be an issue with all releases. 

Just wierd that no one has noticed it before ;). I'll try to find the problem.

Original comment by thahlen@gmail.com on 20 Aug 2010 at 7:24

[GoogleCodeExporter]

Thanks for finding this issue!

There was no problem with the triangulation. But there are some triangles that 
should be removed after the triangulation that is added as part of the 
algorithm. Is special cases the code doing that could remove the first left or 
right valid triangle in a PointSet triangulation. The PolygonSet triangulation 
was not affected and since that is what I use mostly myself this problem had 
not emerged.

You can add this fix until I get in touch with the C# maintainer for the fix.

In class: DTSweep
In method: private static void FinalizationConvexHull( DTSweepContext tcx )
After the line:         TurnAdvancingFrontConvex( tcx, n2, n3 );
Add this:

        n1 = tcx.Front.Tail.Prev;
        if( n1.Triangle.Contains( n1.Next.Point ) && n1.Triangle.Contains( n1.Prev.Point ) )
        {
            t1 = n1.Triangle.neighborAcross( n1.Point );
            RotateTrianglePair( n1.Triangle, n1.Point, t1, t1.OppositePoint( n1.Triangle, n1.Point ) );
        }                
        n1 = tcx.Front.Head.Next;
        if( n1.Triangle.Contains( n1.Prev.Point ) && n1.Triangle.Contains( n1.Next.Point ) )
        {
            t1 = n1.Triangle.NeighborAcross( n1.Point );
            RotateTrianglePair( n1.Triangle, n1.Point, t1, t1.OppositePoint( n1.Triangle, n1.Point ) );
        }                

Hope I didn't add a typo when converting my Java code to C# :-)

Original comment by thahlen@gmail.com on 20 Aug 2010 at 11:30

• Changed state: Fixed

[GoogleCodeExporter]

I just added Issue #15 for the c++ version, and then noticed this. Perhaps it 
is related? I'm also working with simple 4 point sets for now, so could this 
issue still exist in the c++ version?

Original comment by roond...@gmail.com on 16 Dec 2010 at 8:52