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. Straight skeletons were first defined for simple polygons by Aichholzer et al. (1995), and generalized to planar straight-line graphs (PSLG) by Aichholzer & Aurenhammer (1996). In their interpretation as projection of roof surfaces, they are already extensively discussed by G. A. Peschka (1877).
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. 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. 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. 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). However, it has been shown that their algorithm is incorrect. 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. 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 + ε). 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).
… excerpt ends here. Continue reading the full article.
