Konvex poligon triangulation
|Top Previous Next|
Ear clipping method
A polygon ear
One way to triangulate a simple polygon is based on the two ears theorem, 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 (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 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.
Using monotone polygons
Breaking a polygon into monotone polygons
A simple polygon may be decomposed into monotone polygons 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 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.