Polygon Triangulation: Make 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. Click on the Download button at the right to download a zipped file of all movies described on this page. |