The key strategy for solving problems on simple polygons is to decompose simple polygons in simpler polygons.

Trapezoidalization

A trapezoid is a quadrilateral with at least two parallel edges. Note that a triangle is a degenerated trapezoid with a zero-length edge.
The trapezoidalization algorithm relies on the sweep line technique and it has three major steps:

• Sort the vertices of polygon P with respect to their x-coordinate.
• The a vertical line, l, scans the sorted vertices.
• For each vertex v, compute the maximal vertical segment on l, interval to P and containing v see the figure below.

This implies looking for the nearest edge of P, above v or below v, with the constraint that a vertical segment (called the visibility segment) drawn from v to such an edge lies entirely within P. For example, in the above figure, for vertex v₁ there are two such edges, for vertex v₂ there is only one such edge, and for vertex v₃ there is no such edge.

The visibility segments define the trapezoidalization. The polygon is decomposed into trapezoids with vertical parallel edges (visibility segments)
It remains to describe how we can compute visibility segments quickly. We can use the rectangle_intersection algorithm with following changes:

• The event list E (where the sweep line stops) is the list of vertices sorted with respect of their  x-coordinate.
• The sweep line active list L must contain the list of edges of P currently intersected by L, ordered with respect to their y-coordinate.

Hence, each segment should be inserted in sweep-line active list L when its leftmost vertex is encountered in the event list E. Similarly, each segment should be removed from L when its rightmost vertex is encountered in E. At each event, a new vertex, v, is introduced. Incident edges are either inserted or removed from data structure, L, and L is searched for the edges above and below v.

Whenever a nearest edge e above (below) v has been found in L, the visibility segment from v to e defines a vertical edge of a trapezoid. The procedure of extraction of trapezoid from polygon P as follows:

• The visibility segment from v to the intersection point with e, say i, is the first vertical edge of the trapezoid. Then e from i to its left point is the second edge. The second vertical edge of the trapezoid is the visibility segment of the previous event, and so on ( see figure).

Analysis

With an appropriate tree-like structure for L, the edge search can be carried out in O(logn) time. The entire scan (search process) requires O(n log n). The overall complexity of the algorithm is then O(n log n).

Triangulation of Simple Polygon

The process of triangulation of a polygon P consists of finding diagonals within polygon P. Note that a diagonal is a segment between two vertices of polygon P whose interior does not intersect the boundary of P. That is to say, both vertices are visible from each other. The triangulation is not deterministic, but it is certainly possible to show that every triangulation of a polygon P of n vertices has n-3 diagonals and results in n-2 triangles. Following inductive proof is taken from O'Rourke.

Proof   

Both claims are trivially true for triangle i.e., n=3. Let n>=4. Partition the polygon, P,  into two sub polygons P1 and P2 such that P=P1UP2. Let the diagonal be d = ab as shown in the figure below. Suppose number of vertices in P1 and P2 are n₁ and n₂ respectively. Then we have n₁ + n₂ = n+2, since we are counting common vertices a and b twice, first when we are counting the vertices of P1 and then when we are counting the vertices of P2. Applying the induction hypothesis to the sub polygons: Since n₁ + n₂ = n + 2  =>   n₁ + n₂ -2 = n  =>   n₁ - 3 + n₂ - 3 + 1 = n - 3. Therefore, altogether we have (n₁ - 3) + (n₂ - 3) + 1 = n - 3 diagonals. Note that +1 represents d. And we have (n₁ - 2) + (n₂ - 2) = n - 2 triangles.

Triangulation Strategy

The overall triangulation process can be sketched as follows:

1. Partition simple polygon P into monotone polygons.
2. Triangulate each monotone polygon.

Therefore, a merging of the monotone chains gives a fully sorted list of P vertices in linear time.

I. Partitioning of simple polygon into monotone polygons

In this next section we will show that monotone polygons can be linearly triangulated so partitioning a simple polygon into monotone polygon is the key to efficient triangulation algorithms. Partitioning a simple polygons into monotone components is quite similar to the trapezoidalization process. The outline of the process as follows:

• Partition the polygon in monotone components at the “return” vertices.
  • These return vertices are notches for which both incident edges are on the same side of the vertical line that passes through their common vertex.
• Apply a “vertical” trapezoidalization (with no output of trapezoids).

