Demo For Triangulating Simple Polygon

Instruction for demo operation

1. left-click on working area for point input
2. right-click on working area to finish input
3. click button for processing:
Reset-- clear everything and start over
StartOver-- only clear result and process current polygon again
Check monotonicity -- finding monotonic direction
Make monotonic pieces -- subdivide the non-monotonic polygon
Triangulate-- for triangulating the polygon
Checkbox-- stop 0.5 second after each step

Note: the angle appearing in TextArea is of the sweeping line respective to horizontal direction

Introduction to alogrithm

This demo is to show triangulation in the way that make monotonic pieces in O(n log n) first and then triangulate each monotonic piece in O(n).
The alogrithm in the demo includes four steps:
a) check if the valid input polygon is monotonic, if yes, find the monotonic direction, O(n)
from163-chapter04.pdf
b) if not monotonic, make it into monotonic pieces, O(n log n)
from notes by David Mount
c) extract each monotonic subpolygon, O(n)
d) triangulate the monotonic polygon, O(n)
from notes by David Mount

Monotonicity

In geometry, a polygon P in the plane is called monotone with respect to a straight line L, if every line orthogonal to L intersects P at most twice. Notice that the two edges come from different vertices except the two extreme vertices. Monotonicity make triangulation easier. If we know the monotonic direction, we can triangulate it along the direction in O(n). There is a way detect all monotonic directions in O(n). This demo follows this way.

For simple polygon, if we walk along the edges exactly once, we will turn exact 360 degree. And each vertex contributes a positive or negative degree. If we have a line sweeping through the polygon in that degree or the opposite of that degree, we will intersect the two edges incident to the vertex. We could make the two vertex as two extreme vertices.

However, If the polygon have more than one vertex overlapping on the same degree range, we will intersect two edges from a same vertex more than once. That means there is nowhere we can sweep through only intersecting one edge of any vertex except the two extreme vertices.

Thus if we happen to find two vertices cover opposite angle range and no other vertex covers same range, we get a monotonic direction by labeling the two vertices as extreme vertice. The demo is doing this way.

We walk along each edge of polygon in ccw or cw direction starting from arbitrary vertex until we reach the vertex again. During the process, three data structures are maintained to remembering current status:

a) a variable for current degree respect to the edge we start off
b) a interval for range we have reached
c) a deque for intervals only covered once

Whenever we turn a degree at a vertex, we have to update those three data. Updating a) and b) will cost constant time for each vertex. Updating the deque could cost O(n) for each vertex, but totally maintaining will cost O(n) for all the vertices. And finally there will be at most n intervals in the deque.

Final step, move intervals less than -180 degree to an auxiliary stack, popping intervals to see if they cover some opposite range. Check all interval pairs will cost O(n).

Make Monotonic Pieces

The demo follows the alogrithm from note by David Mount.
When a line sweep through a non monotone polygon, it always intersect two edges incident from same vertex somewhere. We categorize these vertex into five types and treat them in three ways:

a) start vertex and end vertex
b) merge vertex and split vertex
c) regular vertex

For a) we keep it as is and will have them as the two extreme vertices of sub polygons. For b) we will insert an edge between them to other vertices(may be merge vertex, split vertex or end vertex), so that the two edges from same vertices belongs to different subpolygons. For c) it only work as anchor to these diagonals.

After inserting these egdes (diagonals of original polygon), the sweep line only intersect on edge of a vertex of a sub polygon except the two extreme vertices.

Usually we sweep along vertical line or horizontal line. In this demo, we sweep along x-coordinate of vertices from small to large no matter it belongs to upper hull or lower hull. During sweeping, we maitain two data structure:

a) an ordered array of vertices according to x coordinate
b) a balanced tree, in the demo it is black red tree from java collection

The array a) tells us which is next vertex to visit. The BR tree remembers edges intersected on our sweep line and the most recently visited vertex (we could call it helper) immediately above the edge.
The basic idea is to sweep through each vertex in order, on each vertex the alogrithm do three actions:

a) whether insert an diagonal from itself to the helper of the edge immediately below it
b) update the helper to itself
c) update the edge incident to it to the BR tree (may delete, insert or replace)

Extract Monotonic Sub-polygons

After finished the above step, we got a graph and each empty loop is a monotonic polygon. We need identify them and triangulate it.
For each original edge, we think of it as one-way. In this demo, we use ccw direction. For each diagonal inserted, we think of it two-way.

Starting from any vertices, proceed in ccw direction, choose the diagonal or original egde which turns largest degree. We will reach back our starting vertex finally with a empty sub polygon. Therefore we have lots of way to identify each subpolygon.

In this demo, we scan through the sorted array in last step again,
for start vertex extract all sub polygons with the as its leftmost extreme vertex
for "merge vertex" and "regular vertex", if there are some edges or diagonals unvisited, proceed along that edge or diagonal identify the missing sub polygon

This is equivalent to traversing a graph, therefore cost O(edges). Notice there only two edges for each vertex and at most O(n) diagonals totally. Thus it cost O(n).

Triangulate Monotonic Polygon

The demo follows the algorithm in note by David Mount.
The basic idea is scan through all vertex along monotonic direction, connect the current vertex to previous vertices it can see. And after ignoring all connected vertices, the remainning vertices will form another monotone sub polygon to work on . During scanning, we maintain two data structures:

a) a sorted list of vertices of polygon according to x coodinates
b) a stack accommodates all vertices accumulated from previous step which are not connected.

The stack is for temporarily store vertices cannot been seen from previously processed vertices. We keep checking the stack top one or two to see if there is some chance some accumulated vertices can be seen.

Since each vertex will be pushed and poped only once and sometimes peeked O(n). However the total times of peeking all vertices on the stack will be O(n). Therefore it cost O(n).