Simple polygon

Simple polygon

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.

External links

*Mathworld | urlname=SimplePolygon | title=Simple polygon


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Polygon (disambiguation) — Polygon may have more than one meaning.In mathematics/computing: * Polygon, a geometric figure * Simple polygon a single contiguous closed region, the more common usage of polygon * Star polygon a star like polygon * Polygon (computer graphics)… …   Wikipedia

  • Polygon — For other uses, see Polygon (disambiguation). Some polygons of different kinds In geometry a polygon (   …   Wikipedia

  • 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. In the strictest sense, these triangles… …   Wikipedia

  • Simple Feature Access — ist eine Spezifikation des Open Geospatial Consortium, welche eine allgemein gültige Architektur für geografische Daten und deren Geometrien definiert. Die Spezifikation beschreibt einerseits die Speicherung und den Zugriff auf Geometrien und… …   Deutsch Wikipedia

  • Simple Features — are an OpenGIS standardwhich specifies digital storage of geographical data (point, line, polygon,multi point, multi line, etc) with both spatialand non spatial attributes. Simple Features are based on 2D geometrywith linear interpolation between …   Wikipedia

  • Simple Features Access — Simple Feature Access ist eine Spezifikation des Open Geospatial Consortium, welche eine allgemein gültige Architektur für geografische Daten und deren Geometrien definiert. Die Spezifikation beschreibt einerseits die Speicherung und den Zugriff… …   Deutsch Wikipedia

  • PoLyGon Format — PoLyGon (abbreviated PLG) is a file format for storing 3D objects. It was originally invented by the people that made REND386. The file is a very simple and easy to read format ideal for very basic flat shaded or wire frame projections.General… …   Wikipedia

  • Polygon mesh — A polygon mesh or unstructured grid is a collection of vertices, edges and faces that defines the shape of a polyhedral object in 3D computer graphics and solid modeling. The faces usually consist of triangles, quadrilaterals or other simple… …   Wikipedia

  • Polygon Window — Aphex Twin Aphex Twin Aphex Twin au Traffic festival à Turin en 2005 Alias AFX, Blue Calx, Bradley Strider, Martin Tressider, Caustic Window, Gak, Soit P.P., Po …   Wikipédia en Français

  • Simple polytope — In geometry, a d dimensional simple polytope is a polytope each of whose vertices is adjacent to exactly d edges.They are topologically dual to simplicial polytopes. The family of polytopes which are bothsimple and simplicial are simplices or two …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”