A Straight Skeleton Approximating the Medial Axis | SpringerLink
Skip to main content

A Straight Skeleton Approximating the Medial Axis

  • Conference paper
Algorithms – ESA 2004 (ESA 2004)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 3221))

Included in the following conference series:

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

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. 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)

    Google Scholar 

  2. Brady, M., Asada, H.: Smoothed Local Symmetries and their Implementation. The International Journal of Robotics Research 3(3), 36–61 (1984)

    Article  Google Scholar 

  3. Leyton, M.: A Process Grammar for Shape. Art Intelligence 34, 213–247 (1988)

    Article  Google Scholar 

  4. Ogniewicz, R.L., Kubler, O.: Hierarchic Voronoi Skeletons. Pattern Recognition 28(3), 343–359 (1995)

    Article  Google Scholar 

  5. 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)

    Google Scholar 

  6. 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)

    Google Scholar 

  7. 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)

    Google Scholar 

  8. Tănase, M., Veltkamp, R.C.: A Straight Skeleton Approximating the Linear Axis. TR (2004)

    Google Scholar 

  9. 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)

    Article  MATH  MathSciNet  Google Scholar 

  10. 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)

    Article  MATH  MathSciNet  Google Scholar 

  11. Cheng, S.-W., Vigneron, A.: Motorcycle Graphs and Straight Skeletons. In: Proc. 13th ACM-SIAM Symp. Discrete Algorithms, pp. 156–165 (2002)

    Google Scholar 

  12. 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)

    Google Scholar 

  13. A VD LEP, the Abstract Voronoi Diagram LEDA Extension Package, http://www.mpi-sb.mpg.de/LEDA/friends/avd.html

  14. Felkel, P., Obdržálek, Š.: Straight Skeleton Implementation. In: Proc. of Spring Conference on Computer Graphics, Budmerice, Slovakia, pp. 210–218 (1998)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints 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

Publish with us

Policies and ethics