Straight skeleton

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.

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. (1995), and generalized to planar straight line graphs by Aichholzer and Aurenhammer (1996). Cheng and Vigneron (2002) showed how to compute the straight skeleton of a simple polygon with n vertices, r of which have angles greater than π in time O(n log² n + r^3/2 log r). For more general polygonal inputs, the best known time bound is from a more complex and slower algorithm by Eppstein and Erickson (1999).

Example

The illustration shows:

a straight skeleton (non bold) of a simple polygon (bold)
the shrinking process that, when taken to its limit, creates the skeleton
a 3d interpretation of the same skeleton, a 'roof' structure

Applications

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 (Aichholzer et al. 1995; Bélanger 2000).

Demaine, Demaine and Lubiw (1998) 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.

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

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

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

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)

Aichholzer, Oswin; Aurenhammer, Franz; Alberts, David; Gärtner, Bernd. "A novel type of skeleton for polygons". Journal of Universal Computer Science. 1 (12): 752–761.{{cite journal}}: CS1 maint: multiple names: authors list (link)

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)

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)

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)

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.{{cite journal}}: CS1 maint: multiple names: authors list (link)

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)

External links

Bélanger, David (2000). "Designing Roofs of Buildings".

Erickson, Jeff. "Straight Skeleton of a Simple Polygon".