Polygon triangulation
|
|
In computational geometry, polygon triangulation is the decomposition of a polygon into a set of triangles.
A triangulation of a polygon P is its partition into non-overlapping triangles whose union is P. In the strictest 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.
A convex polygon is trivial to triangulate in linear time, by adding edges from one vertex to all other vertices. In fact, Bernard Chazelle showed in 1991 that any simple polygon can be triangulated in linear time.
Reference
- Bernard Chazelle, Triangulating a Simple Polygon in Linear Time, Discrete and Computational Geometry, 6, 1991, pp. 485 524.