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

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_{1} there are two such edges, for vertex v_{2} there is only one such edge,
and for vertex v_{3} 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).

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

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_{1} and n_{2} respectively. Then we have
n_{1} + n_{2} = 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_{1} + n_{2} = n + 2
=> n_{1} + n_{2} -2 = n => n_{1} - 3 +
n_{2} - 3 + 1 = n - 3. Therefore, altogether we have (n_{1} - 3) + (n_{2} - 3) + 1 = n - 3
diagonals. Note that +1 represents d. And we have (n_{1 }- 2) + (n_{2
}- 2) = n - 2 triangles.

**Triangulation Strategy**

The overall triangulation process can be sketched as follows:

- Partition simple polygon P into monotone polygons.
- Triangulate each monotone polygon.

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

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*_{1} and a trapezoid
at the right-hand side of notch *r*_{2}. 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*_{2}, 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.

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
WHILEV is not emptyDO

- /* Extract the next vertex from V */
- p = MIN(V)
IF(p is opposite to points in L)THEN

WHILE|L| > 1DO

- 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

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*).

*N*ow, lets look again the overall process of triangulating a simple polygon
from scratch.

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

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.

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.

[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.