An Approximate Algorithm

We begin the decomposition problem with a monotone polygon. The approximate algorithm sweeps through a monotone polygon in the Y direction from bottom to top, so at particular Y-value there will be unique left and right edges of the polygon.


Data Structures

The data structures
shown above include (1) a stack storing vertices which are inward cusps,(2) a top chain and (3) a bottom chain with all the points having inside angles less than 180. Each vertex is either in the stack, or the top chain, or the bottom chain.

The stack and chains are maintained as doubly linked lists. The top chain and the stack both contain the top element. The bottom chain and the stack share the bottom element in a similar manner.

We process the vertices from bottom to top, so the data structures enclose the area below the current Y-value that has been processed.



When the Y sweep encounters a point, the rules for making connections differs, depending on which chain is involved.

Rules for Top Chain:
First test the angle at the new point,

if angle < 180, then simply append point to top chain (and continue sweep), else
make connections between the new point and the elements of the stack, working backward through the stack, until either:
A. angle at point becomes less than 180 (start a fresh top chain) or
B. angle at stack exceeds 180 (add point to stack) or
C. stack empty (add point to stack).


Rules for Bottom Chain:
On the bottom chain we wish to ensure that a connection from the new point to the second element from the bottom of the stack produces a convex region. This property can be described by saying that the new point can "see" the stack bottom. In other words, the stack bottom is visible from the new point.

1. Resolve visibility problems

If a new point cannot see the stack bottom, connections are made from the previous point on the bottom chain (this point is able to see the stack bottom) until the new point can see the stack bottom (figure A). We need to handle extreme cases in which angle at stack exceeds 180. The previous point can become the bottom of the stack (figure B) or remain on the bottom chain (figure C).

2. Eliminate inward cusps
Test the angle at the point,

if angle < 180, then simply append point to bottom chain (and continue sweep), else
make connections, starting with the bottom of the stack and working upward, until the angle at the new point is less than 180 (figure A). If the stack is exhausted, the old stack top and the new point start a new fresh stack, with the top and bottom chains reversed (figure B).


Rules for the Highest Point:
Connect the highest point with every point on the stack except the top and bottom.



Sort points of a monotone polygon into ascending Y order

For each point in order starting at the bottom do


if this is the first or second point then add the point to the stack


if point adjacent to bottom chain then Resolve visibility problems

if this is the last point then apply rules for the highest point

if point adjacent to stack top

if angle at stack top >180 then push point on stack else apply rules for top chain

else if point adjacent to top chain then apply rules for top chain else Eliminate inward cusps on the bottom chain




This algorithm is a constant-factor approximation. It is fast, O(nlogn), and comes within a constant factor of the best solution.



 A sample run can be found here.