Jump to content

Straight skeleton: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
m →Algorithms: Huber and Held 2011
this was mostly cs1 in 2015; standardize on that
 
(82 intermediate revisions by 32 users not shown)
Line 1: Line 1:
{{Short description|Method in geometry for representing a polygon by a topological skeleton}}
[[Image:StraightSkeletonNew.png|thumb|240px|The straight skeleton, the shrinking process that creates it, and a three-dimensional roofline created from it.]]
{{CS1 config|mode=cs1}}
In [[geometry]], a '''straight skeleton''' is a method of representing a [[polygon]] by a [[topological skeleton]]. It is similar in some ways to the [[medial axis]] but differs in that the skeleton is composed of straight line segments, while the medial axis of a polygon may involve parabolic curves.
[[Image:StraightSkeletonDefinition.png|thumb|240px|The shrinking process, the straight skeleton (blue) and the roof model.]]
In [[geometry]], a '''straight skeleton''' is a method of representing a [[polygon]] by a [[topological skeleton]]. It is similar in some ways to the [[medial axis]] but differs in that the skeleton is composed of straight line segments, while the medial axis of a polygon may involve parabolic curves. However, both are [[Homotopy#Homotopy equivalence|homotopy-equivalent]] to the underlying polygon.<ref name="Huber 2018">{{citation
| last1 = Huber | first1 = Stefan
| contribution = The Topology of Skeletons and Offsets
| contribution-url = https://conference.imp.fu-berlin.de/eurocg18/download/paper_17.pdf
| title = Proceedings of the 34th European Workshop on Computational Geometry (EuroCG'18)
| year = 2018}}.</ref>


Straight skeletons were first defined for simple polygons by Aichholzer et al.,<ref name="Aichholzer 1995">{{cite journal
Straight skeletons were first defined for simple polygons by {{harvtxt|Aichholzer|Aurenhammer|Alberts|Gärtner|1995}},<ref name="Aichholzer 1995">{{citation
| author = Aichholzer, Oswin; Aurenhammer, Franz; Alberts, David; Gärtner, Bernd
| last1 = Aichholzer | first1 = Oswin
| last2 = Aurenhammer | first2 = Franz | author2-link = Franz Aurenhammer
| last3 = Alberts | first3 = David
| last4 = Gärtner | first4 = Bernd
| doi = 10.1007/978-3-642-80350-5_65
| issue = 12
| journal = Journal of Universal Computer Science
| journal = Journal of Universal Computer Science
| mr = 1392429
| title = A novel type of skeleton for polygons
| volume = 1
| issue = 12
| pages = 752–761
| pages = 752–761
| title = A novel type of skeleton for polygons
| id = {{MathSciNet | id = 1392429}}
| url = http://www.jucs.org/jucs_1_12/a_novel_type_of
| url = http://www.jucs.org/jucs_1_12/a_novel_type_of
| volume = 1
|year=1995}}</ref> and generalized to [[planar straight line graph]]s by Aichholzer and Aurenhammer.<ref name="Aichholzer 1996">{{cite conference
| year = 1995}}.</ref> and generalized to [[planar straight-line graph]]s (PSLG) by {{harvtxt|Aichholzer|Aurenhammer|1996}}.<ref name="Aichholzer 1996">{{citation
| author = Aichholzer, Oswin; Aurenhammer, Franz
| last1 = Aichholzer | first1 = Oswin
| title = Straight skeletons for general polygonal figures in the plane
| last2 = Aurenhammer | first2 = Franz
| booktitle = Proc. 2nd Ann. Int. Conf. Computing and Combinatorics (COCOON '96)
| contribution = Straight skeletons for general polygonal figures in the plane
| publisher = Lecture Notes in Computer Science, no. 1090, Springer-Verlag
| contribution-url = http://www.igi.tugraz.at/auren/psfiles/aa-ssgpf-98.ps.gz
| pages = 117–126
| pages = 117–126
| publisher = Springer-Verlag
| url = http://www.igi.tugraz.at/auren/psfiles/aa-ssgpf-98.ps.gz
| series = Lecture Notes in Computer Science
| date = 1996}}</ref>
| title = Proc. 2nd Ann. Int. Conf. Computing and Combinatorics (COCOON '96)
| volume = 1090
| year = 1996}}</ref>
In their interpretation as projection of roof surfaces, they are already extensively discussed by {{harvs|first=G. A.|last=Peschka|year=1877|txt}}.<ref>{{citation
| last = Peschka | first = Gustav A.
| location = Brünn
| publisher = Buschak & Irrgang
| title = Kotirte Ebenen: Kotirte Projektionen und deren Anwendung; Vorträge
| doi = 10.14463/GBV:865177619
| url = https://books.google.com/books?id=N1DWSb3oh7sC
| year = 1877}}.</ref>


==Definition==
==Definition==
The straight skeleton of a polygon is defined by a continuous shrinking process in which the edges of the polygon are moved inwards parallel to themselves at a constant speed. As the edges move in this way, the vertices where pairs of edges meet also move, at speeds that depend on the angle of the vertex. If one of these moving vertices collides with a nonadjacent edge, the polygon is split in two by the collision, and the process continues in each part. The straight skeleton is the set of curves traced out by the moving vertices in this process.
The straight skeleton of a polygon is defined by a continuous shrinking process in which the edges of the polygon are moved inwards parallel to themselves at a constant speed. As the edges move in this way, the vertices where pairs of edges meet also move, at speeds that depend on the angle of the vertex. If one of these moving vertices collides with a nonadjacent edge, the polygon is split in two by the collision, and the process continues in each part. The straight skeleton is the set of curves traced out by the moving vertices in this process.
In the illustration the top figure shows the shrinking process and the middle figure depicts the straight skeleton in blue.

For example, part (i) of the illustration shows the straight skeleton of a polygon. Part (ii) shows the sequence of smaller polygons traced out during the shrinking process by the moving edges.


==Algorithms==
==Algorithms==
The straight skeleton may be computed by simulating the shrinking process by which it is defined; a number of variant algorithms for computing it have been proposed, differing in the assumptions they make on the input and in the [[data structure]]s they use for detecting combinatorial changes in the input polygon as it shrinks.
The straight skeleton may be computed by simulating the shrinking process by which it is defined; a number of variant algorithms for computing it have been proposed, differing in the assumptions they make on the input and in the [[data structure]]s they use for detecting combinatorial changes in the input polygon as it shrinks.


The following algorithms consider an input that forms a polygon, a [[polygon with holes]], or a PSLG. For a polygonal input we denote the number of vertices by ''n'' and the number of reflex (concave, i.e., angle greater than {{pi}}) vertices by ''r''. If the input is a PSLG then we consider the initial wavefront structure, which forms a set of polygons, and again denote by ''n'' the number of vertices and by ''r'' the number of reflex vertices w.r.t. the propagation direction. Most of the algorithms listed here are designed and analyzed in the [[real RAM]] model of computation.
*Aichholzer et al.<ref name="Aichholzer 1995"/><ref name="Aichholzer 1996"/> showed how to compute straight skeletons for arbitrary two-dimensional inputs in time O(''n''<sup>2</sup>&nbsp;log&nbsp;''n''), or more strongly in time O(''nr''&nbsp;log&nbsp;''n''), where ''n'' is the number of vertices of the input polygon and ''r'' is the number of reflex (concave) vertices. A simpler method with the same running time is given by Huber and Held, who argue that their approach is likely to run in near-linear time for many inputs.<ref>{{cite conference|last1=Huberfirst1=Stefan|last2=Held|first2=Martin|title=Computing straight skeletons of planar straight-line graphs based on motorcycle graphs|booktitle=Proceedings of the 22nd Canadian Conference on Computational Geometry|date=2010|url=http://www.cs.umanitoba.ca/~cccg2010/electronicProceedings/paper15.pdf}} {{cite conference|last1=Huberfirst1=Stefan|last2=Held|first2=Martin|title=Theoretical and pratical results on straight skeletons of planar straight-line graphs|booktitle=Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SCG'11), June 13–15, 2011, Paris, France|pages=171–178|year=2011}}.</ref>

*By using data structures for the [[Closest pair of points problem|bichromatic closest pair problem]], [[David Eppstein|Eppstein]] and Erickson showed how to construct straight skeleton problems using a linear number of closest pair data structure updates. A closest pair data structure based on [[quadtree]]s provides an O(''nr''&nbsp;+&nbsp;''n''&nbsp;log&nbsp;''n'') time algorithm, or a significantly more complicated data structure leads to the better asymptotic time bound {{nowrap|O(''n''<sup>1 + &epsilon;</sup> + ''n''<sup>8/11 + &epsilon;</sup>''r''<sup>9/11 + &epsilon;</sup>)}}, or more simply {{nowrap|O(''n''<sup>17/11 + &epsilon;</sup>)}}, where &epsilon; is any constant greater than zero.<ref name="Eppstein 1999">{{cite journal
*Aichholzer et al.<ref name="Aichholzer 1995" /><ref name="Aichholzer 1996" /> showed how to compute straight skeletons of PSLGs in time O(''n''<sup>3</sup>&nbsp;log&nbsp;''n''), or more precisely time O((''n''<sup>2</sup>+''f'')&nbsp;log&nbsp;''n''), where ''n'' is the number of vertices of the input polygon and ''f'' is the number of flip events during the construction. The best known bound for ''f'' is O(''n''<sup>3</sup>).
| author = [[David Eppstein|Eppstein, David]]; Erickson, Jeff
*An algorithm with a worst case running time in O(''nr''&nbsp;log&nbsp;n), or simply O(''n''<sup>2</sup>&nbsp;log&nbsp;n), is given by {{harvs|last1=Huber|last2=Held|year=2010|year2=2011|txt}}, who argue that their approach is likely to run in near-linear time for many inputs.<ref>{{citation
| title = Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions
| last1 = Huber | first1 = Stefan
| journal = Discrete & Computational Geometry
| last2 = Held | first2 = Martin
| volume = 22
| contribution = Computing straight skeletons of planar straight-line graphs based on motorcycle graphs
| contribution-url = http://www.cs.umanitoba.ca/~cccg2010/electronicProceedings/paper15.pdf
| title = Proceedings of the 22nd Canadian Conference on Computational Geometry
| year = 2010}}.</ref><ref>{{citation
| last1 = Huber | first1 = Stefan
| last2 = Held | first2 = Martin
| contribution = Theoretical and practical results on straight skeletons of planar straight-line graphs
| contribution-url = https://www.sthu.org/research/publications/files/HuHe11.pdf
| pages = 171–178
| title = Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SCG'11), June 13–15, 2011, Paris, France
| year = 2011}}.</ref>
*Petr Felkel and Štěpán Obdržálek designed an algorithm for simple polygons that is said to have an efficiency of O(''nr'' + ''n'' log ''r'').<ref>{{citation
| accessdate = 2013-08-05
| contribution = CenterLineReplacer
| contribution-url = http://docs.safe.com/fme/2012/html/FME_Transformers/content/transformers/centerlinereplacer.htm
| publisher = Safe Software
| title = FME Transformers}}.</ref><ref>{{citation
| last1 = Felkel | first1 = Petr
| last2 = Obdržálek | first2 = Štěpán
| contribution = Straight skeleton implementation
| pages = 210–218
| title = SCCG 98: Proceedings of the 14th Spring Conference on Computer Graphics
| year = 1998}}.</ref> However, it has been shown that their algorithm is incorrect.<ref>{{citation
| last = Huber | first = Stefan
| isbn = 978-3-8440-0938-5
| publisher = Shaker Verlag
| title = Computing Straight Skeletons and Motorcycle Graphs: Theory and Practice
| url = http://www.shaker.de/de/content/catalogue/index.asp?lang=de&ID=8&ISBN=978-3-8440-0938-5
| year = 2012}}.</ref><ref>{{citation
| last = Yakersberg | first = Evgeny
| publisher = Israel Institute of Technology
| title = Morphing Between Geometric Shapes Using Straight-Skeleton-Based Interpolation.
| year = 2004}}.</ref>
*By using data structures for the [[Closest pair of points problem|bichromatic closest pair problem]], [[David Eppstein|Eppstein]] and Erickson showed how to construct straight skeleton problems using a linear number of closest pair data structure updates. A closest pair data structure based on [[quadtree]]s provides an O(''nr''&nbsp;+&nbsp;''n''&nbsp;log&nbsp;''n'') time algorithm, or a significantly more complicated data structure leads to the better asymptotic time bound {{nowrap|O(''n''<sup>1 + ε</sup> + ''n''<sup>8/11 + ε</sup>''r''<sup>9/11 + ε</sup>)}}, or more simply {{nowrap|O(''n''<sup>17/11 + ε</sup>)}}, where ε is any constant greater than zero.<ref name="Eppstein 1999">{{citation
| last1 = Eppstein | first1 = David | author1-link = David Eppstein
| last2 = Erickson | first2 = Jeff
| doi = 10.1007/PL00009479
| issue = 4
| issue = 4
| journal = [[Discrete and Computational Geometry]]
| mr = 1721026
| pages = 569–592
| pages = 569–592
| title = Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions
| url = http://compgeom.cs.uiuc.edu/~jeffe/pubs/pdf/cycles.pdf
| url = https://jeffe.cs.illinois.edu/pubs/cycles.html
| doi = 10.1007/PL00009479
| volume = 22
| id = {{MathSciNet | id = 1721026}}
| year = 1999}}</ref> This remains the best worst-case time bound known for straight skeleton construction with unrestricted inputs, but is complicated and has not been implemented.
| year = 1999| s2cid = 12460625 | doi-access = free
}}.</ref> This remains the best worst-case time bound known for straight skeleton construction with unrestricted inputs, but is complicated and has not been implemented.
*For [[simple polygon]]s, the problem of straight skeleton construction is easier. Cheng and Vigneron showed how to compute the straight skeleton of simple polygons with ''n'' vertices, ''r'' of which have angles greater than [[Pi]], in time O(''n'' log<sup>2</sup> ''n'' + ''r''<sup>3/2</sup> log ''r'').<ref name="Cheng 2002">{{cite conference
*For [[simple polygon]]s in [[general position]], the problem of straight skeleton construction is easier. Cheng, Mencel, and Vigneron showed how to compute the straight skeleton of simple polygons in time O(''n'' log ''n'' log ''r'' + ''r''<sup>4/3 + ε</sup>).<ref name="Cheng 2016">
{{citation
| author = Cheng, Siu-Wing; Vigneron, Antoine
| last1 = Cheng | first1 = Siu-Wing
| title = Motorcycle graphs and straight skeletons
| last2 = Mencel | first2 = Liam
| booktitle = Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms
| last3 = Vigneron | first3 = Antoine
| date = 2002
| title = A faster algorithm for computing straight skeletons
| pages = 156–165
| pages = 44:1–44:21
| url = http://www.cs.ust.hk/~scheng/pub/motorpub.pdf}}</ref> In the worst case, ''r'' may be linear, in which case this time bound may be simplified to O(''n''<sup>3/2</sup>&nbsp;log&nbsp;''n'').
| journal = ACM Transactions on Algorithms
*A [[monotone polygon]] with respect to a line ''L'' is a polygon with the property that every line orthogonal to ''L'' intersects the polygon in a single interval. When the input is a monotone polygon, its straight skeleton can be constructed in time O(''n''&nbsp;log&nbsp;''n'').<ref>{{cite conference|author=Das, Gautam K.; Mukhopadhyay, Asish; Nandy, Subhas C.; Patil, Sangameswar; Rao, S. V.|title=Computing the straight skeletons of a monotone polygon in O(''n''&nbsp;log&nbsp;''n'') time|booktitle=Proceedings of the 22nd Canadian Conference on Computational Geometry|date=2010|url=http://www.cs.umanitoba.ca/~cccg2010/electronicProceedings/paper24.pdf}}</ref>
| volume = 12
| number = 3
| year = 2016| doi = 10.1145/2898961
| arxiv = 1405.4691
}}.</ref> In the worst case, ''r'' may be on the order of ''n'', in which case this time bound may be simplified to O(''n''<sup>4/3+ε</sup>). If the vertices of the input polygon have O(log n)-bit rational coordinates, their algorithm can be improved to run in O(''n''&nbsp;log&nbsp;''n'') time, even if the input polygon is not in [[general position]].
*A [[monotone polygon]] with respect to a line ''L'' is a polygon with the property that every line orthogonal to ''L'' intersects the polygon in a single interval. When the input is a monotone polygon, its straight skeleton can be constructed in time O(''n''&nbsp;log<sup>2</sup>&nbsp;''n'').<ref>{{cite journal
| last1 = Biedl | first1 = Therese | author1-link = Therese Biedl
| last2 = Held | first2 = Martin
| last3 = Huber | first3 = Stefan
| last4 = Kaaser | first4 = Dominik
| last5 = Palfrader | first5 = Peter
| date = February 2015
| title = A Simple Algorithm for Computing Positively Weighted Straight Skeletons of Monotone Polygons
| journal = Information Processing Letters
| volume= 115
| issue = 2
| pages = 243–247
| doi = 10.1016/j.ipl.2014.09.021
| pmid = 25648376 | pmc = 4308025 | url = https://www.palfrader.org/research/k/Bie_15b.pdf
}} As Biedl et al. point out, an earlier algorithm for monotone polygons by Das et&nbsp;al. is incorrect as described, and at best works only for inputs in [[general position]] that do not have vertex-vertex events: {{citation
| last1 = Das | first1 = Gautam K.
| last2 = Mukhopadhyay | first2 = Asish
| last3 = Nandy | first3 = Subhas C.
| last4 = Patil | first4 = Sangameswar
| last5 = Rao | first5 = S. V.
| contribution = Computing the straight skeletons of a monotone polygon in O(''n''&nbsp;log&nbsp;''n'') time
| contribution-url = http://www.cs.umanitoba.ca/~cccg2010/electronicProceedings/paper24.pdf
| title = Proceedings of the 22nd Canadian Conference on Computational Geometry
| year = 2010}}.</ref>


== Applications ==
== Applications ==
Each point within the input polygon can be lifted into three-dimensional space by using the time at which the shrinking process reaches that point as the z-coordinate of the point. The resulting three-dimensional surface has constant height on the edges of the polygon, and rises at constant slope from them except for the points of the straight skeleton itself, where surface patches at different angles meet. In this way, the straight skeleton can be used as the set of ridge lines of a building roof, based on walls in the form of the initial polygon.<ref name="Aichholzer 1995"/><ref name="Bélanger 2000">{{cite web
Each point within the input polygon can be lifted into three-dimensional space by using the time at which the shrinking process reaches that point as the z-coordinate of the point. The resulting three-dimensional surface has constant height on the edges of the polygon, and rises at constant slope from them except for the points of the straight skeleton itself, where surface patches at different angles meet. In this way, the straight skeleton can be used as the set of ridge lines of a building roof, based on walls in the form of the initial polygon.<ref name="Aichholzer 1995"/><ref name="Bélanger 2000">{{citation
| author = Bélanger, David
| last = Bélanger | first = David
| title = Designing Roofs of Buildings
| title = Designing Roofs of Buildings
| url = http://www.sable.mcgill.ca/~dbelan2/roofs/roofs.html
| year = 2000
| url = http://www.sable.mcgill.ca/~dbelan2/roofs/roofs.html}}</ref> Part (iii) of the illustration depicts a surface formed from the straight skeleton in this way.
| year = 2000}}.</ref> The bottom figure in the illustration depicts a surface formed from the straight skeleton in this way.


Demaine, Demaine and Lubiw used the straight skeleton as part of a technique for folding a sheet of paper so that a given polygon can be cut from it with a single straight cut, and related [[origami]] design problems.<ref name="Demaine 1998">{{cite conference
Demaine, Demaine and Lubiw used the straight skeleton as part of a technique for folding a sheet of paper so that a given polygon can be cut from it with a single straight cut (the [[fold-and-cut theorem]]), and related [[origami]] design problems.<ref name="Demaine 1998">{{citation
| author = [[Erik Demaine|Demaine, Erik D.]]; [[Martin Demaine|Demaine, Martin L.]]; Lubiw, Anna
| last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
| last2 = Demaine | first2 = Martin L. | author2-link = Martin Demaine
| title = Folding and cutting paper
| last3 = Lubiw | first3 = Anna | author3-link = Anna Lubiw
| booktitle = Revised Papers from the Japan Conference on Discrete and Computational Geometry (JCDCG'98)
| contribution = Folding and cutting paper
| publisher = Lecture Notes in Computer Science, no. 1763, Springer-Verlag
| contribution-url = http://theory.lcs.mit.edu/~edemaine/papers/JCDCG98/
| pages = 104–117
| date = 1998
| doi = 10.1007/b75044
| doi = 10.1007/b75044
| pages = 104–117
| url = http://theory.lcs.mit.edu/~edemaine/papers/JCDCG98/}}</ref>
| publisher = Springer-Verlag
| series = Lecture Notes in Computer Science
| title = Revised Papers from the Japan Conference on Discrete and Computational Geometry (JCDCG'98)
| volume = 1763
| year = 1998| isbn = 978-3-540-67181-7 | s2cid = 32962663 }}.</ref>


Barequet et al. use straight skeletons in an algorithm for finding a three-dimensional surface that interpolates between two given [[polygonal curve]]s.<ref name="Barequet 2003">{{cite conference
Barequet et al. use straight skeletons in an algorithm for finding a three-dimensional surface that interpolates between two given [[polygonal chain]]s.<ref name="Barequet 2003">{{citation
| last1 = Barequet | first1 = Gill
| author = Barequet, Gill; [[Michael T. Goodrich|Goodrich, Michael T.]]; Levi-Steiner, Aya; Steiner, Dvir
| last2 = Goodrich | first2 = Michael T. | author2-link = Michael T. Goodrich
| title = Straight-skeleton based contour interpolation
| last3 = Levi-Steiner | first3 = Aya
| booktitle = Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms
| last4 = Steiner | first4 = Dvir
| contribution = Straight-skeleton based contour interpolation
| contribution-url = https://www.cs.technion.ac.il/~barequet/teaching/cg/sp01/project/papers/Barequet-Goodrich.ps.gz
| pages = 119–127
| pages = 119–127
| title = Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms
| url = http://www.cs.technion.ac.il/~barequet/teaching/cg/sp01/project/papers/Barequet-Goodrich.ps.gz
| date = 2003}}</ref>
| year = 2003}}.</ref>


Tănase and Veltkamp propose to decompose concave polygons into unions of convex regions using straight skeletons, as a preprocessing step for shape matching in image processing.<ref name="Tănase 2003">{{cite conference
Tănase and Veltkamp propose to decompose [[concave polygon]]s into unions of convex regions using straight skeletons, as a preprocessing step for shape matching in image processing.<ref name="Tănase 2003">{{citation
| author = Tănase, Mirela; Veltkamp, Remco C.
| last1 = Tănase | first1 = Mirela
| last2 = Veltkamp | first2 = Remco C.
| title = Polygon decomposition based on the straight line skeleton
| contribution = Polygon decomposition based on the straight line skeleton
| booktitle = [[Symposium on Computational Geometry|Proceedings of the 19th Annual ACM Symposium on Computational Geometry]]
| date = 2003
| doi = 10.1145/777792.777802
| doi = 10.1145/777792.777802
| pages = 58–67}}</ref>
| pages = 58–67
| title = [[Symposium on Computational Geometry|Proceedings of the 19th Annual ACM Symposium on Computational Geometry]]
| year = 2003| isbn = 1-58113-663-3
| s2cid = 18173658
}}.</ref>


Bagheri and Razzazi use straight skeletons to guide vertex placement in a [[graph drawing]] algorithm in which the graph drawing is constrained to lie inside a polygonal boundary.<ref name="Bagheri 2004">{{cite journal
Bagheri and Razzazi use straight skeletons to guide vertex placement in a [[graph drawing]] algorithm in which the graph drawing is constrained to lie inside a polygonal boundary.<ref name="Bagheri 2004">{{citation
| author = Bagheri, Alireza; Razzazi, Mohammadreza
| last1 = Bagheri | first1 = Alireza
| last2 = Razzazi | first2 = Mohammadreza
| title = Drawing free trees inside simple polygons using polygon skeleton
| journal = Computing and Informatics
| volume = 23
| year = 2004
| issue = 3
| issue = 3
| journal = Computing and Informatics
| mr = 2165282
| pages = 239–254
| pages = 239–254
| title = Drawing free trees inside simple polygons using polygon skeleton
| id = {{MathSciNet | id=2165282}}}}</ref>
| volume = 23
| year = 2004}}.</ref>


The straight skeleton can also be used to construct an [[Parallel_(curve)|offset curve]] of a polygon, with [[miter joint|mitered corners]], analogously to the construction of an offset curve with rounded corners formed from the medial axis.
The straight skeleton can also be used to construct an [[Parallel (curve)|offset curve]] of a polygon, with [[miter joint|mitered corners]], analogously to the construction of an offset curve with rounded corners formed from the medial axis. Tomoeda and Sugihara apply this idea in the design of signage, visible from wide angles, with an illusory appearance of depth.<ref>{{citation
| last1 = Tomoeda | first1 = Akiyasu
| last2 = Sugihara | first2 = Kokichi
| contribution = Computational creation of a new illusionary solid sign
| doi = 10.1109/ISVD.2012.26
| pages = 144–147
| title = Ninth International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2012)
| year = 2012| isbn = 978-1-4673-1910-2
| s2cid = 27610348
}}.</ref> Similarly, Asente and Carr use straight skeletons to design [[color gradient]]s that match letter outlines or other shapes.<ref>{{citation
| last1 = Asente | first1 = Paul
| last2 = Carr | first2 = Nathan
| contribution = Creating contour gradients using 3D bevels
| doi = 10.1145/2487276.2487283
| isbn = 978-1-4503-2203-4
| location = New York, NY, USA
| pages = 63–66
| publisher = ACM
| title = Proceedings of the Symposium on Computational Aesthetics (CAE '13, Anaheim, California)
| year = 2013| s2cid = 17302186
}}.</ref>


As with other types of skeleton such as the [[medial axis]], the straight skeleton can be used to collapse a two-dimensional area to a simplified one-dimensional representation of the area. For instance, Haunert and Sester describe an application of this type for straight skeletons in [[geographic information system]]s, in finding the centerlines of roads.<ref>{{cite journal|author=Haunert, Jan-Henrik; Sester, Monika|title=Area collapse and road centerlines based on straight skeletons|journal=Geoinformatica|year=2008|volume=12|issue=2|pages=169–191|doi=10.1007/s10707-007-0028-x}}</ref><ref>{{cite book|title=Straight Skeleton Survey Adjustment Of Road Centerlines From Gps Coarse Acquisition Data: A Case Study In Bolivia|author=Raleigh, David Baring|series=Masters thesis|publisher=Ohio State University, Geodetic Science and Surveying|year=2008|url=http://etd.ohiolink.edu/view.cgi?acc_num=osu1221854081}}</ref>
As with other types of skeleton such as the [[medial axis]], the straight skeleton can be used to collapse a two-dimensional area to a simplified one-dimensional representation of the area. For instance, Haunert and Sester describe an application of this type for straight skeletons in [[geographic information system]]s, in finding the centerlines of roads.<ref>{{citation
| last1 = Haunert | first1 = Jan-Henrik
| last2 = Sester | first2 = Monika
| doi = 10.1007/s10707-007-0028-x
| issue = 2
| journal = GeoInformatica
| pages = 169–191
| title = Area collapse and road centerlines based on straight skeletons
| volume = 12
| year = 2008| s2cid = 2169666
}}.</ref><ref>{{citation
| last = Raleigh | first = David Baring
| publisher = Ohio State University, Geodetic Science and Surveying
| title = Straight Skeleton Survey Adjustment Of Road Centerlines From Gps Coarse Acquisition Data: A Case Study In Bolivia
| url = https://etd.ohiolink.edu/!etd.send_file?accession=osu1221854081&disposition=inline
| year = 2008}}.</ref>

Every [[Tree (graph theory)|tree]] with no [[Degree (graph theory)|degree]]-two vertices can be realized as the straight skeleton of a [[convex polygon]].<ref>{{citation
| last1 = Aichholzer | first1 = Oswin
| last2 = Cheng | first2 = Howard
| last3 = Devadoss | first3 = Satyan L.
| last4 = Hackl | first4 = Thomas
| last5 = Huber | first5 = Stefan
| last6 = Li | first6 = Brian
| last7 = Risteski | first7 = Andrej
| contribution = What makes a tree a straight skeleton?
| contribution-url = http://2012.cccg.ca/papers/paper30.pdf
| title = Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG'12)
| year = 2012}}.</ref> The [[convex hull]] of the roof shape corresponding to this straight skeleton forms a [[Steinitz's theorem|Steinitz realization]] of the [[Halin graph]] formed from the tree by connecting its leaves in a cycle.


==Higher dimensions==
==Higher dimensions==
Barequet et al. defined a version of straight skeletons for three-dimensional [[polyhedron|polyhedra]], described algorithms for computing it, and analyzed its complexity on several different types of polyhedron.<ref>{{cite conference|author=Barequet, Gill; [[David Eppstein|Eppstein, David]]; [[Michael T. Goodrich|Goodrich, Michael T.]]; Vaxman, Amir|title=Straight skeletons of three-dimensional polyhedra|booktitle=Proc. 16th European Symposium on Algorithms|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|date=2008|volume=5193|pages=148–160|doi=10.1007/978-3-540-87744-8_13|id={{arXiv|0805.0022}}}}</ref>
Barequet et al. defined a version of straight skeletons for three-dimensional [[polyhedron|polyhedra]], described algorithms for computing it, and analyzed its complexity on several different types of polyhedron.<ref>{{citation
| last1 = Barequet | first1 = Gill
| last2 = Eppstein | first2 = David | author2-link = David Eppstein
| last3 = Goodrich | first3 = Michael T. | author3-link = Michael T. Goodrich
| last4 = Vaxman | first4 = Amir
| arxiv = 0805.0022
| contribution = Straight skeletons of three-dimensional polyhedra
| doi = 10.1007/978-3-540-87744-8_13
| pages = 148–160
| publisher = Springer-Verlag
| series = Lecture Notes in Computer Science
| title = Proc. 16th European Symposium on Algorithms
| volume = 5193
| year = 2008| isbn = 978-3-540-87743-1
| s2cid = 42150
}}.</ref>

Huber et al. investigated [[metric space]]s under which the corresponding [[Voronoi diagram]]s and straight skeletons coincide. For two dimensions, the characterization of such metric spaces is complete. For higher dimensions, this method can be interpreted as a generalization of straight skeletons of certain input shapes to arbitrary dimensions by means of Voronoi diagrams.<ref name="Huber 2014">{{citation
| last1 = Huber | first1 = Stefan
| last2 = Aichholzer | first2 = Oswin
| last3 = Hackl | first3 = Thomas
| last4 = Vogtenhuber | first4 = Birgit
| contribution = Straight skeletons by means of Voronoi diagrams under polyhedral distance functions
| contribution-url = https://www.sthu.org/research/publications/files/cccg2014-skbyvd.pdf
| title = Proc. 26th Canadian Conference on Computational Geometry (CCCG'14)
| year = 2014}}.</ref>


==References==
==References==
{{reflist}}
{{reflist|30em}}


==External links==
==External links==
Line 108: Line 282:
| url = http://compgeom.cs.uiuc.edu/~jeffe/open/skeleton.html}}
| url = http://compgeom.cs.uiuc.edu/~jeffe/open/skeleton.html}}
* [http://www.cgal.org/Pkg/StraightSkeleton2 2D Straight Skeleton] in [[CGAL]], the Computational Geometry Algorithms Library
* [http://www.cgal.org/Pkg/StraightSkeleton2 2D Straight Skeleton] in [[CGAL]], the Computational Geometry Algorithms Library
* [https://polyskeleton.appspot.com/ Straight Skeleton for polygon with holes] Straight Skeleton builder implemented in java.
* {{cite web
| author = Amit Parnerkar, Sarnath Ramnath
| title = Engineering an efficient algorithm for finding the straight skeleton of a simple polygon in '''O(n log n)'''
| url = http://web.stcloudstate.edu/rsarnath/skeleton/definition.htm}}
* [https://www.sthu.org/code/stalgo/ STALGO]: "STALGO is an industrial-strength C++ software package for computing straight skeletons and mitered offset-curves." by Stefan Huber.


[[Category:Discrete geometry]]
[[Category:Discrete geometry]]
[[Category:Geometric algorithms]]
[[Category:Computational geometry]]

Latest revision as of 06:34, 29 August 2024

The shrinking process, the straight skeleton (blue) and the roof model.

In geometry, a straight skeleton is a method of representing a polygon by a topological skeleton. It is similar in some ways to the medial axis but differs in that the skeleton is composed of straight line segments, while the medial axis of a polygon may involve parabolic curves. However, both are homotopy-equivalent to the underlying polygon.[1]

Straight skeletons were first defined for simple polygons by Aichholzer et al. (1995),[2] and generalized to planar straight-line graphs (PSLG) by Aichholzer & Aurenhammer (1996).[3] In their interpretation as projection of roof surfaces, they are already extensively discussed by G. A. Peschka (1877).[4]

Definition

[edit]

The straight skeleton of a polygon is defined by a continuous shrinking process in which the edges of the polygon are moved inwards parallel to themselves at a constant speed. As the edges move in this way, the vertices where pairs of edges meet also move, at speeds that depend on the angle of the vertex. If one of these moving vertices collides with a nonadjacent edge, the polygon is split in two by the collision, and the process continues in each part. The straight skeleton is the set of curves traced out by the moving vertices in this process. In the illustration the top figure shows the shrinking process and the middle figure depicts the straight skeleton in blue.

Algorithms

[edit]

The straight skeleton may be computed by simulating the shrinking process by which it is defined; a number of variant algorithms for computing it have been proposed, differing in the assumptions they make on the input and in the data structures they use for detecting combinatorial changes in the input polygon as it shrinks.

The following algorithms consider an input that forms a polygon, a polygon with holes, or a PSLG. For a polygonal input we denote the number of vertices by n and the number of reflex (concave, i.e., angle greater than π) vertices by r. If the input is a PSLG then we consider the initial wavefront structure, which forms a set of polygons, and again denote by n the number of vertices and by r the number of reflex vertices w.r.t. the propagation direction. Most of the algorithms listed here are designed and analyzed in the real RAM model of computation.

  • Aichholzer et al.[2][3] showed how to compute straight skeletons of PSLGs in time O(n3 log n), or more precisely time O((n2+f) log n), where n is the number of vertices of the input polygon and f is the number of flip events during the construction. The best known bound for f is O(n3).
  • An algorithm with a worst case running time in O(nr log n), or simply O(n2 log n), is given by Huber and Held (2010, 2011), who argue that their approach is likely to run in near-linear time for many inputs.[5][6]
  • Petr Felkel and Štěpán Obdržálek designed an algorithm for simple polygons that is said to have an efficiency of O(nr + n log r).[7][8] However, it has been shown that their algorithm is incorrect.[9][10]
  • By using data structures for the bichromatic closest pair problem, Eppstein and Erickson showed how to construct straight skeleton problems using a linear number of closest pair data structure updates. A closest pair data structure based on quadtrees provides an O(nr + n log n) time algorithm, or a significantly more complicated data structure leads to the better asymptotic time bound O(n1 + ε + n8/11 + εr9/11 + ε), or more simply O(n17/11 + ε), where ε is any constant greater than zero.[11] This remains the best worst-case time bound known for straight skeleton construction with unrestricted inputs, but is complicated and has not been implemented.
  • For simple polygons in general position, the problem of straight skeleton construction is easier. Cheng, Mencel, and Vigneron showed how to compute the straight skeleton of simple polygons in time O(n log n log r + r4/3 + ε).[12] In the worst case, r may be on the order of n, in which case this time bound may be simplified to O(n4/3+ε). If the vertices of the input polygon have O(log n)-bit rational coordinates, their algorithm can be improved to run in O(n log n) time, even if the input polygon is not in general position.
  • A monotone polygon with respect to a line L is a polygon with the property that every line orthogonal to L intersects the polygon in a single interval. When the input is a monotone polygon, its straight skeleton can be constructed in time O(n log2 n).[13]

Applications

[edit]

Each point within the input polygon can be lifted into three-dimensional space by using the time at which the shrinking process reaches that point as the z-coordinate of the point. The resulting three-dimensional surface has constant height on the edges of the polygon, and rises at constant slope from them except for the points of the straight skeleton itself, where surface patches at different angles meet. In this way, the straight skeleton can be used as the set of ridge lines of a building roof, based on walls in the form of the initial polygon.[2][14] The bottom figure in the illustration depicts a surface formed from the straight skeleton in this way.

Demaine, Demaine and Lubiw used the straight skeleton as part of a technique for folding a sheet of paper so that a given polygon can be cut from it with a single straight cut (the fold-and-cut theorem), and related origami design problems.[15]

Barequet et al. use straight skeletons in an algorithm for finding a three-dimensional surface that interpolates between two given polygonal chains.[16]

Tănase and Veltkamp propose to decompose concave polygons into unions of convex regions using straight skeletons, as a preprocessing step for shape matching in image processing.[17]

Bagheri and Razzazi use straight skeletons to guide vertex placement in a graph drawing algorithm in which the graph drawing is constrained to lie inside a polygonal boundary.[18]

The straight skeleton can also be used to construct an offset curve of a polygon, with mitered corners, analogously to the construction of an offset curve with rounded corners formed from the medial axis. Tomoeda and Sugihara apply this idea in the design of signage, visible from wide angles, with an illusory appearance of depth.[19] Similarly, Asente and Carr use straight skeletons to design color gradients that match letter outlines or other shapes.[20]

As with other types of skeleton such as the medial axis, the straight skeleton can be used to collapse a two-dimensional area to a simplified one-dimensional representation of the area. For instance, Haunert and Sester describe an application of this type for straight skeletons in geographic information systems, in finding the centerlines of roads.[21][22]

Every tree with no degree-two vertices can be realized as the straight skeleton of a convex polygon.[23] The convex hull of the roof shape corresponding to this straight skeleton forms a Steinitz realization of the Halin graph formed from the tree by connecting its leaves in a cycle.

Higher dimensions

[edit]

Barequet et al. defined a version of straight skeletons for three-dimensional polyhedra, described algorithms for computing it, and analyzed its complexity on several different types of polyhedron.[24]

Huber et al. investigated metric spaces under which the corresponding Voronoi diagrams and straight skeletons coincide. For two dimensions, the characterization of such metric spaces is complete. For higher dimensions, this method can be interpreted as a generalization of straight skeletons of certain input shapes to arbitrary dimensions by means of Voronoi diagrams.[25]

References

[edit]
  1. ^ Huber, Stefan (2018). "The Topology of Skeletons and Offsets" (PDF). Proceedings of the 34th European Workshop on Computational Geometry (EuroCG'18)..
  2. ^ a b c Aichholzer, Oswin; Aurenhammer, Franz; Alberts, David; Gärtner, Bernd (1995). "A novel type of skeleton for polygons". Journal of Universal Computer Science. 1 (12): 752–761. doi:10.1007/978-3-642-80350-5_65. MR 1392429..
  3. ^ a b Aichholzer, Oswin; Aurenhammer, Franz (1996). "Straight skeletons for general polygonal figures in the plane". Proc. 2nd Ann. Int. Conf. Computing and Combinatorics (COCOON '96). Lecture Notes in Computer Science. Vol. 1090. Springer-Verlag. pp. 117–126.
  4. ^ Peschka, Gustav A. (1877). Kotirte Ebenen: Kotirte Projektionen und deren Anwendung; Vorträge. Brünn: Buschak & Irrgang. doi:10.14463/GBV:865177619..
  5. ^ Huber, Stefan; Held, Martin (2010). "Computing straight skeletons of planar straight-line graphs based on motorcycle graphs" (PDF). Proceedings of the 22nd Canadian Conference on Computational Geometry..
  6. ^ Huber, Stefan; Held, Martin (2011). "Theoretical and practical results on straight skeletons of planar straight-line graphs" (PDF). Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SCG'11), June 13–15, 2011, Paris, France. pp. 171–178..
  7. ^ "CenterLineReplacer". FME Transformers. Safe Software. Retrieved 2013-08-05..
  8. ^ Felkel, Petr; Obdržálek, Štěpán (1998). "Straight skeleton implementation". SCCG 98: Proceedings of the 14th Spring Conference on Computer Graphics. pp. 210–218..
  9. ^ Huber, Stefan (2012). Computing Straight Skeletons and Motorcycle Graphs: Theory and Practice. Shaker Verlag. ISBN 978-3-8440-0938-5..
  10. ^ Yakersberg, Evgeny (2004). Morphing Between Geometric Shapes Using Straight-Skeleton-Based Interpolation. Israel Institute of Technology..
  11. ^ Eppstein, David; Erickson, Jeff (1999). "Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions". Discrete and Computational Geometry. 22 (4): 569–592. doi:10.1007/PL00009479. MR 1721026. S2CID 12460625..
  12. ^ Cheng, Siu-Wing; Mencel, Liam; Vigneron, Antoine (2016). "A faster algorithm for computing straight skeletons". ACM Transactions on Algorithms. 12 (3): 44:1–44:21. arXiv:1405.4691. doi:10.1145/2898961..
  13. ^ Biedl, Therese; Held, Martin; Huber, Stefan; Kaaser, Dominik; Palfrader, Peter (February 2015). "A Simple Algorithm for Computing Positively Weighted Straight Skeletons of Monotone Polygons" (PDF). Information Processing Letters. 115 (2): 243–247. doi:10.1016/j.ipl.2014.09.021. PMC 4308025. PMID 25648376. As Biedl et al. point out, an earlier algorithm for monotone polygons by Das et al. is incorrect as described, and at best works only for inputs in general position that do not have vertex-vertex events: Das, Gautam K.; Mukhopadhyay, Asish; Nandy, Subhas C.; Patil, Sangameswar; Rao, S. V. (2010). "Computing the straight skeletons of a monotone polygon in O(n log n) time" (PDF). Proceedings of the 22nd Canadian Conference on Computational Geometry..
  14. ^ Bélanger, David (2000). Designing Roofs of Buildings..
  15. ^ Demaine, Erik D.; Demaine, Martin L.; Lubiw, Anna (1998). "Folding and cutting paper". Revised Papers from the Japan Conference on Discrete and Computational Geometry (JCDCG'98). Lecture Notes in Computer Science. Vol. 1763. Springer-Verlag. pp. 104–117. doi:10.1007/b75044. ISBN 978-3-540-67181-7. S2CID 32962663..
  16. ^ Barequet, Gill; Goodrich, Michael T.; Levi-Steiner, Aya; Steiner, Dvir (2003). "Straight-skeleton based contour interpolation". Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 119–127..
  17. ^ Tănase, Mirela; Veltkamp, Remco C. (2003). "Polygon decomposition based on the straight line skeleton". Proceedings of the 19th Annual ACM Symposium on Computational Geometry. pp. 58–67. doi:10.1145/777792.777802. ISBN 1-58113-663-3. S2CID 18173658..
  18. ^ Bagheri, Alireza; Razzazi, Mohammadreza (2004). "Drawing free trees inside simple polygons using polygon skeleton". Computing and Informatics. 23 (3): 239–254. MR 2165282..
  19. ^ Tomoeda, Akiyasu; Sugihara, Kokichi (2012). "Computational creation of a new illusionary solid sign". Ninth International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2012). pp. 144–147. doi:10.1109/ISVD.2012.26. ISBN 978-1-4673-1910-2. S2CID 27610348..
  20. ^ Asente, Paul; Carr, Nathan (2013). "Creating contour gradients using 3D bevels". Proceedings of the Symposium on Computational Aesthetics (CAE '13, Anaheim, California). New York, NY, USA: ACM. pp. 63–66. doi:10.1145/2487276.2487283. ISBN 978-1-4503-2203-4. S2CID 17302186..
  21. ^ Haunert, Jan-Henrik; Sester, Monika (2008). "Area collapse and road centerlines based on straight skeletons". GeoInformatica. 12 (2): 169–191. doi:10.1007/s10707-007-0028-x. S2CID 2169666..
  22. ^ Raleigh, David Baring (2008). Straight Skeleton Survey Adjustment Of Road Centerlines From Gps Coarse Acquisition Data: A Case Study In Bolivia. Ohio State University, Geodetic Science and Surveying..
  23. ^ Aichholzer, Oswin; Cheng, Howard; Devadoss, Satyan L.; Hackl, Thomas; Huber, Stefan; Li, Brian; Risteski, Andrej (2012). "What makes a tree a straight skeleton?" (PDF). Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG'12)..
  24. ^ Barequet, Gill; Eppstein, David; Goodrich, Michael T.; Vaxman, Amir (2008). "Straight skeletons of three-dimensional polyhedra". Proc. 16th European Symposium on Algorithms. Lecture Notes in Computer Science. Vol. 5193. Springer-Verlag. pp. 148–160. arXiv:0805.0022. doi:10.1007/978-3-540-87744-8_13. ISBN 978-3-540-87743-1. S2CID 42150..
  25. ^ Huber, Stefan; Aichholzer, Oswin; Hackl, Thomas; Vogtenhuber, Birgit (2014). "Straight skeletons by means of Voronoi diagrams under polyhedral distance functions" (PDF). Proc. 26th Canadian Conference on Computational Geometry (CCCG'14)..
[edit]
Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=Straight_skeleton&oldid=1242871491"