Find the medial axis of a polygon using C #

Question

I was tasked with figuring out how to find the centerline of the polygon. My searches made me believe that what I needed was called the Medial Axis. Like this:

alt text http://www.ndl.kiev.ua/downloads/center_line.png

According to what I read, what I need can be obtained using the algorithm for constructing a 2D 2D diagram for segments.

I found the C # version for Voronoi algorithm on codeplex (FortuneVoronoi), and after applying my polygon to it, I get the following:

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

Green is the original polygon. Orange is the top of Voronoi, and black is the edge of the raven.

I can see the tasks that I need at these peaks, but I'm not sure about the next step, which requires filtering everything that I do not need.

I would appreciate any help you can offer.

Answer 1

One simple solution would be suggested in the comments:

• Build the Delaunay triangulation of the vertices of the polygon.
• Define Voronoi vertices inside the polygon (see http://en.wikipedia.org/wiki/Point_in_polygon )
• Print the edges of Voronoi, connecting the two internal peaks of Voronoi.

If you have huge data, intersections can be quite expensive.

Then you can take a similar approach, for example in question , and this solution might work for you as well. How will I do it:

• Build the Delaunay triangulation of the vertices of the polygon.
• Insert the middle of each edge of the polygon that is not covered by the delaunay edge. Do this recursively until all edges of the polygon are covered by Delaunay edges.
• Mark all the Delaunay edges that match the edge of the polygon.
• Remove the medial axis using steps 3.-5. in this decision

PS. Please note that both solutions give some approximation of the medial axis, calculating it for sure is much more expensive, but as a teaser ... you can get such results for black input points:

Answer 2

A similar design is a straight skeleton that can be created by compressing the polygon into itself and tracking the vertices as it approaches the center.This can be a little easier to build, although this is not quite the same curve as the medial axis.

Answer 3

Wow. I am going to go on a limb here and assume that maybe the algorithm is confused inside and outside the polygon. When you define the edges and vertices of your original polygon, you need to make sure that they are defined in such a way that “inside” is always used using something like the “right-right” rule. Just looking at the polygon in the lower right corner, it looks like the edge of your polygon actually intersects itself. Maybe the algorithm sees this section, while others see it as “inside out”. Same thing in the bottom left.

What my inside feels is that the algorithm does not seem to be able to determine which direction is inside and what is outside.

I think a naive approach would be to filter out all Voroni “nodes” that are outside the polygon, however I don't think it will look like. We’ll take a closer look at the diagram, it looks like each node has 3 edges that connect it to other nodes. Perhaps you can filter out nodes where any of the three edges is connected to nodes outside the polygon. Will this work?