Polygon triangulation
Template:Short description Template:Broader
In computational geometry, polygon triangulation is the partition of a polygonal area (simple polygon) Template:Mvar into a set of triangles,<ref name= bkos>Template:Citation</ref> i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is Template:Mvar.
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 verticesEdit
Over time, a number of algorithms have been proposed to triangulate a polygon.
Special casesEdit
.svg){kind=link}
It is trivial to triangulate any convex polygon in linear time into a fan triangulation, by adding diagonals from one vertex to all other non-nearest neighbor vertices.
The total number of ways to triangulate a convex n-gon by non-intersecting diagonals is the (n−2)nd Catalan number, which equals
- <math>\frac{n(n+1)...(2n-4)}{(n-2)!}</math>,
a formula found by Leonhard Euler.<ref>Template:Citation</ref>
A monotone polygon can be triangulated in linear time with either the algorithm of A. Fournier and D.Y. Montuno,<ref>Template:Citation</ref> or the algorithm of Godfried Toussaint.<ref>Template:Citation</ref>
Ear clipping methodEdit
One way to triangulate a simple polygon is based on the two ears theorem, as the fact that any simple polygon with at least 4 vertices without holes has at least two "ears", which are triangles with two sides being the edges of the polygon and the third one completely inside it.<ref>Template:Citation</ref> 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 slower than some other algorithms, and it only works on polygons without holes. An implementation that keeps separate lists of convex and concave vertices will run in Template:Math 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.<ref>Template:Citation</ref>
Monotone polygon triangulationEdit
A simple polygon is monotone with respect to a line Template:Math, if any line orthogonal to Template:Math intersects the polygon at most twice. A monotone polygon can be split into two monotone chains. A polygon that is monotone with respect to the y-axis is called y-monotone. A monotone polygon with Template:Math vertices can be triangulated in Template:Math time. Assuming a given polygon is y-monotone, the greedy algorithm begins by walking on one chain of the polygon from top to bottom while adding diagonals whenever it is possible.<ref name= bkos/> It is easy to see that the algorithm can be applied to any monotone polygon.
Triangulating a non-monotone polygonEdit
If a polygon is not monotone, it can be partitioned into monotone subpolygons in Template:Math time using a sweep-line approach. The algorithm does not require the polygon to be simple, thus it can be applied to polygons with holes. Generally, this algorithm can triangulate a planar subdivision with Template:Math vertices in Template:Math time using Template:Math space.<ref name= bkos/>
Dual graph of a triangulationEdit
A useful graph that is often associated with a triangulation of a polygon Template:Math is the dual graph. Given a triangulation Template:Math of Template:Math, one defines the graph Template:Math as the graph whose vertex set are the triangles of Template:Math, two vertices (triangles) being adjacent if and only if they share a diagonal. It is easy to observe that Template:Math is a tree with maximum degree 3.
Computational complexityEdit
Until 1988, whether a simple polygon can be triangulated faster than Template:Math time was an open problem in computational geometry.<ref name= bkos/> Then, Template:Harvtxt discovered an Template:Math-time algorithm for triangulation,<ref>Template:Citation</ref> later simplified by Template:Harvtxt.<ref>Template:Citation</ref> Several improved methods with complexity Template:Math (in practice, indistinguishable from linear time) followed.<ref>Template:Citation</ref><ref name="Seidel">Template:Citation</ref><ref>Template:Citation</ref>
Bernard Chazelle showed in 1991 that any simple polygon can be triangulated in linear time, though the proposed algorithm is very complex.<ref>Template:Citation</ref> A simpler randomized algorithm with linear expected time is also known.<ref>Template:Citation</ref>
Seidel's decomposition algorithm<ref name="Seidel" /> and Chazelle's triangulation method are discussed in detail in Template:Harvtxt.<ref>Template:Citation</ref>
The time complexity of triangulation of an Template:Math-vertex polygon with holes has an Template:Math lower bound, in algebraic computation tree models of computation.<ref name= bkos/> It is possible to compute the number of distinct triangulations of a simple polygon in polynomial time using dynamic programming, and (based on this counting algorithm) to generate uniformly random triangulations in polynomial time.<ref>Template:Citation</ref> However, counting the triangulations of a polygon with holes is #P-complete, making it unlikely that it can be done in polynomial time.<ref>Template:Citation</ref>
Related objects and problemsEdit
- Both triangulation problems are a special case of triangulation (geometry) and a special case of polygon partition.
- Minimum-weight triangulation is a triangulation in which the goal is to minimize the total edge length.
- A point-set triangulation is a polygon triangulation of the convex hull of a set of points. A Delaunay triangulation is another way to create a triangulation based on a set of points.
- The associahedron is a polytope whose vertices correspond to the triangulations of a convex polygon.
- Polygon triangle covering, in which the triangles may overlap.
- Tiling by polygons, where the goal is to cover the entire plane with polygons of pre-specified shapes.
See alsoEdit
ReferencesEdit
External linksEdit
- Demo as Flash swf, A Sweep Line algorithm.
- Song Ho's explanation of the OpenGL GLU tesselator