Concave forms are not triangulated correctly

[GoogleCodeExporter]

I recently discovered a small problem when I tried to triangulate
concave shapes. I don't know if I used your library in a wrong way or if
there's a bug in it.

The situation is the following: I have a concave shape that looks like a
"C", composed of 4 points. I would expect, that two triangles are
returned for this shape: One for the upper half, one for the lower one.
Unfortunately, the two triangles do exceed the natural given form of the
"C" and don't represent the shape correctly.
I created a small test case I attached for you to reproduce this
behaviour. I know this test case is not very good, but it shows the
problem I have.
I also implemented a small extension (AdvancedPolygonPoint) to keep a
unique Id for each TriangulationPoint. It was easier that way to get to
the problem :)

Original issue reported on code.google.com by furtelw...@gmail.com on 4 Jul 2011 at 2:14

Attachments:

• [Triangulation Test.zip](https://storage.googleapis.com/google-code-attachments/poly2tri/issue-26/comment-0/Triangulation Test.zip)

[GoogleCodeExporter]

You are triangulating a PointSet and not a Polygon.

A PointSet is just a bunch of points in the plane that the triangulator will 
perform a Delaunay triangulation on. The end result should result in a convex 
triangulation (tho not 100% implemented yet). But in most cases you endup with 
a triangulation that is convex. 

What you want to do is to Triangulate a Polygon(the "C") so use a Polygon class 
instead of a PointSet.

Original comment by thahlen@gmail.com on 4 Jul 2011 at 2:46

• Changed state: Done