Inline videos. See also:Category: Articles with embedded Videos..

Simple polygon

From Biocrawler, the free encyclopedia.

A simple concave hexagon

In geometry, two edges of a polygon may cross or even overlap in general. A simple polygon is a polygon which does not intersect itself anywhere. These 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 polygon that is not simple is a complex polygon, and does not always have a well-defined inside and outside. Convex polygons are simple. A simple polygon is topologically equivalent to a disk.

In computational geometry, there are several important problems where the given input is a simple polygon, each depending critically on its well-defined interior:

Determining if a point falls inside a simple polygon; see Point in polygon
Finding the area contained by a simple polygon; see Polygon area
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.
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

[edit]