Consider the following figure,

Which has a virtual trapezoid at the left-hand side of notch r₁ and a trapezoid at the right-hand side of notch r₂. We obtained the monotone components by creating diagonals in these trapezoids. We extracted from the polygon the one monotonic component, A, by drawing a diagonal between v and r. Then by drawing a diagonal between the second “return” vertex r₂, and vertex w, we split the rest of the polygon into two monotone components B and C.
The algorithm for monotone partitioning of the simple polygon takes O(nlogn) time.

II. Triangulating monotone Polygon

The triangulating algorithm that embraces "as soon as possible" or "greedy" strategy works as follows:

• Scan in order the sorted vertices of simple polygon P.
• Maintain a sweepline active list L of the points already scanned but triangle has not yet created.
• Eliminate points within data structure, L.
  • That is, delete points from the list L when a triangle has been created.

We illustrate this process using following example

We summarize all likely situations to occur in the first three steps. They are as follows:

• The first three points are on the same chain. The angle abc is convex, which allows points a and c to be connected with a diagonal. The point b is removed from active list L, which is now (a, c)
• Now add point d. The angle acd is reflex. Hence, triangle (a, c, d) is outside the polygon. In this case nothing can done. So, we go ahead and add point d in the active list L. The same holds for point e. The data structure, L, becomes (a, c, d, e).
• Add point f. Note that
  • Point f lies on a different chain than those points already in the L, and
  • The points in L form a reflex chain.
  • Therefore, point f can be successively connected to points a, c, and d. We get three triangles. Remove points a, c, and d from L which reduces L to (f, e).

The important point to note here is that the algorithm creates the diagonals without an explicit test for visibility between the two points.
The pseudo-code follows

Algorithm Monotone_Triangulation
Input: Monotone polygon P
Output: Set of triangles

• Sort the n vertices belonging to polygon P with respect to x-coordinate and store them in V.
• Initialize sweep-line active list L
  • L = a list with the first two points of V
• WHILE V is not empty DO
  • /* Extract the next vertex from V */
  • p = MIN(V)
  • IF (p is opposite to points in L) THEN
    • WHILE |L| > 1 DO
      • Output Triangle {First(L), Second(L),p}
      • REMOVE (FIRST(L))
    • Add p to L
  • ELSE
    • WHILE (Angle{Last(L), Previous (Last(L)), p}is convex .AND. |L| > 1) DO
      • Output Triangle {last(L), Previous (last), p}
      • REMOVE last (L)
    • /*  The angle is reflex or cardinality of L is 1 */
    • Add p to L

Analysis

Sorting the vertices of monotone polygon P is carried out in O(n) time. Note that this is linear due to the monotonic nature of Polygon. In the last step, triangles are created during a simple search of the sorted list of vertices. Therefore, the algorithm solves the monotone polygon triangulation problem in Θ(n).

Now, lets look again the overall process of triangulating a simple polygon from scratch.

• Partition simple polygon into monotone polygons.
• Triangulate each monotone.

Overall Complexity of Triangulation of Simple Polygon

The monotone partitioning algorithm runs O(n log(n)) time and the subsequent triangulation of monotone polygons is processed in linear time.
Therefore, the simple polygon triangulation is carried out in O(n log(n)) + O(n) = O(n log(n)).
 

This is not optimal because a linear algorithm exists.

Bibliographic Notes

The simple triangulation algorithm was proposed in [1]. The optimality of the algorithm has been an open issue for a long time because it was not proved that O(n log(n)) is a lower bound. Actually, it is not, as shown by the O(n loglog(n)) algorithm proposed by [2]. The problem was then conjectured to be linear. One way to prove it was to find a Θ(n) algorithm. This was done in [3]. However, although this is an important theoretical achievement, this optimal algorithm is hardly implementable.

Reference

[1] M. R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan. "Triangulating a Simple Polygon.", Information Processing Letter, 7(4): 175-180, 1978.

[2] R. E. Tarjan and C. J. van Wyk, "An O(n loglog(n)) Time Algorithm for Triangulating a Simple Polygon." SIAM Journal of Computing, 17(1):143-178, 1988.

[3] B. Chazelle, "Triangulating a Simple Polygon in Linear Time.", Discrete and Computational Geometry, 6:485-524,1991.