The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.6.10 Medial-Axis Transformation

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: A polygon or polyhedron P.

Problem: What is the set of points within P which have more than one closest point on the boundary of P?

Excerpt from The Algorithm Design Manual: The medial-axis transformation is useful in thinning a polygon, or, as is sometimes said, finding its skeleton. The goal is to extract a simple, robust representation of the shape of the polygon. As can be seen from the figures above, the thinned versions of the letters capture the essence of the shape of an `A' and a `B', and would be relatively unaffected by changing the thickness of strokes or by adding font-dependent flourishes such as serifs.

The medial-axis transformation of a polygon is always a tree, making it fairly easy to use dynamic programming to measure the ``edit distance'' between the skeleton of a known model and the skeleton of an unknown object. Whenever the two skeletons are close enough, we can classify the unknown object as an instance of our model. This technique has proven useful in computer vision and in optical character recognition. The skeleton of a polygon with holes (like the `A' and `B') is not a tree, but an embedded planar graph, but it remains easy to work with.


Implementations

  • CGAL: The Computational Geometry Algorithms Library (C++) (rating 8)
  • VRONI: Voronoi Diagrams of Points, Segments and Arcs in 2D (C) (rating 8)
  • Cocone Software for surface reconstruction and medial axis (Application) (rating 7)
  • Power Crust, Unions of Balls, and the Medial Axis Transform (C++,C) (rating 7)
  • Skeletonization Software () (rating 5)

  • Recommended Books

    Computational Geometry in C by Joseph O'Rourke Discrete Voronoi Skeletons by R. Ogniewicz Algorithms for Graphics and Image Processing by T. Pavlidis
    Pattern Classification and Scene Analysis by R. Duda and P. Hart

    Related Problems


      
    Minkowski Sum
      
    Shape Similarity
      
    Voronoi Diagrams



    This page last modified on 2008-07-10 .
    www.algorist.com