We present a full pipeline for computing the medial axis transform of an arbitrary 2D shape. The instability of the medial axis transform is overcome by a pruning algorithm guided by a user-defined Hausdorff distance threshold. The stable medial axis transform is then approximated by spline curves in 3D to produce a smooth and compact representation. These spline curves are computed by minimizing the approximation error between the input shape and the shape represented by the medial axis transform. Our results on various 2D shapes suggest that our method is practical and effective, and yields faithful and compact representations of medial axis transforms of 2D shapes.
Among these, the VD based approach stands out due to its theoretical guarantee and efficient computation. As a preprocessing step, we obtain an initial discrete medial axis of a shape using the VD based algorithm. The VD based method assumes that the boundary of an input shape @math is a smooth curve and is sampled by a dense discrete set @math of points (Fig. ), with the sampling density determined by the local feature size @cite_23 in order to capture the boundary topology correctly. The Voronoi diagram of @math is computed and the Voronoi vertices interior to @math are taken to approximate the medial axis of Voronoi diagram (Fig. ), since a point on the Voronoi diagram is also characterized by having at least two closest points among the sample points. @PARASPLIT
@cite_23
2029041800
We give a simple combinatorial algorithm that computes a piecewise-linear approximation of a smooth surface from a finite set of sample points. The algorithm uses Voronoi vertices to remove triangles from the Delaunay triangulation. We prove the algorithm correct by showing that for densely sampled surfaces, where density depends on a local feature size function, the output is topologically valid and convergent (both pointwise and in surface normals) to the original surface. We briefly describe an implementation of the algorithm and show example outputs.