In
geometry
Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
, a polygonal chain is a connected series of
line segment
In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between ...
s. More formally, a polygonal chain is a
curve
In mathematics, a curve (also called a curved line in older texts) is an object similar to a line (geometry), line, but that does not have to be Linearity, straight.
Intuitively, a curve may be thought of as the trace left by a moving point (ge ...
specified by a
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
of points
called its
vertices. The curve itself consists of the line segments connecting the consecutive vertices.
Name
A polygonal chain may also be called a polygonal curve, polygonal path, polyline,
[.] piecewise linear curve,
broken line or, in
geographic information system
A geographic information system (GIS) is a type of database containing Geographic data and information, geographic data (that is, descriptions of phenomena for which location is relevant), combined with Geographic information system software, sof ...
s, a linestring or linear ring.
Variations
A simple polygonal chain is one in which only consecutive (or the first and the last) 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.
A simple closed polygonal chain in
the plane
In mathematics, a plane is a Euclidean (flat), two-dimensional surface that extends indefinitely. A plane is the two-dimensional analogue of a point (zero dimensions), a line (one dimension) and three-dimensional space. Planes can arise as ...
is the boundary of a
simple polygon
In geometry, a simple polygon is a polygon that does not Intersection (Euclidean geometry), intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pairwise ...
. Often the term "
polygon
In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed ''polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two toge ...
" 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.
A polygonal chain is called monotone if there is a
straight line
In geometry, a line is an infinitely long object with no width, depth, or curvature. Thus, lines are One-dimensional space, one-dimensional objects, though they may exist in Two-dimensional Euclidean space, two, Three-dimensional space, three, ...
''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
In geometry, a polygon ''P'' in the plane is called monotone with respect to a straight line ''L'', if every line orthogonal to ''L'' intersects the boundary of ''P'' at most twice.
Similarly, a polygonal chain ''C'' is called monotone with respec ...
is a polygon (a closed chain) that can be partitioned into exactly two monotone chains. The graphs of
piecewise linear functions form monotone chains with respect to a horizontal line.
Properties
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
In mathematics, the Erdős–Szekeres theorem asserts that, given ''r'', ''s,'' any sequence of distinct real numbers with length at least (''r'' − 1)(''s'' − 1) + 1 contains a monotonically increasing su ...
.
Applications
Polygonal chains can often be used to approximate more complex curves. In this context, the
Ramer–Douglas–Peucker algorithm The Ramer–Douglas–Peucker algorithm, also known as the Douglas–Peucker algorithm and iterative end-point fit algorithm, is an algorithm that decimates a curve composed of line segments to a similar curve with fewer points. It was one of the e ...
can be used to find a polygonal chain with few segments that serves as an accurate approximation.
In
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 graph (discrete mathematics), graphs arising from applications such a ...
, 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
In graph drawing styles that represent the edges of a graph by polylines (sequences of line segments connected at bends), it is desirable to minimize the number of bends per edge (sometimes called the curve complexity). or the total number of bend ...
.
Polygonal chains are also a fundamental data type in
computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...
. For instance, a
point location
The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided ...
algorithm of
Lee and
Preparata operates by decomposing arbitrary
planar subdivision
In computational geometry and geometric graph theory, a planar straight-line graph, in short ''PSLG'', (or ''straight-line plane graph'', or ''plane straight-line graph'') is a term used for an embedding of a planar graph in the plane such that it ...
s into an ordered sequence of monotone chains, in which a point location query problem may be solved by
binary search
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the m ...
; this method was later refined to give optimal time bounds for the point location problem.
[.]
With
geographic information system
A geographic information system (GIS) is a type of database containing Geographic data and information, geographic data (that is, descriptions of phenomena for which location is relevant), combined with Geographic information system software, sof ...
, linestrings may represent any linear geometry, and can be described using the
well-known text markup as a
LineString
or
MultiLineString
.
Linear rings (or
LinearRing
) are closed and simple polygonal chains used to build polygon geometries.
See also
*
Chain (algebraic topology)
In algebraic topology, a -chain
is a formal linear combination of the -cells in a cell complex. In simplicial complexes (respectively, cubical complexes), -chains are combinations of -simplices (respectively, -cubes), but not necessarily connected ...
, a formal combination of simplices that in the 1-dimensional case includes polygonal chains
*
Composite Bézier curve
In geometric modelling and in computer graphics, a composite Bézier curve or Bézier spline is a spline made out of Bézier curves that is at least C^0 continuous. In other words, a composite Bézier curve is a series of Bézier curves joined ...
, a generalization that replaces each straight line of a polygonal chain with a smooth curve.
*
Link distance In computational geometry, the link distance between two points in a polygon is the minimum number of line segments of any polygonal chain within the polygon that has the two points as its endpoints. The link diameter of the polygon is the maximum ...
, the number of segments of the shortest chain that links two points within a polygon
*
Piecewise regression
Segmented regression, also known as piecewise regression or broken-stick regression, is a method in regression analysis in which the independent variable is partitioned into intervals and a separate line segment is fit to each interval. Segmented r ...
*
Path (graph theory)
In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct (and since the vertices are distinct, so are the edges). A directed path (sometimes c ...
, an analogous concept in abstract graphs
*
Polyhedral terrain
In computational geometry, a polyhedral terrain in three-dimensional Euclidean space is a polyhedral surface that intersects every line parallel to some particular line in a connected set (i.e., a point or a line segment) or the empty set. Withou ...
, a 3D generalization of a monotone polygonal chain
*
Spirangle
In geometry, a spirangle is a figure related to a spiral. Spirangles are similar to spirals in that they expand from a center point as they grow larger, but they are made out of straight line segments, instead of curves. Spirangle vectographs ...
, a spiral polygonal chain
*
Stick number, a knot invariant based on representing a knot as a closed polygonal chain
*
Traverse, application in
surveying
Surveying or land surveying is the technique, profession, art, and science of determining the terrestrial two-dimensional or three-dimensional positions of points and the distances and angles between them. A land surveying professional is ca ...
References
{{reflist
Polygons
Curves