Simple polygon

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Some simple polygons.

In geometry a simple polygon /ˈpɒlɪɡɒn/ is defined as a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pair-wise to form a 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 (called its interior) which always has a measurable area.
  • 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 that is not straight (180°); otherwise, the collinear 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 figure 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.[1]

Simple polygons are also called Jordan polygons, because the Jordan curve theorem 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 simple polygon in the plane is topologically equivalent to a circle and its interior is topologically equivalent to a disk.

Weakly simple polygon[edit]

Weakly simple polygon.svg

If a closed polygonal chain embedded in the plane divides it into two regions one of which is topologically equivalent to a disk, then the chain is called a weakly simple polygon.[2] Informally, a weakly simple polygon is a polygon in which some sides can "touch" but cannot "cross over".

In the image on the left, ABCDEFGHJKLM is a weakly simple polygon with the color blue marking its interior.

In a 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.[3] The "interior" can be empty. For example, referring to the image above, the polygonal chain ABCBA is a weakly simple polygon: it may be viewed as the limit of "squeezing" of the polygon ABCFGHA.

Non-simple weakly simple polygons arise in computer graphics and CAD 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.

Computational problems[edit]

In computational geometry, 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.[4]

  • Point in polygon 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; that is, the area of the interior of the polygon.
  • Polygon triangulation: 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 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.
  • Boolean operations on polygons: Various Boolean operations on the sets of points defined by polygonal regions.
  • The convex hull 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 of a simple polygon
  • Medial axis/topological skeleton/straight skeleton of a simple polygon
  • Offset curve of a simple polygon
  • Minkowski sum for simple polygons

See also[edit]


  1. ^ Grünbaum, B.; Convex polytopes 2nd Ed, Springer, 2003
  2. ^ Wolfgang Thomas, Pascal Weil (2007). STACS 2007: 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings (illustrated ed.). Springer. p. 177. ISBN 3540709177. 
  3. ^ Hsien-Chih Chang, Jeff Erickson, Chao Xu (2015). Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15). p. 1655-1670. 
  4. ^ The FAQ, which lists solutions to mathematical problems with 2D and 3D polygons.

External links[edit]