In geometry, a simple polygon is a polygon whose sides do not intersect. They 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 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.
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
- Convex hull of a simple polygon.
See Also
Software
- GPC General Polygon Clipper Library, 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
