Straight skeleton
Encyclopedia
Geometry
Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....
, a straight skeleton is a method of representing a polygon
Polygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...
by a topological skeleton
Topological skeleton
In shape analysis, skeleton of a shape is a thin version of that shape that is equidistant to its boundaries. The skeleton usually emphasizes geometrical and topological properties of the shape, such as its connectivity, topology, length, direction, and width...
. It is similar in some ways to the medial axis
Medial axis
The medial axis of an object is the set of all points having more than one closest point on the object's boundary. Originally referred to as the topological skeleton, it was introduced by Blum as a tool for biological shape recognition....
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., and generalized to planar straight line graphs by Aichholzer and Aurenhammer.
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.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
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 structureData structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s they use for detecting combinatorial changes in the input polygon as it shrinks.
- Aichholzer et al. showed how to compute straight skeletons for arbitrary two-dimensional inputs in time O(n2 log n), or more strongly in time O(nr log 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.
- By using data structures for the bichromatic closest pair problemClosest pair of points problemThe closest pair of points problem or closest pair problem is a problem of computational geometry: given n points in metric space, find a pair of points with the smallest distance between them...
, EppsteinDavid EppsteinDavid Arthur Eppstein is an American computer scientist and mathematician. He is professor of computer science at University of California, Irvine. He is known for his work in computational geometry, graph algorithms, and recreational mathematics.-Biography:Born in England of New Zealander...
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 quadtreeQuadtreeA quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular, or may have arbitrary shapes. This...
s provides an O(nr + n log n) time algorithm, or a significantly more complicated data structure leads to the better asymptotic time bound , or more simply , 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 polygonSimple polygonIn geometry, a simple polygon is a closed polygonal chain of line segments in the plane which do not have points in common other than the common vertices of pairs of consecutive segments....
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 PiPi' is a mathematical constant that is the ratio of any circle's circumference to its diameter. is approximately equal to 3.14. Many formulae in mathematics, science, and engineering involve , which makes it one of the most important mathematical constants...
, in time O(n log2 n + r3/2 log r). 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 polygonMonotone polygonIn geometry, a polygon P in the plane is called monotone with respect to a straight line L, if every line orthogonal to L intersects P at most twice....
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).
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. Part (iii) of 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
Origami
is the traditional Japanese art of paper folding, which started in the 17th century AD at the latest and was popularized outside Japan in the mid-1900s. It has since then evolved into a modern art form...
design problems.
Barequet et al. use straight skeletons in an algorithm for finding a three-dimensional surface that interpolates between two given polygonal curves.
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.
Bagheri and Razzazi use straight skeletons to guide vertex placement in a graph drawing
Graph drawing
Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...
algorithm in which the graph drawing is constrained to lie inside a polygonal boundary.
The straight skeleton can also be used to construct an offset curve
Parallel (curve)
A parallel of a curve is the envelope of a family of congruent circles centered on the curve. It generalises the concept of parallel lines. It can also be defined as a curve whose points are at a fixed normal distance of a given curve....
of a polygon, with mitered corners
Miter joint
A miter joint , sometimes shortened to miter, is a joint made by bevelling each of two parts to be joined, usually at a 45° angle, to form a corner, usually a 90° angle...
, analogously to the construction of an offset curve with rounded corners formed from the medial axis.
As with other types of skeleton such as the medial axis
Medial axis
The medial axis of an object is the set of all points having more than one closest point on the object's boundary. Originally referred to as the topological skeleton, it was introduced by Blum as a tool for biological shape recognition....
, 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
Geographic Information System
A geographic information system, geographical information science, or geospatial information studies is a system designed to capture, store, manipulate, analyze, manage, and present all types of geographically referenced data...
s, in finding the centerlines of roads.
Higher dimensions
Barequet et al. defined a version of straight skeletons for three-dimensional polyhedraPolyhedron
In elementary geometry a polyhedron is a geometric solid in three dimensions with flat faces and straight edges...
, described algorithms for computing it, and analyzed its complexity on several different types of polyhedron.
External links
- 2D Straight Skeleton in CGALCGALThe Computational Geometry Algorithms Library is a software library that aims to provide easy access to efficient and reliable algorithms in computational geometry. While primarily written in C++, Python and Scilab bindings are also available....
, the Computational Geometry Algorithms Library - Straight Skeleton for polygon with holes Straight Skeleton builder implemented in java.