Simple Polygon
   HOME

TheInfoList



OR:

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 simple polygon is a
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 ...
that does not intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting
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 or "sides" that are joined pairwise to form a single closed path. If the sides intersect then the polygon is not simple. The qualifier "simple" is frequently omitted, with the above definition then being understood to define a polygon in general. The definition given above ensures the following properties: * A polygon encloses a
region In geography, regions, otherwise referred to as zones, lands or territories, are areas that are broadly divided by physical characteristics (physical geography), human impact characteristics (human geography), and the interaction of humanity and t ...
(called its interior) which always has a measurable
area Area is the quantity that expresses the extent of a region on the plane or on a curved surface. The area of a plane region or ''plane area'' refers to the area of a shape A shape or figure is a graphics, graphical representation of an obje ...
. * The line segments that make up a polygon (called sides or edges) meet only at their endpoints, called vertices (singular: vertex) or less formally "corners". * Exactly two edges meet at each vertex. * The number of edges always equals the number of vertices. Two edges meeting at a corner are usually required to form an
angle In Euclidean geometry, an angle is the figure formed by two Ray (geometry), rays, called the ''Side (plane geometry), sides'' of the angle, sharing a common endpoint, called the ''vertex (geometry), vertex'' of the angle. Angles formed by two ...
that is not straight (180°); otherwise, the
collinear In geometry, collinearity of a set of points is the property of their lying on a single line. A set of points with this property is said to be collinear (sometimes spelled as colinear). In greater generality, the term has been used for aligned ...
line segments will be considered parts of a single side. Mathematicians typically use "polygon" to refer only to the shape made up by the line segments, not the enclosed region, however some may use "polygon" to refer to a
plane Plane(s) most often refers to: * Aero- or airplane, a powered, fixed-wing aircraft * Plane (geometry), a flat, 2-dimensional surface Plane or planes may also refer to: Biology * Plane (tree) or ''Platanus'', wetland native plant * ''Planes' ...
figure Figure may refer to: General *A shape, drawing, depiction, or geometric configuration *Figure (wood), wood appearance *Figure (music), distinguished from musical motif *Noise figure, in telecommunication *Dance figure, an elementary dance pattern ...
that is bounded by a closed path, composed of a finite sequence of straight line segments (i.e., by a closed polygonal chain). According to the definition in use, this boundary may or may not form part of the polygon itself. Simple polygons are also called Jordan polygons, because the
Jordan curve theorem In topology, the Jordan curve theorem asserts that every ''Jordan curve'' (a plane simple closed curve) divides the plane into an " interior" region bounded by the curve and an "exterior" region containing all of the nearby and far away exterior ...
can be used to prove that such a polygon divides the plane into two regions, the region inside it and the region outside it. A polygon in the plane is simple if and only if it is
topologically equivalent In mathematics, two functions are said to be topologically conjugate if there exists a homeomorphism that will conjugate the one into the other. Topological conjugacy, and related-but-distinct of flows, are important in the study of iterated fun ...
to a
circle A circle is a shape consisting of all points in a plane that are at a given distance from a given point, the centre. Equivalently, it is the curve traced out by a point that moves in a plane so that its distance from a given point is const ...
. Its interior is topologically equivalent to a
disk Disk or disc may refer to: * Disk (mathematics), a geometric shape * Disk storage Music * Disc (band), an American experimental music band * ''Disk'' (album), a 1995 EP by Moby Other uses * Disk (functional analysis), a subset of a vector sp ...
.


Weakly simple polygon

If a collection of non-crossing line segments forms the boundary of a region of the plane that is topologically equivalent to a disk, then this boundary is called a weakly simple polygon. In the image on the left, ABCDEFGHJKLM is a weakly simple polygon according to this definition, with the color blue marking the region for which it is the boundary. This type of weakly simple polygon can arise in computer graphics and
CAD Computer-aided design (CAD) is the use of computers (or ) to aid in the creation, modification, analysis, or optimization of a design. This software is used to increase the productivity of the designer, improve the quality of design, improve co ...
as a computer representation of polygonal regions with holes: for each hole a "cut" is created to connect it to an external boundary. Referring to the image above, ABCM is an external boundary of a planar region with a hole FGHJ. The cut ED connects the hole with the exterior and is traversed twice in the resulting weakly simple polygonal representation. In an alternative and more general definition of weakly simple polygons, they are the limits of sequences of simple polygons of the same combinatorial type, with the convergence under the
Fréchet distance In mathematics, the Fréchet distance is a measure of similarity between curves that takes into account the location and ordering of the points along the curves. It is named after Maurice Fréchet. Intuitive definition Imagine a person traversin ...
. This formalizes the notion that such a polygon allows segments to touch but not to cross. However, this type of weakly simple polygon does not need to form the boundary of a region, as its "interior" can be empty. For example, referring to the image above, the polygonal chain ABCBA is a weakly simple polygon according to this definition: it may be viewed as the limit of "squeezing" of the polygon ABCFGHA.


