Triangulation of polygon

Question

Im trying to triangulate a polygon for use in a 3d model. When i try using the ear method on a polygon with points as dotted below, i get triangles where the red lines are. Since there are no other points inside these triangles this is probably correct. But i want it to triangulate the area inside the black lines only. Anyone know of any algorithms that will do this?

Answer 1

There are many algorithms to triangulate a polygon that do not need partitioning into monotone polygons first. One is described in my textbook Computational Geometry in C, which has code associated with it that can be freely downloaded from that link (in C or in Java). You must first have the points in order corresponding to a boundary traversal. My code assumes counterclockwise, but of course that is easy to change. See also the Wikipedia article. Perhaps that is your problem, that you don't have the boundary points consistently organized?

Answer 2

The usual approach would be to split your simple polygon into monotone polygon using trapezoid decomposition and then triangulate the monotone polygons. The first part can be achieved with a sweep line algorithm. And speed-ups are possible with the right data-structure (e.g. doubly connected edge list). The best description of this, that I know, can be found in Computational Geometry. This and this also seem helpful.

Answer 3

Wikipedia suggest that you break the polygon up into monotone polygons. You check that the polygon is not concave by simply checking for all angles being less than 180 degrees - any corners which has a angle of over 180 is concave, and you need to break it at that corner.

Answer 4

If you can use C++, you can use CGAL and in particular the example given here that can triangulate a set of non-intersected polygons. This example works only if you already know the black segments.

Answer 5

You need to use the EarClipping algorithm, not the Delaunay. See the following white paper: http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf