Sources
open directory project
Help build the largest human-edited directory on the web.
Submit a site - Become an editor
Wikipedia. Licensed under the GNU Free Documentation License.
Are you an expert in this subject? Join the discussion and share your knowledge at Wikipedia.org.
Simple polygon
From Wikipedia, the free encyclopedia
In geometry, two edges of a polygon may cross or even overlap in general. A simple polygon is a polygon which its sides do not intersect. 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. 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
- Convex hull of a simple polygon.
- Eric W. Weisstein, Simple polygon at MathWorld.