Polygonal chain

In geometry, a polygonal chain[a] is a connected series of line segments.

The curve itself consists of the line segments connecting the consecutive vertices.

A simple polygonal chain is one in which only consecutive segments intersect and only at their endpoints.

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.

[2] The graphs of piecewise linear functions form monotone chains with respect to a horizontal line.

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.

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.

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.