**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*

*The Geometry Center Home Page*
Comments to: nina@geom.umn.edu

Created: May 31 1995 ---
Last modified: Thu Jun 1 14:26:51 1995