Simple Polygon - Computational Problems

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