Simple polygon

A simple concave hexagon

A non-simple (complex) pentagon.

In geometry, a simple polygon is a closed polygonal chain of line segments in the plane which do not have points in common other than the common vertices of pairs of consecutive segments.

A polygon that is not simple is called self-intersecting by geometers and complex by computer graphics programmers (in geometry, a complex polygon is something different). Such a polygon does not necessarily have a well-defined inside and outside.

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. Informally, a weakly simple polygon is a polygon in which some sides can "touch" but cannot "cross over".

            A----------B
            |xxxxxxxxxx|
            |xH-----Gxx|
            |x|     |xx|
            |x|     |xx|
            |xJ-K,E-Fxx|
            |xxxx|xxxxx|
            M---L,D----C

In the ASCII art above, ABCDEFGHJKLM is a weakly simple polygon with 'x'-es 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 Hausdorff metric. They not necessarily define an "interior". For example, referring to the ASCII art 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 ASCII art 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.

• 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.
• Polygon union: finding the simple polygon or polygons containing the area inside either of two simple polygons
• Polygon intersection: finding the simple polygon or polygons containing the area inside both of two simple polygons
• The convex hull of a simple polygon may be computed more efficiently than the complex hull of other types of inputs, such as the convex hull of a point set.

See also

• Star domain

External links

• Weisstein, Eric W. "Simple polygon". MathWorld.