Polygon triangulation: make monotone polygons
decompose a polygon into monotone polygons; then triangulate the monotone polygons
In addition to the recursive algorithm, we can also triangulate a polygon in a two-step algorithm: first, decompose the polygon into monotone polygons; then triangulate the monotone polygons. A polygon is monotone if, when traversing from the uppermost vertex to the lowermost vertex along either the left or right side, one never moves up; that is, while going down, one goes consistently down or level.
The algorithm begins by characterizing the vertices as stop, start, split, merge, or regular vertices. Split (or merge) vertices lie above (or below) their neighbors, and are therefore vertices which make the polygon not monotone. The algorithm proceeds to connect split and merge vertices, thereby making monotone polygons.
Fourteen movies are available: for non-monotone polygons with eight (six movies), sixteen (four movies), 32 (two movies) and 64 (two movies) vertices, respectively. Five of the movies (eight and sixteen vertices, respectively) include pauses to pose questions to the viewer. Remember the guidelines for use of these movies.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
