8

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:

alt text
(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.

Glorfindel
  • 21,988
  • 13
  • 81
  • 109
mdm20
  • 4,475
  • 2
  • 22
  • 24

3 Answers3

14

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:

medial axis

Community
  • 1
  • 1
balint.miklos
  • 1,867
  • 1
  • 19
  • 23
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.

SingleNegationElimination
  • 151,563
  • 33
  • 264
  • 304
0

Wow. I'm going to go out on a limb here and suggest that maybe the algorithm is confused about the inside vs. the outside of the polygon. When you define the edges and vertices of your original polygon, you have to make sure they're defined in such a way that "inside" is always found using something like the "right hand rule". Just looking at the polygon in the bottom right corner, it looks like the edge of your polygon actually crosses itself. Maybe the algorithm is seeing that section, and others, as "inside out". The same in the bottom left.

That's my gut feeling, that the algorithm doesn't seem to be able to determine what 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 that will look. Taking a closer look at your 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 3 edges are connected to nodes outside the polygon. Would that work?

Scott Whitlock
  • 13,739
  • 7
  • 65
  • 114
  • 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. – Eric Lippert Jul 01 '09 at 16:44