All Topics  
Simple polygon

 

 
   Email Print
   Bookmark   Link
 

 

Simple polygon
 
 
  Topics Simple polygon Topic Home

In geometry
Geometry

Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers....
, a simple polygon is closed polygonal chain of line segments that do not cross each other. That is, it consists of finitely many line segments, each line segment endpoint is shared by two segments, and the segments do not otherwise intersect. In other words, a simple polygon is a polygon
Polygon

In geometry a polygon is traditionally a plane Shape that is bounded by a closed curve path or circuit, composed of a finite sequence of straight line segments ....
 whose sides do not cross. Simple polygons are also called Jordan polygons, because the Jordan curve theorem
Jordan curve theorem

In topology, the Jordan curve theorem states that every non-self-intersecting Loop in the plane divides the plane into an "inside" and an "outside" region, and any path connecting a point of one region to a point of the other intersects that loop somewhere....
 can be used to prove that such a polygon divides the plane into two regions, the region inside it and the region outside it.






Discussion
Ask a question about 'Simple polygon'
Start a new discussion about 'Simple polygon'
Answer questions from other users
Full Discussion Forum



Encyclopedia


In geometry
Geometry

Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers....
, a simple polygon is closed polygonal chain of line segments that do not cross each other. That is, it consists of finitely many line segments, each line segment endpoint is shared by two segments, and the segments do not otherwise intersect. In other words, a simple polygon is a polygon
Polygon

In geometry a polygon is traditionally a plane Shape that is bounded by a closed curve path or circuit, composed of a finite sequence of straight line segments ....
 whose sides do not cross. Simple polygons are also called Jordan polygons, because the Jordan curve theorem
Jordan curve theorem

In topology, the Jordan curve theorem states that every non-self-intersecting Loop in the plane divides the plane into an "inside" and an "outside" region, and any path connecting a point of one region to a point of the other intersects that loop somewhere....
 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 in the plane is topologically equivalent to a circle
Circle

A circle is a simple shape of Euclidean geometry consisting of those point in a plane which are the same distance from a given point called the center....
 and its interior is topologically equivalent to a disk
Disk (mathematics)

In geometry, a disk is the region in a plane bounded by a circle.A disk is said to be closed or open according to whether or not it contains the circle that constitutes its boundary....
.

A polygon that is not simple is called self-intersecting by geometers and complex by computer graphics programmers (in geometry, a complex polygon
Complex polygon

The term complex polygon can mean two different things:*In computer graphics, as a polygon which is neither convex polygon nor concave polygon.*In geometry, as a polygon in the unitary space plane, which has two complex number dimensions....
 is something different). Such a polygon does not necessarily have a well-defined inside and outside.

In computational geometry
Computational geometry

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of 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
    Point in polygon

    In computational geometry, the point-in-polygon problem asks whether a given point in the plane lies inside, outside, or on the boundary of a 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
    Polygon triangulation

    In computational geometry, polygon triangulation is the decomposition of a polygon into a set of triangles.A triangulation of a polygon P is its partition into non-overlapping triangles whose union is P....
    : 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
    Bernard Chazelle

    Bernard Chazelle is Eugene Higgins Professor of Computer Science of computer science at Princeton University. Much of his work is in computational geometry, where he has found many of the best-known algorithms, such as linear-time triangulation of a simple polygon, as well as many useful complexity results, such as lower bound techniques ba...
     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
    Convex hull

    In mathematics, the convex hull or convex envelope for a Set of points X in a real vector space V is the minimal convex set containing X....
     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.


See Also


Software

  • GPC General Polygon Clipper Library
    GPC General Polygon Clipper Library

    The University of Manchester GPC library is a software library providing an API forcomputing the results of clipping operations on sets of polygons....
    , 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

  • The , which lists solutions to mathematical problems with 2D and 3D Polygons.