Balint Miklos
Mark Pauly
ABSTRACT
We illustrate a simple algorithm for approximating the medial axis of a 2D shape with smooth boundary from a sample of this boundary. The algorithm is compared to a more general approximation method that builds on the same idea, namely, to approximate the shape by a union of balls. While not as general, our algorithm is simpler, faster and numerically more stable. Both algorithms are visualized using the Mesecina tool, which is also described.
- Computational Geometry Algorithms Library. http://www.cgal.org/.Google Scholar
- CORE library. http://cs.nyu.edu/exact/core/.Google Scholar
- Nina Amenta, Marshall Bern, and David Eppstein. The crust and the beta--skeleton: combinatorial curve reconstruction. Graph. Models Image Process., 60(2):125--35, 1998. Google ScholarDigital Library
- Nina Amenta, Sunghee Choi, and Ravi Kolluri. The power crust, unions of balls, and the medial axis transform. Computational Geometry: Theory and Applications, 19(2--3):127--153, 2001. Google ScholarDigital Library
- Nina Amenta and Ravi Krishna Kolluri. The medial axis of a union of balls. Comput. Geom. Theory Appl., 20(1--2):25--37, 2001. Google ScholarDigital Library
- Dominique Attali and Annick Montanvert. Computing and simplifying 2D and 3D continuous skeletons. Comput. Vis. Image Underst., 67(3):261--273, 1997. Google ScholarDigital Library
- André Lieutier. Any open bounded subset of Rn has the same homotopy type than its medial axis. In SM'03: Proceedings of the eighth ACM symposium on Solid modeling and applications, pages 65--75, New York, NY, USA, 2003. ACM Press. Google ScholarDigital Library
Index Terms
- Medial axis approximation from inner Voronoi balls: a demo of the Mesecina tool
Recommendations
The medial axis of the union of inner Voronoi balls in the plane
Consider a dense sampling S of the smooth boundary of a planar shape O, i.e., an open subset of R 2 . We show that the medial axis of the union of Voronoi balls centered at Voronoi vertices inside O has a particularly simple structure: it is the union ...
Homotopy-preserving medial axis simplification
SPM '05: Proceedings of the 2005 ACM symposium on Solid and physical modelingWe present a novel algorithm to compute a simplified medial axis of a polyhedron. Our simplification algorithm tends to remove unstable features of Blum's medial axis. Moreover, our algorithm preserves the topological structure of the original medial ...
The scale axis picture show
SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometryWe demonstrate how the scale axis transform can be used to compute a parameterized family of shape skeletons. The skeletons gradually represent only the most important features of a shape, in a scale-adaptive manner. Here a shape O is any bounded open ...
Comments