An efficient shape representation scheme using Voronoi skeletons

Abstract

This paper describes an efficient shape representation scheme using Voronoi skeletons. This paper makes the following significant contributions. First a new algorithm for the construction of the Voronoi diagram of a polygon with holes is described. The main features of this algorithm are its robustness in handling the standard degenerate cases (colinearity of more than two points; co-circularity of more than three points), and its ease of implementation. The algorithm has been fully implemented and tested on a variety of test inputs. Second, the Voronoi diagram of a polygon is used to derive accurate and robust skeletons for planar shapes. The shape representation scheme using Voronoi skeletons possesess the important properties of connectivity as well as Euclidean metrics. Redundant skeletal edges are deleted in a pruning step which guarantees that connectivity of the skeleton will be preserved. © 1995.