How to convert a polygon to a set on non-overlapping triangles?

Question

I have a coordinate set of 2D points that form a closed polygon. I need to generate a set of 2D triangles that distribute the polygon completely.

There are no constrains as such except that the triangles should fill the area of polygon completely. It would be even more helpful if it is a standard algorithm I could implement.

Answer 1

As mentioned above, Delaunay triangulation is a rather complicated algorithm for this task. If you accept O(n^2) running time, you may try Ear Clipping algorithm which is much more easier to understand and to code. The basic idea is the following. Every polygon with >= 4 vertexes and no holes (i.e. its border is a single polyline without self-intersections and self-tangencies) has at least one "ear". An ear is a three consecutive vertexes such that the triangle built on them lies inside the polygon and contains no other points of the polygon inside. If you "cut an ear" (add a triangle to the answer and replace remove the middle point of these three points), you reduce the task to a polygon with less vertexes, and so on. Ears may be trivially (by definition) found in O(n^2) resulting in a O(n^3) triangulation algorithm. There is O(n) ear finding algorithm, and, though it is not very complicated, it is rather long to be described in a couple of phrases.

Furthermore, if you need faster algorithms, you should look something about monotone polygons triangulation and splitting a polygon into monotone ones. There even exists a linear-time triangulation algorithm, but its just as complicated as Delaunay triangulation is.

You may consider Wikipedia article and see an small overview of existing methods there.

Answer 2

The best way to triangulate general polygons is to compute the constrained Delaunay triangulation - this is a standard Delaunay triangulation of the polygon vertices with additional constraints imposed to ensure that the polygon edges appear in the triangulation explicitly. This type of approach can handle any type of polygon - convex, concave, polygons with holes, etc.

Delaunay triangulations are those that maximise the minimum angle in the mesh, meaning that such a triangulation is optimal in terms of element shape quality.

Coding a constrained Delaunay triangulation algorithm is a tricky task, but a number of good libraries exist, specifically CGAL and Triangle. Both these libraries implement an (optimally) efficient O(n*log(n)) algorithm.

Answer 3

If you don't require that the vertices of the triangles be vertices of the polygon, try a triangulation based on a trapezoidal decomposition, as in Fast Polygon Triangulation based on Seidel's Algorithm.