Jump to content

Straight skeleton

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by David Eppstein (talk | contribs) at 19:02, 22 November 2013 (Undid revision 582840475 by 5.52.227.99 (talk) WP:REFSPAM). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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.

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

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. In the illustration the top figure shows the shrinking process and the middle figure depicts the straight skeleton in blue.

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 structures they use for detecting combinatorial changes in the input polygon as it shrinks.

  • Aichholzer et al.[1][2] showed how to compute straight skeletons for arbitrary two-dimensional inputs 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, who argue that their approach is likely to run in near-linear time for many inputs.[4]
  • Petr Felkel and Štěpán Obdržálek designed an algorithm that is said to have an efficiency of O(nr + n log r).[5][6] However, it has been reported that their algorithm is incorrect.[7][8]
  • 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.[9] 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, 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 log2 n + r3/2 log r).[10] In the worst case, r may be linear, in which case this time bound may be simplified to O(n3/2 log n).
  • 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 log n).[11]

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.[1][12] 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.[13]

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

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.[15]

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.[16]

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.[17] Similarly, Asente and Carr use straight skeletons to design color gradients that match letter outlines or other shapes.[18]

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.[19][20]

Higher dimensions

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.[21]

References

  1. ^ 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. MR 1392429.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  2. ^ 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, no. 1090, Springer-Verlag. pp. 117–126. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)CS1 maint: multiple names: authors list (link)
  3. ^ Peschka, Gustav A. (1877). Kotirte Ebenen: Kotirte Projektionen und deren Anwendung; Vorträge. Brno: Buschak & Irrgang.
  4. ^ 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. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help) Huber, Stefan; Held, Martin (2011). "Theoretical and practical results on straight skeletons of planar straight-line graphs". Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SCG'11), June 13–15, 2011, Paris, France. pp. 171–178. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help).
  5. ^ "CenterLineReplacer". FME Transformers. Safe Software. Retrieved 2013-08-05.
  6. ^ 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. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
  7. ^ Huber, Stefan (2012). Computing Straight Skeletons and Motorcycle Graphs: Theory and Practice. Shaker Verlag. ISBN 978-3-8440-0938-5.
  8. ^ Yakersberg, Evgeny (2004). Morphing Between Geometric Shapes Using Straight-Skeleton-Based Interpolation. Masters thesis. Israel Institute of Technology.
  9. ^ Eppstein, David; Erickson, Jeff (1999). "Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions" (PDF). Discrete & Computational Geometry. 22 (4): 569–592. doi:10.1007/PL00009479. MR 1721026.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  10. ^ Cheng, Siu-Wing; Vigneron, Antoine (2002). "Motorcycle graphs and straight skeletons" (PDF). Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 156–165. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)CS1 maint: multiple names: authors list (link)
  11. ^ 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. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)CS1 maint: multiple names: authors list (link)
  12. ^ Bélanger, David (2000). "Designing Roofs of Buildings".
  13. ^ 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, no. 1763, Springer-Verlag. pp. 104–117. doi:10.1007/b75044. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)CS1 maint: multiple names: authors list (link)
  14. ^ 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. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)CS1 maint: multiple names: authors list (link)
  15. ^ 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. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)CS1 maint: multiple names: authors list (link)
  16. ^ Bagheri, Alireza; Razzazi, Mohammadreza (2004). "Drawing free trees inside simple polygons using polygon skeleton". Computing and Informatics. 23 (3): 239–254. MR 2165282.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  17. ^ 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.
  18. ^ 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.
  19. ^ 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.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  20. ^ Raleigh, David Baring (2008). Straight Skeleton Survey Adjustment Of Road Centerlines From Gps Coarse Acquisition Data: A Case Study In Bolivia. Masters thesis. Ohio State University, Geodetic Science and Surveying.
  21. ^ 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. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)CS1 maint: multiple names: authors list (link)
Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=Straight_skeleton&oldid=582853197"