Medial axis of a shape provides a copmpact representation of its features and their connectivity. We propose to approximate the medial axis directly from the Voronoi diagram of a set of sample points.
1. Our approach computes a subcomplex from the Voronoi diagram that lies close to the medial axis and converges to it as sampling density approaches infinity.
2. Our algorithm uses two filter conditions to select the Voronoi facets from the Voronoi diagram. Unlike previous approaches, these two criteria are scale and density independent.
|
|
|
|
|
|
|
|
<
Output of algorithm >
|
|
|
Medial axis of Fandisk
Medial axis of Foot
|
|
|
|
|
|
|
|
|
T. K. Dey and W. Zhao. Approximate medial axis as a voronoi subcomplex, Proc. 7th ACM Sympos. Solid Modeling and Applications (2002), 356--366.
T. K. Dey and W. Zhao. Approximating the medial axis from the Voronoi diagram with a convergence guarantee. Euoropean Symposium on Algorithms (ESA 2002). Extended version to appear in Algorithmica.