Click here in counter-clock-wise order to add points.
Press "Backspace" to delete points.
Algorithm MAKEMONOTONE(P)
Input. A simple polygon P stored in a doubly-connected edge list D.
Output. A partitioning of P into monotone subpolygons, stored in D.
1. Construct a priority queue Q on the vertices of P, using their y-coordinates as priority.
If two points have the same y-coordinate, the one with smaller x-coordinate has higher
priority.
2. Initialize an empty binary search tree T.
3. while Q is not empty
4. do Remove the vertex vi with the highest priority from Q.
5. Call the appropriate procedure to handle the vertex, depending on its
type.
Algorithm TRIANGULATEMONOTONEPOLYGON(P)
Input. A strictly y-monotone polygon P stored in a doubly-connected edge list D.
Output. A triangulation of P stored in the doubly-connected edge list D.
1. Merge the vertices on the left chain and the vertices on the right chain of P into one
sequence, sorted on decreasing y-coordinate. If two vertices have the same y-coordinate,
then the leftmost one comes first. Let u1, ..., un denote the sorted sequence.
2. Initialize an empty stack S, and push u1 and u2 onto it.
3. for j <- 3 to n-1
4. do if uj and the vertex on top of S are on different chains
5. then Pop all vertices from S.
6. Insert into D a diagonal from uj to each popped vertex, except the last one.
7. Push uj-1 and uj onto S.
8. else Pop one vertex from S.
9. Pop the other vertices from S as long as the diagonals from uj to them are
inside P. Insert these diagonals into D. Push the last vertex that has been
popped back onto S.
10. Push uj onto S.
11. Add diagonals from un to all stack vertices except the first and the last one.
HANDLESTARTVERTEX(vi)
1. Insert ei in T and set helper(ei) to vi.
HANDLEENDVERTEX(vi)
1. if helper(ei-1) is a merge vertex
2. then Insert the diagonal connecting vi to helper(ei-1) in D.
3. Delete ei-1 from T.
HANDLESPLITVERTEX(vi)
1. Search in T to find the edge e j directly left of vi.
2. Insert the diagonal connecting vi to helper(e j) in D.
3. helper(ej) <- vi
4. Insert ei in T and set helper(ei) to vi.
HANDLEMERGEVERTEX(vi)
1. if helper(ei-1) is a merge vertex
2. then Insert the diagonal connecting vi to helper(ei-1) in D.
3. Delete ei-1 from T.
4. Search in T to find the edge ej directly left of vi.
5. if helper(ej) is a merge vertex
6. then Insert the diagonal connecting vi to helper(ej) in D.
7. helper(ej) <- vi
HANDLEREGULARVERTEX(vi)
1. if the interior of P lies to the right of vi
2. then if helper(ei-1) is a merge vertex
3. then Insert the diagonal connecting vi to helper(ei-1) in D.
4. Delete ei-1 from T.
5. Insert ei in T and set helper(ei) to vi.
6. else Search in T to find the edge ej directly left of vi.
7. if helper(ej) is a merge vertex
8. then Insert the diagonal connecting vi to helper(ej) in D.