Polygon triangulation: Encyclopedia II - Polygon triangulation - Using monotone polygons

Polygon triangulation - Using monotone polygons

A monotone polygon is one with a boundary that consists of two parts, each of which consists of points that have incrementing coordinates in one dimension. Such a polygon can easily be triangulated in linear time as described by A. Fournier and D.Y. Montuno.

To break up a polygon into monotone polygons, follow these steps:

For each point, check if the vertices are both on the same side of the 'sweep line', a horizontal or vertical line. If they are, check the next sweep line on the other side. Break the polygon on the line between the original point and one of the points on this one.

Note that if you are moving downwards, the points where both of the vertices are below the sweep line are 'split points'. They mark a split in the polygon. From there you have to consider both sides separately.

Adapted from the Wikipedia article "Using monotone polygons", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki