Polygon triangulation

In computational geometry, polygon triangulation is the decomposition of a polygonal area (simple polygon) P into a set of triangles,^[1] i.e., finding the set of triangles with pairwise non-intersecting interiors whose union is P.

In the strict sense, these triangles may have vertices only at the vertices of P. In a less strict sense, points can be added anywhere on or inside the polygon to serve as vertices of triangles. In addition, the cases of triangulation of a simple polygon and of a polygonal area with polygonal holes are treated separately.

Triangulations may be viewed as special cases of planar straight-line graphs. When there are no holes or added points, triangulations form maximal outerplanar graphs.

Polygon triangulation without extra vertices

Over time a number of algorithms have been proposed to triangulate a polygon.

Special cases

A convex polygon is trivial to triangulate in linear time, by adding diagonals from one vertex to all other vertices. Including this and other methods, the total number of ways to triangulate a convex n-gon by non-intersecting diagonals is , a solution found by Euler.^[2]

A monotone polygon can easily be triangulated in linear time with either the algorithm of A. Fournier and D.Y. Montuno,^[3] or the algorithm of Godfried Toussaint.^[4]

Ear clipping method

A polygon ear

One way to triangulate a simple polygon is based on the fact that any simple polygon with at least 4 vertices without holes has at least two so called 'ears', which are triangles with two sides being the edges of the polygon and the third one completely inside it (and with an extra property unimportant for triangulation).^[5] The algorithm then consists of finding such an ear, removing it from the polygon (which results in a new polygon that still meets the conditions) and repeating until there is only one triangle left.

This algorithm is easy to implement, but suboptimal, and it only works on polygons without holes. An implementation that keeps separate lists of convex and concave vertices will run in O(n²) time. This method is known as ear clipping and sometimes ear trimming. An efficient algorithm for cutting off ears was discovered by Hossam ElGindy, Hazel Everett, and Godfried Toussaint.^[6]

Using monotone polygons

Breaking a polygon into monotone polygons

A simple polygon may be decomposed into monotone polygons as follows.^[1]

For each point, check if the neighboring points are both on the same side of the 'sweep line', a horizontal or vertical line on which the point being iterated lies. If they are, check the next sweep line on the other side. Break the polygon on the line between the original point and one of the points on this one.

Note that if you are moving downwards, the points where both of the vertices are below the sweep line are 'split points'. They mark a split in the polygon. From there you have to consider both sides separately.

Using this algorithm to triangulate a simple polygon takes O(n log n) time.

Computational complexity

For a long time, there was an open problem in computational geometry whether a simple polygon can be triangulated faster than O(n log n) time.^[1] Then, Tarjan & van Wyk (1988) discovered an O(n log log n) algorithm for triangulation,^[7] later simplified by Kirkpatrick, Klawe & Tarjan (1992).^[8] Several improved methods with complexity O(n log^* n) (in practice, indistinguishable from linear time) followed.^[9][10][11]

Bernard Chazelle showed in 1991 that any simple polygon can be triangulated in linear time, though the proposed algorithm is very complex.^[12]

The time complexity of triangulation of a polygon with holes has an Ω(n log n) lower bound.^[1]

See also

• Nonzero-rule
• Tessellation
• Catalan number
• Point set triangulation
• Delaunay triangulation
• Tiling by regular polygons
• Minimum-weight triangulation, for a point set and for a simple polygon

References

• Amato, Nancy M.; Goodrich, Michael T.; Ramos, Edgar A. (2001), "A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry 26 (2): 245–265, doi:10.1007/s00454-001-0027-x, ISSN 0179-5376, http://parasol.tamu.edu/publications/abstract.php?pub_id=185 

External links

• Demo as Flash swf, A Sweep Line algorithm.
• Song Ho's explanation of the OpenGL GLU tesselator