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.

Solution 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:

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

Comments

[Eric Lippert]

Indeed. The generated voronoi set is defined both inside and outside the polygon. (For that matter, the voronoi set algorithm does not require that the generating set be a polygon, or even be a continuous connected set.) The original poster is only interested in the boundaries of the voronoi set regions such that those boundaries are inside the poly. So build an algorithm that filters out voronoi set boundaries that are not inside the poly. Determining whether a given point is inside a poly is not very hard.