Find medial axis of a polygon using C#

Question

I've been tasked to figure out how to find the centerline of a polygon. My google searches led me to believe that what I need is called the 'Medial Axis'. Like this:

_{(source: kiev.ua)}

According to what I've read, what I need can be produced by using a 2D Voronoi diagram construction algorithm for segments.

I've found a C# version of the Voronoi algorithm on codeplex (FortuneVoronoi) and after applying my polygon to it, I end up with this:

alt text http://www.carbonatlas.com/geonotes/gaia_voronoi.png

The green is the original polygon. The orange are the Voronoi vertices and the black lines are the voronoi edges.

I can see the makings of what I need in those vertices, but I'm unsure of the next step required to filter out all the stuff I don't need.

I'd appreciate any help you can offer.

Answer 1

One simple solution would be as suggested in the comments:

1. Build the Delaunay triangulation of the polygon vertices.
2. Identify the Voronoi vertices inside the polygon (see http://en.wikipedia.org/wiki/Point_in_polygon)
3. Output the Voronoi edges connecting two interior Voronoi vertices.

If you have huge data the intersections might be quite costly.

Then you could do a similar approach like in the question, and this solution could work for you, as well. The way I would do it:

1. Build the Delaunay triangulation of the polygon vertices.
2. Insert the midpoint of every polygon edge that is not covered by a delaunay edge. Do this recursively until all polygon edges are covered by Delaunay edges.
3. Mark all Delaunay edges which correspond to a polygon edge.
4. Extract the medial axis using steps 3.-5. in this solution

PS. Note that both solutions give some approximation of the medial axis, computing it exactly is much more costly but as a teaser... you can get results like this for the black input sample points:

Answer 2

A similar construct is the Straight skeleton, which can be constructed by shrinking the polygon into itself and tracing the vertices as they approach the center. This may be a little easier to construct, though it's not quite the same curve as the medial axis.