Up: Directory of Computational Geometry Software

Medial axis and constrained Delaunay triangulation

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.

The Triangle program computes constrained Delaunay triangulations.

Constarined Delaunay Triangulation

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.

Voronoi diagram for line segments

 Two Fortran programs to compute the Voronoi diagram of line segments, SEGVOR for non-intersecting segments and PLVOR for segments which intersect only at their endpoints.

Documentation and source code available from the Web page.

By Toshiyuki Imai at the University of Tokyo.

Skeletonization

 And now for something completely different - a program that computes the medial axis of a binary image (or a pre-computed contour polygon). C source code. Lots of helpful I/O interfaces. You can get it via the Web page.

By Robert L. Ogniewisz at the Harvard Robotics Lab.

Up: Directory of Computational Geometry Software
[HOME] The Geometry Center Home Page

Comments to: nina@geom.umn.edu
Created: May 31 1995 --- Last modified: Thu Jun 1 14:26:51 1995