Find medial axis of a polygon using C#
c#, computational-geometry, geometry, medial-axis
Solution
One simple solution would be as suggested in the comments:
- Build the Delaunay triangulation of the polygon vertices.
- Identify the Voronoi vertices inside the polygon (see http://en.wikipedia.org/wiki/Point_in_polygon)
- 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:
- Build the Delaunay triangulation of the polygon vertices.
- 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.
- Mark all Delaunay edges which correspond to a polygon edge.
- 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:
Problem
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.