Simple polygon

Last updated
Some simple polygons. Polygons Examples of polygons.png
Some simple polygons.

In geometry, a simple polygon /ˈpɒlɪɡɒn/ is a polygon that does not intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pairwise to form a single closed path. If the sides intersect then the polygon is not simple. The qualifier "simple" is frequently omitted, with the above definition then being understood to define a polygon in general.

Contents

The definition given above ensures the following properties:

Two edges meeting at a corner are usually required to form an angle that is not straight (180°); otherwise, the collinear line segments will be considered parts of a single side.

Mathematicians typically use "polygon" to refer only to the shape made up by the line segments, not the enclosed region, however some may use "polygon" to refer to a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments (i.e., by a closed polygonal chain). According to the definition in use, this boundary may or may not form part of the polygon itself. [1]

Simple polygons 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 in the plane is simple if and only if it is topologically equivalent to a circle. Its interior is topologically equivalent to a disk.

Weakly simple polygon

Weakly simple polygon.svg

If a collection of non-crossing line segments forms the boundary of a region of the plane that is topologically equivalent to a disk, then this boundary is called a weakly simple polygon. [2] In the image on the left, ABCDEFGHJKLM is a weakly simple polygon according to this definition, with the color blue marking the region for which it is the boundary. This type of weakly simple polygon can arise in computer graphics and CAD as a computer representation of polygonal regions with holes: for each hole a "cut" is created to connect it to an external boundary. Referring to the image above, ABCM is an external boundary of a planar region with a hole FGHJ. The cut ED connects the hole with the exterior and is traversed twice in the resulting weakly simple polygonal representation.

In an alternative and more general definition of weakly simple polygons, they are the limits of sequences of simple polygons of the same combinatorial type, with the convergence under the Fréchet distance. [3] This formalizes the notion that such a polygon allows segments to touch but not to cross. However, this type of weakly simple polygon does not need to form the boundary of a region, as its "interior" can be empty. For example, referring to the image above, the polygonal chain ABCBA is a weakly simple polygon according to this definition: it may be viewed as the limit of "squeezing" of the polygon ABCFGHA.

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. [4]

Related Research Articles

Polyhedron Three-dimensional shape with flat polygonal faces, straight edges and sharp corners

In geometry, a polyhedron is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices. The word polyhedron comes from the Classical Greek πολύεδρον, as poly- + -hedron.

In geometry, a polygon is a plane figure that is described by a finite number of straight line segments connected to form a closed polygonal chain or polygonal circuit. The solid plane region, the bounding circuit, or the two together, may be called a polygon.

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

Convex hull The smallest convex set containing a given set

In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.

Point in polygon

In computational geometry, the point-in-polygon (PIP) problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon. It is a special case of point location problems and finds applications in areas that deal with processing geometrical data, such as computer graphics, computer vision, geographical information systems (GIS), motion planning, and CAD.

The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided design (CAD).

Concave polygon

A simple polygon that is not convex is called concave, non-convex or reentrant. A concave polygon will always have at least one reflex interior angle—that is, an angle with a measure that is between 180 degrees and 360 degrees exclusive.

Convex polygon

A convex polygon is a simple polygon in which no line segment between two points on the boundary ever goes outside the polygon. Equivalently, it is a simple polygon whose interior is a convex set. In a convex polygon, all interior angles are less than or equal to 180 degrees, while in a strictly convex polygon all interior angles are strictly less than 180 degrees.

Polygon triangulation

In computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is P.

Arrangement of lines

In geometry an arrangement of lines is the partition of the plane formed by a collection of lines. Bounds on the complexity of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.

In geometry, a triangulation is a subdivision of a planar object into triangles, and by extension the subdivision of a higher-dimension geometric object into simplices. Triangulations of a three-dimensional volume would involve subdividing it into tetrahedra packed together.

The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from a real-world problem of guarding an art gallery with the minimum number of guards who together can observe the whole gallery. In the geometric version of the problem, the layout of the art gallery is represented by a simple polygon and each guard is represented by a point in the polygon. A set of points is said to guard a polygon if, for every point in the polygon, there is some such that the line segment between and does not leave the polygon.

Geometric graph theory

Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geometric graphs, meaning graphs drawn in the Euclidean plane with possibly intersecting straight-line edges, and topological graphs, where the edges are allowed to be arbitrary continuous curves connecting the vertices, thus it is "the theory of geometric and topological graphs".

Straight skeleton

In geometry, a straight skeleton is a method of representing a polygon by a topological skeleton. It is similar in some ways to the medial axis but differs in that the skeleton is composed of straight line segments, while the medial axis of a polygon may involve parabolic curves. However, both are homotopy-equivalent to the underlying polygon.

Rectilinear polygon

A rectilinear polygon is a polygon all of whose edge intersections are at right angles. Thus the interior angle at each vertex is either 90° or 270°. Rectilinear polygons are a special case of isothetic polygons.

Pseudotriangle

In Euclidean plane geometry, a pseudotriangle (pseudo-triangle) is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A pseudotriangulation (pseudo-triangulations) is a partition of a region of the plane into pseudotriangles, and a pointed pseudotriangulation is a pseudotriangulation in which at each vertex the incident edges span an angle of less than π.

In geometry, a vertex, often denoted by letters such as , , , , is a point where two or more curves, lines, or edges meet. As a consequence of this definition, the point where two lines meet to form an angle and the corners of polygons and polyhedra are vertices.

Monotone polygon

In geometry, a polygon P in the plane is called monotone with respect to a straight line L, if every line orthogonal to L intersects P at most twice.

Polygonal chain

In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain P is a curve specified by a sequence of points called its vertices. The curve itself consists of the line segments connecting the consecutive vertices.

A partition of a polygon is a set of primitive units, which do not overlap and whose union equals the polygon. A polygon partition problem is a problem of finding a partition which is minimal in some sense, for example a partition with a smallest number of units or with units of smallest total side-length.

References

  1. Grünbaum, B.; Convex Polytopes 2nd Ed, Springer, 2003
  2. Dumitrescu, Adrian; Tóth, Csaba D. (2007). "Light orthogonal networks with constant geometric dilation". In Thomas, Wolfgang; Weil, Pascal (eds.). STACS 2007: 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings (illustrated ed.). Springer. p. 177. ISBN   3540709177.
  3. Hsien-Chih Chang; Jeff Erickson; Chao Xu (2015). Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15). pp. 1655–1670.
  4. The comp.graphics.algorithms FAQ, which lists solutions to mathematical problems with 2D and 3D polygons.
  5. Haines, Eric (1994). "Point in polygon strategies". In Heckbert, Paul S. (ed.). Graphics Gems IV. San Diego, CA, USA: Academic Press Professional, Inc. pp.  24–46. ISBN   0-12-336155-9.
  6. Bart Braden (1986). "The surveyor's area formula" (PDF). The College Mathematics Journal. 17 (4): 326–337. doi:10.2307/2686282. Archived from the original (PDF) on 2012-11-07.
  7. 1 2 Lee, D. T. (1998). "Chapter 19: Computational Geometry I". In Atallah, Mikhail J. (ed.). Algorithms and Theory of Computation Handbook. Chapman & Hall/CRC Applied Algorithms and Data Structures series. CRC Press. ISBN   9781420049503. See "Other decompositions", p. 19-25.