abstract
| - 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. 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.
|