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

Home | Bookmarks | Papers | Blog |