Polygonal chain
In geometry, a polygonal chain[a] is a connected series of line segments. More formally, a polygonal chain is a curve specified by a sequence of points called its vertices. The curve itself consists of the line segments connecting the consecutive vertices.
Variations
Simple
A simple polygonal chain is one in which only consecutive segments intersect and only at their endpoints.
Closed
A closed polygonal chain is one in which the first vertex coincides with the last one, or, alternatively, the first and the last vertices are also connected by a line segment.[1] A simple closed polygonal chain in
Monotone
A polygonal chain is called monotone if there is a
Parametrization
Each segment of a polygonal chain is typically
From point sets
Every set of at least points contains a polygonal path of at least edges in which all slopes have the same sign. This is a corollary of the Erdős–Szekeres theorem.
Applications
Polygonal chains can often be used to approximate more complex curves. In this context, the Ramer–Douglas–Peucker algorithm can be used to find a polygonal chain with few segments that serves as an accurate approximation.[3][4]
In graph drawing, polygonal chains are often used to represent the edges of graphs, in drawing styles where drawing the edges as straight line segments would cause crossings, edge-vertex collisions, or other undesired features. In this context, it is often desired to draw edges with as few segments and bends as possible, to reduce the visual clutter in the drawing; the problem of minimizing the number of bends is called bend minimization.[5]
In
Polygonal chains are also a fundamental data type in
With geographic information system, linestrings may represent any linear geometry, and can be described using the well-known text markup as a LineString
or MultiLineString
.[7] Linear rings (or LinearRing
) are closed and simple polygonal chains used to build polygon geometries.
See also
- Chain (algebraic topology), a formal combination of simplices that in the 1-dimensional case includes polygonal chains
- Composite Bézier curve, a generalization that replaces each straight line of a polygonal chain with a smooth curve.
- Link distance, the number of segments of the shortest chain that links two points within a polygon
- Piecewise regression
- Path (graph theory), an analogous concept in abstract graphs
- Polyhedral terrain, a 3D generalization of a monotone polygonal chain
- Spirangle, a spiral polygonal chain
- Stick number, a knot invariant based on representing a knot as a closed polygonal chain
- Traverse, application in surveying
Notes
References
- ISBN 9780521563291.
- ISBN 9780521649766.
- .
- .
- doi:10.1137/0216030.
- doi:10.1137/0215023.
- ^ a b Open Geospatial Consortium (2011-05-28), Herring, John R. (ed.), OpenGIS® Implementation Standard for Geographic information - Simple feature access - Part 1: Common architecture, 1.2.1, Open Geospatial Consortium, retrieved 2016-01-15
- ISBN 9781568815800.
- ISBN 9780387952796.
- ^ ISBN 9783540332596.
- ^ Muggeo, Vito M. R. (May 2008), "segmented: An R package to fit regression models with broken-line relationships" (PDF), R News, 8 (1): 20–25