Computational problems

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 ...
, several important computational tasks involve inputs in the form of a simple polygon; in each of these problems, the distinction between the interior and exterior is crucial in the problem definition. *
Point in polygon In computational geometry, the point-in-polygon (PIP) problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon. It is a special case of point location problems and finds applications in areas that deal ...
testing involves determining, for a simple polygon ''P'' and a query point ''q'', whether ''q'' lies interior to ''P''. * Simple formulae are known for computing
polygon area 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 tog ...
; that is, the area of the interior of the polygon. * Polygon partition is a set of primitive units (e.g. squares), which do not overlap and whose union equals the polygon. A polygon partition problem is a problem of finding a partition which is minimal in some sense, for example: a partition with a smallest number of units or with units of smallest total side-length. Se
25">"Other decompositions", p. 19-25
** A special case of polygon partition is
Polygon triangulation In computational geometry, polygon triangulation is the partition of a polygonal area (simple polygon) into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is . Triangulations may be v ...
: dividing a simple polygon into triangles. Although convex polygons are easy to triangulate, triangulating a general simple polygon is more difficult because we have to avoid adding edges that cross outside the polygon. Nevertheless,
Bernard Chazelle Bernard Chazelle (born November 5, 1955) is a French-American computer scientist. He is currently the Eugene Higgins Professor of Computer Science at Princeton University. Much of his work is in computational geometry, where he is known for hi ...
showed in 1991 that any simple polygon with ''n'' vertices can be triangulated in Θ(''n'') time, which is optimal. The same algorithm may also be used for determining whether a closed polygonal chain forms a simple polygon. ** Another special case is the
art gallery problem The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from the following real-world problem: In the geometric version of the problem, the layout of the art gallery is represente ...
, which can be equivalently reformulated as a partition into a minimum number of
star-shaped polygon In geometry, a star-shaped polygon is a polygonal region in the plane that is a star domain, that is, a polygon that contains a point from which the entire polygon boundary is visible. Formally, a polygon is star-shaped if there exists a poi ...
s. *
Boolean operations on polygons Boolean operations on polygons are a set of Boolean operations (AND, OR, NOT, XOR, ...) operating on one or more sets of polygons in computer graphics. These sets of operations are widely used in computer graphics, CAD, and in EDA (in integrated ci ...
: Various Boolean operations on the sets of points defined by polygonal regions. *The
convex hull In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
of a simple polygon may be computed more efficiently than the convex hull of other types of inputs, such as the convex hull of a point set. *
Voronoi diagram In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed th ...
of a simple polygon *
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 in 1967 by Harry Blum as a tool for biological shape recogn ...
/
topological skeleton In shape analysis, skeleton (or topological 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, ...
/
straight skeleton In geometry, a straight skeleton is a method of representing a polygon by a topological skeleton. It is similar in some ways to the medial axis but differs in that the skeleton is composed of straight line segments, while the medial axis of a pol ...
of a simple polygon * Offset curve of a simple polygon *
Minkowski sum In geometry, the Minkowski sum (also known as dilation) of two sets of position vectors ''A'' and ''B'' in Euclidean space is formed by adding each vector in ''A'' to each vector in ''B'', i.e., the set : A + B = \. Analogously, the Minkowski ...
for simple polygons


See also

*
Simple curve In mathematics, a curve (also called a curved line in older texts) is an object similar to a line, but that does not have to be straight. Intuitively, a curve may be thought of as the trace left by a moving point. This is the definition that ...


References


External links

* {{Polygons Types of polygons