Document Open Access Logo

On Implementing Straight Skeletons: Challenges and Experiences

Authors Günther Eder , Martin Held , Peter Palfrader

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.38.pdf
  • Filesize: 1.73 MB
  • 17 pages

Document Identifiers

Author Details

Günther Eder
  • Universität Salzburg, FB Computerwissenschaften, Austria
Martin Held
  • Universität Salzburg, FB Computerwissenschaften, Austria
Peter Palfrader
  • Universität Salzburg, FB Computerwissenschaften, Austria

Funding

Work supported by Austrian Science Fund (FWF): Grants ORD 53-VO and P31013-N31.

Cite As Get BibTex

Günther Eder, Martin Held, and Peter Palfrader. On Implementing Straight Skeletons: Challenges and Experiences. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SoCG.2020.38

Abstract

We present Cgal implementations of two algorithms for computing straight skeletons in the plane, based on exact arithmetic. One code, named Surfer2, can handle multiplicatively weighted planar straight-line graphs (PSLGs) while our second code, Monos, is specifically targeted at monotone polygons. Both codes are available on GitHub. We discuss algorithmic as well as implementational and engineering details of both codes. Furthermore, we present the results of an extensive performance evaluation in which we compared Surfer2 and Monos to the straight-skeleton package included in Cgal. It is not surprising that our special-purpose code Monos outperforms Cgal’s straight-skeleton implementation. But our tests provide ample evidence that also Surfer2 can be expected to be faster and to consume significantly less memory than the Cgal code. And, of course, Surfer2 is more versatile because it can handle multiplicative weights and general PSLGs as input. Thus, Surfer2 currently is the fastest and most general straight-skeleton code available.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • weighted straight skeleton
  • implementation
  • algorithm engineering
  • experiments
  • Cgal
  • Core

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Oswin Aichholzer and Franz Aurenhammer. Straight Skeletons for General Polygonal Figures in the Plane. In Voronoi’s Impact on Modern Sciences II, volume 21, pages 7-21. Institute of Mathematics of the National Academy of Sciences of Ukraine, 1998. URL: https://doi.org/10.1007/3-540-61332-3_144.
  2. Oswin Aichholzer, Franz Aurenhammer, David Alberts, and Bernd Gärtner. A Novel Type of Skeleton for Polygons. Journal of Universal Computer Science, 1(12):752-761, 1995. URL: https://doi.org/10.1007/978-3-642-80350-5_65.
  3. Thomas Auer and Martin Held. Heuristics for the Generation of Random Polygons. In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG), pages 38-44, 1996. Google Scholar
  4. Therese Biedl, Martin Held, Stefan Huber, Dominik Kaaser, and Peter Palfrader. A Simple Algorithm for Computing Positively Weighted Straight Skeletons of Monotone Polygons. Information Processing Letters, 115(2):243-247, 2015. URL: https://doi.org/10.1016/j.ipl.2014.09.021.
  5. Therese Biedl, Martin Held, Stefan Huber, Dominik Kaaser, and Peter Palfrader. Weighted Straight Skeletons in the Plane. Computational Geometry: Theory and Applications, 48(2):120-133, 2015. URL: https://doi.org/10.1016/j.comgeo.2014.08.006.
  6. Therese Biedl, Stefan Huber, and Peter Palfrader. Planar Matchings for Weighted Straight Skeletons. In Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC), pages 117-127, 2014. URL: https://doi.org/10.1007/978-3-319-13075-0_10.
  7. Ulrik Brandes, Markus Eiglsperger, Ivan Herman, Michael Himsolt, and M. Scott Marshall. GraphML Progress Report Structural Layer Proposal. In Proceedings of the 9th International Symposium on Graph Drawing, pages 501-512, 2001. URL: http://graphml.graphdrawing.org/.
  8. Fernando Cacciola. Private email correspondence, 2010. Google Scholar
  9. Fernando Cacciola. 2D Straight Skeleton and Polygon Offsetting. In CGAL User and Reference Manual. CGAL Editorial Board, 5.0 edition, 2019. URL: https://doc.cgal.org/5.0/Manual/packages.html#PkgStraightSkeleton2.
  10. Siu-Wing Cheng, Liam Mencel, and Antoine Vigneron. A Faster Algorithm for Computing Straight Skeletons. ACM Transactions on Algorithms, 12(3):44:1-44:21, 2016. URL: https://doi.org/10.1145/2898961.
  11. Günther Eder, Martin Held, SteinÞór Jasonarson, Philipp Mayer, and Peter Palfrader. On Generating Polygons: Introducing the Salzburg Database. In Proceedings of the 36th European Workshop on Computational Geometry, pages 75:1-7, 2020. Google Scholar
  12. Günther Eder and Martin Held. Computing Positively Weighted Straight Skeletons of Simple Polygons based on Bisector Arrangement. Information Processing Letters, 132:28-32, 2018. URL: https://doi.org/10.1016/j.ipl.2017.12.001.
  13. David Eppstein and Jeff Erickson. Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions. Discrete & Computational Geometry, 22(4):569-592, 1999. URL: https://doi.org/10.1145/276884.276891.
  14. Petr Felkel and Š. Obdržálek. Straight Skeleton Implementation. In Proceedings of the 14th Spring Conference on Computer Graphics (SCCG), pages 210-218, 1998. Google Scholar
  15. Martin Held and Peter Palfrader. Straight Skeletons with Additive and Multiplicative Weights and Their Application to the Algorithmic Generation of Roofs and Terrains. Computer-Aided Design, 92(1):33-41, 2017. URL: https://doi.org/10.1016/j.cad.2017.07.003.
  16. Martin Held and Peter Palfrader. Skeletal Structures for Modeling Generalized Chamfers and Fillets in the Presence of Complex Miters. Computer-Aided Design and Applications, 16(4):620-627, 2019. URL: https://doi.org/10.14733/cadaps.2019.620-627.
  17. Stefan Huber. Computing Straight Skeletons and Motorcycle Graphs: Theory and Practice. Shaker Verlag, 2012. ISBN 978-3-8440-0938-5. Google Scholar
  18. Stefan Huber and Martin Held. Theoretical and Practical Results on Straight Skeletons of Planar Straight-line Graphs. In SoCG '11: Proceedings of the twenty-seventh Annual Symposium on Computational Geometry, 2011. URL: https://doi.org/10.1145/1998196.1998223.
  19. Tom Kelly and Peter Wonka. Interactive Architectural Modeling with Procedural Extrusions. ACM Transactions on Graphics, 30(2):14:1-14:15, April 2011. URL: https://doi.org/10.1145/1944846.1944854.
  20. Lutz Kettner. Halfedge Data Structures. In CGAL User and Reference Manual. CGAL Editorial Board, 5.0 edition, 2019. URL: https://doc.cgal.org/5.0/Manual/packages.html#PkgHalfedgeDS.
  21. Peter Palfrader, Martin Held, and Stefan Huber. On Computing Straight Skeletons by Means of Kinetic Triangulations. In Proceedings of the 20th Annual European Symposium on Algorithms (ESA), pages 766-777, 2012. URL: https://doi.org/10.1007/978-3-642-33090-2_66.
  22. The CGAL Project. CGAL User and Reference Manual. CGAL Editorial Board, 5.0 edition, 2019. URL: https://doc.cgal.org/5.0/Manual/packages.html.
  23. Antoine Vigneron and Lie Yan. A Faster Algorithm for Computing Motorcycle Graphs. Discrete & Computational Geometry, 52(3):492-514, 2014. URL: https://doi.org/10.1007/00454-014-9625-2.
  24. Evgeny Yakersberg. Morphing Between Geometric Shapes Using Straight-Skeleton-Based Interpolation. MSc thesis, CS Dept., Technion, Haifa, Israel, 2004. Google Scholar
  25. Mariette Yvinec. 2D Triangulation. In CGAL User and Reference Manual. CGAL Editorial Board, 5.0 edition, 2019. URL: https://doc.cgal.org/5.0/Manual/packages.html#PkgTriangulation2.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact