- Straight skeleton
In
geometry , a straight skeleton is a method of representing apolygon by atopological skeleton . It is similar in some ways to themedial axis but differs in that the skeleton is composed of straight line segments, while the medial axis of a polygon may involve parabolic curves.The straight skeleton 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.
Straight skeletons were first defined for simple polygons by Aichholzer et al.,cite journal
author = Aichholzer, Oswin; Aurenhammer, Franz; Alberts, David; Gärtner, Bernd
journal = Journal of Universal Computer Science
title = A novel type of skeleton for polygons
volume = 1
issue = 12
pages = 752–761
id = MathSciNet | id = 1392429
url = http://www.jucs.org/jucs_1_12/a_novel_type_of
year=1995] and generalized toplanar straight line graph s by Aichholzer and Aurenhammer.cite conference
author = Aichholzer, Oswin; Aurenhammer, Franz
title = Straight skeletons for general polygonal figures in the plane
booktitle = Proc. 2nd Ann. Int. Conf. Computing and Combinatorics (COCOON '96)
publisher = Lecture Notes in Computer Science, no. 1090, Springer-Verlag
pages = 117–126
url = http://www.igi.tugraz.at/auren/psfiles/aa-ssgpf-98.ps.gz
date = 1996] Cheng and Vigneron showed how to compute the straight skeleton of a simple polygon with "n" vertices, "r" of which have angles greater thanPi ; in time O("n" log2 "n" + "r"3/2 log "r").cite conference
author = Cheng, Siu-Wing; Vigneron, Antoine
title = Motorcycle graphs and straight skeletons
booktitle = Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms
date = 2002
pages = 156–165
url = http://www.cs.ust.hk/~scheng/pub/motorpub.pdf] For more general polygonal inputs, the best known time bound is from a more complex and slower algorithm by Eppstein and Erickson.cite journal
author = Eppstein, David; Erickson, Jeff
title = Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions
journal = Discrete & Computational Geometry
volume = 22
issue = 4
pages = 569–592
url = http://compgeom.cs.uiuc.edu/~jeffe/pubs/pdf/cycles.pdf
doi = 10.1007/PL00009479
id = MathSciNet | id = 1721026
year = 1999]Example
The illustration shows:
# a straight skeleton (non bold) of asimple polygon (bold)
# the shrinking process that, when taken to its limit, creates the skeleton
# a 3d interpretation of the same skeleton, a 'roof' structureApplications
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.cite web
author = Bélanger, David
title = Designing Roofs of Buildings
year = 2000
url = http://www.sable.mcgill.ca/~dbelan2/roofs/roofs.html]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.cite conference
author = Demaine, Erik D.; Demaine, Martin L.; Lubiw, Anna
title = Folding and cutting paper
booktitle = Revised Papers from the Japan Conference on Discrete and Computational Geometry (JCDCG'98)
publisher = Lecture Notes in Computer Science, no. 1763, Springer-Verlag
pages = 104–117
date = 1998
doi = 10.1007/b75044
url = http://theory.lcs.mit.edu/~edemaine/papers/JCDCG98/]Barequet et al. use straight skeletons in an algorithm for finding a three-dimensional surface that interpolates between two given
polygonal curve s.cite conference
author = Barequet, Gill; Goodrich, Michael T.; Levi-Steiner, Aya; Steiner, Dvir
title = Straight-skeleton based contour interpolation
booktitle = Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms
pages = 119–127
url = http://www.cs.technion.ac.il/~barequet/teaching/cg/sp01/project/papers/Barequet-Goodrich.ps.gz
date = 2003]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.cite conference
author = Tănase, Mirela; Veltkamp, Remco C.
title = Polygon decomposition based on the straight line skeleton
booktitle = Proceedings of the 19th Annual ACM Symposium on Computational Geometry
date = 2003
doi = 10.1145/777792.777802
pages = 58–67]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.cite journal
author = Bagheri, Alireza; Razzazi, Mohammadreza
title = Drawing free trees inside simple polygons using polygon skeleton
journal = Computing and Informatics
volume = 23
year = 2004
issue = 3
pages = 239–254
id = MathSciNet | id=2165282]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.
References
External links
*cite web
author = Erickson, Jeff
title = Straight Skeleton of a Simple Polygon
url = http://compgeom.cs.uiuc.edu/~jeffe/open/skeleton.html
* [http://www.cgal.org/Pkg/StraightSkeleton2 2D Straight Skeleton] inCGAL , the Computational Geometry Algorithms Library
Wikimedia Foundation. 2010.
