Get Polygon Triangulation essential facts below. View Videos or join the Polygon Triangulation discussion. Add Polygon Triangulation to your Like2do.com topic list for future reference or share this resource on social media.
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. 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 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.
Monotone Polygon Triangulation
Breaking a polygon into monotone polygons
A polygonal chain C is called monotone with respect to a straight line L, if every line orthogonal to L intersects C at most once. We call these chains monotone chains. A polygon P is monotone with respect to a line L if its boundary can be split into two chains, each being monotone with respect to L. We call these polygons monotone polygons. We say that a polygon P is horizontally monotone (or x-monotone) if P is monotone w.r.t. x-axis.
We can triangulate a monotone polygon in time, where is the number of vertices of the monotone polygon. The algorithm is described in section 3.3 of the book Computational Geometry: Algorithms and Applications (3rd edition), by Berg et al.
Decomposition of a Simple Polygon into Monotone Pieces
If a simple polygon is not monotone, it can be made monotone, in time, using a sweep-line approach. To see it, read section 3.2 of the book Computational Geometry: Algorithms and Applications (3rd edition) by Berg et al.
Dual graph of a triangulation
A useful graph that is often associated with a triangulation of a polygon P is the dual graph. Given a triangulation TP of P, one defines the graph G(TP) as the graph whose vertex set are the triangles of TP, two vertices (triangles) being adjacent if and only if they share a diagonal. It is easy to observe that G(TP) is a tree with maximum degree 3.
Bernard Chazelle showed in 1991 that any simple polygon can be triangulated in linear time, though the proposed algorithm is very complex. A simpler randomized algorithm with linear expected time is also known.
Seidel's decomposition algorithm and Chazelle's triangulation method are discussed in detail in Li & Klette (2011).