Polygonal chain

In geometry, a polygonal chain^[a] is a connected series of line segments. More formally, a polygonal chain ⁠ $P$ ⁠ is a curve specified by a sequence of points $(A_{1},A_{2},\dots ,A_{n})$ 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 the plane is the boundary of a simple polygon. Often the term "polygon" is used in the meaning of "closed polygonal chain", but in some cases it is important to draw a distinction between a polygonal area and a polygonal chain.

Monotone

A set of n=17 points has a polygonal path with 4 same-sign slopes

A polygonal chain is called monotone if there is a straight line L such that every line perpendicular to L intersects the chain at most once. Every nontrivial monotone polygonal chain is open. In comparison, a monotone polygon is a polygon (a closed chain) that can be partitioned into exactly two monotone chains.^[2] The graphs of piecewise linear functions form monotone chains with respect to a horizontal line.

Parametrization

Each segment of a polygonal chain is typically parametrized linearly, using linear interpolation between successive vertices. For the whole chain, two parametrizations are common in practical applications: Each segment of the chain can be assigned a unit interval of the parameter corresponding to the index of the first vertex; alternately, each segment of the chain can be assigned an interval of the parameter corresponding to the length of the segment, so that the parameter corresponds uniformly to arclength along the whole chain.

From point sets

Every set of at least $n$ points contains a polygonal path of at least $\lfloor {\sqrt {n-1}}\rfloor$ 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 computer-aided geometric design, smooth curves are often defined by a list of control points, e.g. in defining Bézier curve segments. When connected together, the control points form a polygonal chain called a control polygon.

Polygonal chains are also a fundamental data type in computational geometry. For instance, a point location algorithm of Lee and Preparata operates by decomposing arbitrary planar subdivisions into an ordered sequence of monotone chains, in which a point location query problem may be solved by binary search; this method was later refined to give optimal time bounds for the point location problem.^[6]

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.

Notes

^ A polygonal chain may also be called a polygonal curve,^[8] polygonal path,^[9] polyline,^[10] piecewise linear curve,^[10] broken line^[11] or, in geographic information systems, a linestring or linear ring.^[7]

References

^ Mehlhorn, Kurt; Näher, Stefan (1999), LEDA: A Platform for Combinatorial and Geometric Computing, Cambridge University Press, p. 758, ISBN 9780521563291.
^ O'Rourke, Joseph (1998), Computational Geometry in C, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, p. 45, ISBN 9780521649766.
^ Ramer, Urs (1972), "An iterative procedure for the polygonal approximation of plane curves", Computer Graphics and Image Processing, 1 (3): 244–256, doi:10.1016/S0146-664X(72)80017-0.
^ Douglas, David; Peucker, Thomas (1973), "Algorithms for the reduction of the number of points required to represent a digitized line or its caricature", The Canadian Cartographer, 10 (2): 112–122, doi:10.3138/FM57-6770-U75U-7727.
^ Tamassia, Roberto (1987), "On embedding a graph in the grid with the minimum number of bends", SIAM Journal on Computing, 16 (3): 421–444, doi:10.1137/0216030.
^ Edelsbrunner, Herbert; Guibas, Leonidas J.; Stolfi, Jorge (1986), "Optimal point location in a monotone subdivision", SIAM Journal on Computing, 15 (2): 317–340, 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
^ Gomes, Jonas; Velho, Luiz; Costa Sousa, Mario (2012), Computer Graphics: Theory and Practice, CRC Press, p. 186, ISBN 9781568815800.
^ Cheney, Ward (2001), Analysis for Applied Mathematics, Graduate Texts in Mathematics, vol. 208, Springer, p. 13, ISBN 9780387952796.
^ ^a ^b Boissonnat, Jean-Daniel; Teillaud, Monique (2006), Effective Computational Geometry for Curves and Surfaces, Springer, p. 34, 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

[Names-1] A polygonal chain may also be called a polygonal curve,^[8] polygonal path,^[9] polyline,^[10] piecewise linear curve,^[10] broken line^[11] or, in geographic information systems, a linestring or linear ring.^[7]

[2] Mehlhorn, Kurt; Näher, Stefan (1999), LEDA: A Platform for Combinatorial and Geometric Computing, Cambridge University Press, p. 758, ISBN 9780521563291.

[3] O'Rourke, Joseph (1998), Computational Geometry in C, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, p. 45, ISBN 9780521649766.

[4] Ramer, Urs (1972), "An iterative procedure for the polygonal approximation of plane curves", Computer Graphics and Image Processing, 1 (3): 244–256, doi:10.1016/S0146-664X(72)80017-0.

[5] Douglas, David; Peucker, Thomas (1973), "Algorithms for the reduction of the number of points required to represent a digitized line or its caricature", The Canadian Cartographer, 10 (2): 112–122, doi:10.3138/FM57-6770-U75U-7727.

[6] Tamassia, Roberto (1987), "On embedding a graph in the grid with the minimum number of bends", SIAM Journal on Computing, 16 (3): 421–444, doi:10.1137/0216030.

[7] Edelsbrunner, Herbert; Guibas, Leonidas J.; Stolfi, Jorge (1986), "Optimal point location in a monotone subdivision", SIAM Journal on Computing, 15 (2): 317–340, doi:10.1137/0215023.

[OGC-8] 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

[ref1-9] Gomes, Jonas; Velho, Luiz; Costa Sousa, Mario (2012), Computer Graphics: Theory and Practice, CRC Press, p. 186, ISBN 9781568815800.

[ref2-10] Cheney, Ward (2001), Analysis for Applied Mathematics, Graduate Texts in Mathematics, vol. 208, Springer, p. 13, ISBN 9780387952796.

[ecg-11] Boissonnat, Jean-Daniel; Teillaud, Monique (2006), Effective Computational Geometry for Curves and Surfaces, Springer, p. 34, ISBN 9783540332596.

[ref4-12] 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

[a]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]