Polygon triangulation
Encyclopedia
In computational geometry
, polygon triangulation is the decomposition of a polygonal area (simple polygon
) P into a set of triangles, 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 graph
s. When there are no holes or added points, triangulations form maximal outerplanar graphs
.
is trivial to triangulate in linear time, by adding edges from one vertex to all other vertices.
A monotone polygon
can easily be triangulated in linear time with either the algorithm of A. Fournier
and D.Y. Montuno, or the algorithm of Godfried Toussaint
.
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). 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(n2) 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
.
A simple polygon may be decomposed into monotone polygon
s as follows.
For each point, check if the neighboring points are both on the same side of the 'sweep line', a horizontal or vertical line. 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.
can be triangulated faster than O(n log n) time. In 1990 David G. Kirkpatrick
, Maria M. Klawe
, Robert E. Tarjan
discovered an O(n log log n) algorithm for triangulation. Simple randomised methods such as Seidel's or Clarkson et al.s, have O(n log* n) behaviour which, in practice, are indistinguishable from O(n).
Bernard Chazelle
showed in 1991 that any simple polygon can be triangulated in linear time, though the proposed algorithm is very complex.
Finally, in 1998 the first practical O(n) average time algorithms were discovered and published by Alexey V. Skvortsov and Yuri L. Kostyuk. The fastest of these algorithms employs dynamic caching for triangles.
The time complexity
of triangulation of a polygon with holes has an Ω(n log n) lower bound.
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
, polygon triangulation is the decomposition of a polygonal area (simple polygon
Simple polygon
In geometry, a simple polygon is a closed polygonal chain of line segments in the plane which do not have points in common other than the common vertices of pairs of consecutive segments....
) P into a set of triangles, 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 graph
Planar straight-line graph
Planar straight-line graph is a term used in computational geometry for an embedding of a planar graph in the plane such that its edges are mapped into straight line segments...
s. When there are no holes or added points, triangulations form maximal outerplanar graphs
Outerplanar graph
In graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges...
.
Polygon triangulation without extra vertices
Over time a number of algorithms have been proposed to triangulate a polygon.Special cases
A convex polygonConvex polygon
In geometry, a polygon can be either convex or concave .- Convex polygons :A convex polygon is a simple polygon whose interior is a convex set...
is trivial to triangulate in linear time, by adding edges from one vertex to all other vertices.
A monotone polygon
Monotone polygon
In geometry, a polygon P in the plane is called monotone with respect to a straight line L, if every line orthogonal to L intersects P at most twice....
can easily be triangulated in linear time with either the algorithm of A. Fournier
Alain Fournier
Alain Fournier was a computer graphics researcher.- Biography :Alain Fournier was born on November 5, 1943 in Lyon, France. He was married twice, first to Beverly Bickle and later to Adrienne Drobnies, with whom he had one daughter, Ariel.Fournier's early training was in chemistry, culminating in...
and D.Y. Montuno, or the algorithm of Godfried Toussaint
Godfried Toussaint
Godfried T. Toussaint is a Research Professor of Computer Science at New York University Abu Dhabi in Abu Dhabi, United Arab Emirates. He is an expert on various aspects of computational geometry, discrete geometry, and their applications: pattern recognition , motion planning, visualization ,...
.
Ear clipping method
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(n2) 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
Godfried Toussaint
Godfried T. Toussaint is a Research Professor of Computer Science at New York University Abu Dhabi in Abu Dhabi, United Arab Emirates. He is an expert on various aspects of computational geometry, discrete geometry, and their applications: pattern recognition , motion planning, visualization ,...
.
Using monotone polygons
Monotone polygon
In geometry, a polygon P in the plane is called monotone with respect to a straight line L, if every line orthogonal to L intersects P at most twice....
s as follows.
For each point, check if the neighboring points are both on the same side of the 'sweep line', a horizontal or vertical line. 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 polygonSimple polygon
In geometry, a simple polygon is a closed polygonal chain of line segments in the plane which do not have points in common other than the common vertices of pairs of consecutive segments....
can be triangulated faster than O(n log n) time. In 1990 David G. Kirkpatrick
David G. Kirkpatrick
David Galer Kirkpatrick is a professor of computer science at the University of British Columbia. He is known for the Kirkpatrick–Seidel algorithm and his work on Polygon triangulation, and for co-inventing α-shapes and the β-skeleton...
, Maria M. Klawe
Maria Klawe
Maria M. Klawe is a computer scientist and the fifth president of Harvey Mudd College . Although born in Toronto in 1951, she became a naturalized U.S. citizen in 2009. She was previously Dean of the School of Engineering and Applied Science at Princeton University.-Biography:Klawe was born in...
, Robert E. Tarjan
Robert Tarjan
Robert Endre Tarjan is a renowned American computer scientist. He is the discoverer of several important graph algorithms, including Tarjan's off-line least common ancestors algorithm, and co-inventor of both splay trees and Fibonacci heaps. Tarjan is currently the James S...
discovered an O(n log log n) algorithm for triangulation. Simple randomised methods such as Seidel's or Clarkson et al.s, have O(n log* n) behaviour which, in practice, are indistinguishable from O(n).
Bernard Chazelle
Bernard Chazelle
Bernard Chazelle is the Eugene Higgins Professor of Computer Science at Princeton University. Much of his work is in computational geometry, where he has found many of the best-known algorithms, such as linear-time triangulation of a simple polygon, as well as many useful complexity results, such...
showed in 1991 that any simple polygon can be triangulated in linear time, though the proposed algorithm is very complex.
Finally, in 1998 the first practical O(n) average time algorithms were discovered and published by Alexey V. Skvortsov and Yuri L. Kostyuk. The fastest of these algorithms employs dynamic caching for triangles.
The time complexity
Time complexity
In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and...
of triangulation of a polygon with holes has an Ω(n log n) lower bound.
See also
- Catalan numberCatalan numberIn combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involvingrecursively defined objects...
- Point set triangulationPoint set triangulationA triangulation of a set of points P in the plane is a triangulation of the convex hull of P, with all points from P being among the vertices of the triangulation. Triangulations are special cases of planar straight-line graphs....
- Delaunay triangulationDelaunay triangulationIn mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...
- Minimum-weight triangulation, for a point set and for a simple polygon
External links
- Demo as Flash swf, A Sweep Line algorithm.