A constrained Delaunay triangulation of a set of line segments (which might form a polygon) is the Delaunay triangulation of the endpoints where the distance between two points is the length of the shortest path between them which doesn't cross a line segment. You get a triangulation in which the input segments are some of the edges. If you take the Voronoi diagram of the line segments themselves (that is, each region in the diagram is the set of points closest to some segment) you get a decomposition whose edges are lines and parabolic arcs. The medial axis of a polygon is the Voronoi diagram of its segments.
A short floating-point program in gcc/g++. If you're using Netscape, hold down the shift key while clicking here to download the shar file.
By Dani Lischinski, at the University of Washington.
Documentation and source code available from the Web page.
By Toshiyuki Imai at the University of Tokyo.
By Robert L. Ogniewisz at the Harvard Robotics Lab.
Comments to: firstname.lastname@example.org
Created: May 31 1995 --- Last modified: Thu Jun 1 14:26:51 1995