# Simple polygon

In geometry, a **simple polygon** is a polygon whose sides do not cross. That is, its boundary is a closed polygonal chain of line segments that do not cross each other. The term *simple polygon* often refers to the boundary alone.

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.

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.

## Contents

## Applications in computational geometry

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

### Software

- General Polygon Clipper (GPC), a C++ library which computes the results of clipping operations (difference, intersection, exclusive-or and union) on sets of polygons. It is usable with C, C#, Delphi, Java, Perl, Python, Haskell, Lua, VB.Net.

## External links

### Software

- The comp.graphics.algorithms FAQ, which lists solutions to mathematical problems with 2D and 3D Polygons.