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.
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
begin
if this is the first or second point then add the point to the stack
else
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
End
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.