EVG-Thin: A Thinning Approximation to the Extended Voronoi Graph

Copyright (C) 2006 - Patrick Beeson (pbeeson at cs.utexas.edu)
This program is released under the GNU General Public License (GPL).

This code implements an extension of the pixel-based "thinning" algorithm that finds skeletons of bitmaps. The classic thinning algorithm is a fast approximation of the Voronoi diagram; however, this software also approximates the Extended Voronoi graph. This code was written to be applied in real-time to occupancy grids (from the mobile robotics literature) where cells are either occupied, free, or unknown, but it should work on bitmap images for other domains.

Relevant Citations


C++ (tested with g++-4.0 under Linux 2.6)



[QR home: http://www.cs.utexas.edu/users/qr]