Medial Axis

by Ayelet Shemesh

A Medial Axis is defined as the collection of points within the polygon that are closest to more than one of the edges. It can also be viewed (equivalently) as the points that can be the center of a circle that is entirely within the polygon and touches the polygon in atleast two places.

For example, in a triange the Medial Axis are the bisectors of the angles:

A more complicated polygon would result in a much more interesting Medial Axis. For example:

or:

It's very easy to understand from the examples that the medial axis of a polygon forms a tree-like skeleton, made of lines and parabolas. The usual implementation is (in general) the Voronoi diagram of the edges of the polygon - rather than the vertexes as used in most Voronoi implementations.

The Medial Axis is useful in character recognition, road network detection, in geographic information systems, and other applications. You can read about some of the uses of Medial Axis here.

Some Links that could be usefull to you:

During my search for Medial Axis related material I encountered a lot of sites and stuff that could be helpful to another searcher and they are:

Book.Zip this is a book about the Medial Axis problem. It's in PostScript so you need a program like ghostview to view it. It has pseudo code.
Straight Skeleton is another approach to Medial Axis's problem. Using the shrinking process the authors of this article suggest a very intuitive way to compute a polygon's medial axis. It also can be changed easily to create the "normal" medial axis.
This software is written in C and is able to compute robust Euclidean skeletons from 2-D binary images. It's taken from this site, but was opened and rezipped to be more easily opened.
Although I never found it usefull maybe I just didn't know how to search it correctly - this site is supposed to be a search engine for Computational Geometry related publications and sites.
The nicest site I saw about Medial Axis was this one. It has an applet that implements the medial axis very nicely. It also has a library (GISHUR) to be used in Computational Geometry applets. But it's documented in German only. And btw - it has some bugs in the implementation - a simple triangle doesn't always get a medial axis. Has something to do with orientation. And the shapes can be dragged to intersect themselves, which causes the applet to hang.

This applet computes the Medial Axis of a Polygon. It does it using "brute force" algorithm, meaning that every pixel in the polygon is checked, and if it conforms to the conditions - it's added to the Medial Axis. A point is decided as "within" a polygon according to the simple even-odd (or alternating) rule.

Note that also usually a Medial Axis is defined only for simple polygons in this applet you can make a self intersected polygon, and see the nice results. for example:

And here's the applet itself

Enjoy!

The source code of this applet is available in PointList.java and Medial.java.