Simple Polygon Triangulation

From CGAFaq

Triangulation of a polygon partitions its interior into triangles with disjoint interiors. Usually one restricts corners of the triangles to coincide with vertices of the polygon, in which case every polygon of n vertices can be triangulated, and all triangulations contain n-2 triangles, employing n-3 "diagonals" (chords between vertices that otherwise do not touch the boundary of the polygon).

Triangulations can be constructed by a variety of algorithms, ranging from a naive search for noncrossing diagonals, which is O(n⁴), to "ear" clipping, which is O(n²) and relatively straightforward to implement [O'Rourke (C), Chap. 1], to partitioning into monotone polygons, which leads to O(n log n) time complexity [O'Rourke (C), Chap. 2; Overmars, Chap. 3], to several randomized algorithms; by Clarkson et al., by Seidel, and by Devillers, which lead to O(n log* n) complexity; to Chazelle's linear-time algorithm, which has yet to be implemented.

There is a tradeoff between code complexity and time complexity. Fortunately, several of the algorithms have been implemented and are available:

Ear-clipping:

http://cs.smith.edu/~orourke/books/compgeom.html

ftp://ftp.cis.uab.edu/pub/sloan/Software/triangulation/src/

Seidel's Algorithm:

http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html

ftp://ftp.cs.unc.edu/pub/users/narkhede/triangulation.tar.gz

http://reality.sgi.com/atul/code/chapter.html

See also the collection of triangulation links at

http://www.geom.umn.edu/software/cglist/

References:

• [O'Rourke (C)]
• [Overmars]
• [Gems V]
• Clarkson, K., Tarjan, R., and VanWyk, C. A fast Las Vegas algorithm for triangulating a simple polygon. Discrete and Computational Geometry, 4(1):423‚Äì432, 1989.
• Clarkson, K., Cole, R., Tarjan, R. Randomized parallel algorithms for trapezoidal diagrams. Int. J. Comp. Geom. Appl., 117-133, 1992.

http://cm.bell-labs.com/cm/cs/who/clarkson/tri.html

• Seidel, R. (1991), A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, Comput. Geom. Theory Appl. 1, 51-64.
• Devillers, O. (1992), Randomization yields simple O(n log* n) algorithms for difficult Omega(n) problems, Internat. J. Comput. Geom. Appl. 2(1), 97-111.
• Chazelle, B. (1991), Triangulating a simple polygon in linear time, Discrete Comput. Geom. 6, 485-524.
• Held, M. (1998) "FIST: Fast Industrial-Strength Triangulation".

http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html