Abstract
We propose the linear axis, a new skeleton for polygonal shapes. It is related to the medial axis and the straight skeleton, being the result of a wavefront propagation process. The wavefront is linear and propagates by translating edges at constant speed. The initial wavefront is an altered version of the original polygon: zero-length edges are added at reflex vertices. The linear axis is a subset of the straight skeleton of the altered polygon. In this way, the counter-intuitive effects in the straight skeleton caused by sharp reflex vertices are alleviated. We introduce the notion of ε-equivalence between two skeletons, and give an algorithm that computes the number of zero-length edges for each reflex vertex which yield a linear axis ε-equivalent to the medial axis. This linear axis and thus the straight skeleton can be computed from the medial axis in linear time for polygons with a constant number of “nearly co-circular” sites. All previous algorithms for straight skeleton computation are sub-quadratic.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Blum, H.: A Transformation for Extracting New Descriptors of Shape. In: Wathen-Dunn, W. (ed.) Symp. Mo dels for Speech and Visual Form, pp. 362–381. MIT Press, Cambridge (1967)
Brady, M., Asada, H.: Smoothed Local Symmetries and their Implementation. The International Journal of Robotics Research 3(3), 36–61 (1984)
Leyton, M.: A Process Grammar for Shape. Art Intelligence 34, 213–247 (1988)
Ogniewicz, R.L., Kubler, O.: Hierarchic Voronoi Skeletons. Pattern Recognition 28(3), 343–359 (1995)
Aichholzer, O., Aurenhammer, F.: Straight Skeletons for General Polygonal Figures in the Plane. In: Cai, J.-Y., Wong, C.K. (eds.) COCOON 1996. LNCS, vol. 1090, pp. 117–126. Springer, Heidelberg (1996)
Aichholzer, O., Aurenhammer, F., Alberts, D., Gärtner, B.: A Novel Type of Skeleton for Polygons. The Journal of Universal Computer Science 1, 752–761 (1995)
Tănase, M., Veltkamp, R.C.: Polygon Decomposition based on the Straight Line Skeleton. In: Proc.19th ACM Symp. on Computational Geometry, pp. 58–67 (2003)
Tănase, M., Veltkamp, R.C.: A Straight Skeleton Approximating the Linear Axis. TR (2004)
Chin, F., Snoeyink, J., Wang, C.-A.: Finding the Medial Axis of a Simple Polygon in Linear Time. Discrete Computational Geometry 21(3), 405–420 (1999)
Eppstein, D., Erickson, J.: Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions. Discrete and Computational Geometry 22(4), 569–592 (1999)
Cheng, S.-W., Vigneron, A.: Motorcycle Graphs and Straight Skeletons. In: Proc. 13th ACM-SIAM Symp. Discrete Algorithms, pp. 156–165 (2002)
Douglas, D.H., Peucker, T.K.: Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or its Caricature. The Canadian Cartographer 10(2), 112–122 (1973)
A VD LEP, the Abstract Voronoi Diagram LEDA Extension Package, http://www.mpi-sb.mpg.de/LEDA/friends/avd.html
Felkel, P., Obdržálek, Š.: Straight Skeleton Implementation. In: Proc. of Spring Conference on Computer Graphics, Budmerice, Slovakia, pp. 210–218 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tănase, M., Veltkamp, R.C. (2004). A Straight Skeleton Approximating the Medial Axis. In: Albers, S., Radzik, T. (eds) Algorithms – ESA 2004. ESA 2004. Lecture Notes in Computer Science, vol 3221. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30140-0_71
Download citation
DOI: https://doi.org/10.1007/978-3-540-30140-0_71
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23025-0
Online ISBN: 978-3-540-30140-0
eBook Packages: Springer Book Archive