Polygon Triangulation: Recursive algorithm

The recursive algorithm for triangulating the polygon begins by searching for two vertices on opposite sides ot the polygon, and connecting them with a diagonal. If the diagonal lies totally within the polygon, the polygon has been decomposed into two smaller polygons; if not, a pair of vertices is found whose diagonal does lie totally within the polygon. This procedure is then continued recursively until all smaller polygons are triangles.
This algorithm is used in the "art gallery problem," found elsewhere. Click on the Download button at the right to download a zipped file of all movies described on this page. |