# Simple polygon

Some simple polygons.

In geometry a simple polygon 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

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

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
• Polygon resizing
• Minkowski sum for simple polygons