Polygon Triangulation

"Geometry is the science of correct reasoning on incorrect figures."

George Polya

Godfried T. Toussaint, "Slicing an ear using prune and search," Pattern Recognition Letters, vol. 14, September 1993, pp. 719-722. (with H. ElGindy, and H. Everett)

compressed PostScript file ear.ps. gz

Godfried T. Toussaint, "Efficient triangulation of simple polygons," The Visual Computer, vol. 7, 1991, pp. 280-295.

compressed PostScript file triangulation.ps. gz

Godfried T. Toussaint, "The Graham scan triangulates simple polygons," Pattern Recognition Letters, vol. 11, November1990, pp. 713-716. (with X. Kong and H. Everett)

compressed PostScript file tri.scan.ps. gz

Ear-Cutting tutorial by Ian Garton. Play with an interactive Java applet to triangulate, either the interior of a polygon by ear-cutting or the outside of a polygon by mouth-closing!

See also Martin Held's page on practical implementations of polygon triangulation algorithms. Martin has written a nice paper describing an empirical comparison of some of the algorithms described above with other variants.

Research Interests Homepage