Polygon Partitioning


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:




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 v1 there are two such edges, for vertex v2 there is only one such edge, and for vertex v3 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:

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:





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.



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 n1 and n2 respectively. Then we have n1 + n2 = 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 n1 + n2 = n + 2  =>   n1 + n2 -2 = n  =>   n1 - 3 + n2 - 3 + 1 = n - 3. Therefore, altogether we have (n1 - 3) + (n2 - 3) + 1 = n - 3 diagonals. Note that +1 represents d. And we have (n1 - 2) + (n2 - 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:

Consider the following figure,



Which has a virtual trapezoid at the left-hand side of notch r1 and a trapezoid at the right-hand side of notch r2. 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 r2, 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:

We illustrate this process using following example



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


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





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.



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.



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