Simple polygon
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.
The definition given above ensures the following properties:
- A polygon encloses a region (called its interior) which always has a measurable area.
- The line segments that make up a polygon (called sides or edges) meet only at their endpoints, called vertices (singular: vertex) or less formally "corners".
- Exactly two edges meet at each vertex.
- The number of edges always equals the number of vertices.
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
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]
- Point in polygon testing involves determining, for a simple polygon P and a query point q, whether q lies interior to P.[5]
- Simple formulae are known for computing polygon area; that is, the area of the interior of the polygon.[6]
- Polygon partition is a set of primitive units (e.g. squares), 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.[7]
- A special case of polygon partition is 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. The same algorithm may also be used for determining whether a closed polygonal chain forms a simple polygon.
- Another special case is the art gallery problem, which can be equivalently reformulated as a partition into a minimum number of star-shaped polygons.[7]
- Boolean operations on polygons: Various Boolean operations on the sets of points defined by polygonal regions.
- The convex hull of a simple polygon may be computed more efficiently than the convex hull of other types of inputs, such as the convex hull of a point set.
- Voronoi diagram of a simple polygon
- Medial axis/topological skeleton/straight skeleton of a simple polygon
- Offset curve of a simple polygon
- Minkowski sum for simple polygons
References
- ↑ Grünbaum, B.; Convex polytopes 2nd Ed, Springer, 2003
- ↑ Dumitrescu, Adrian; Tóth, Csaba D. (2007). "Light orthogonal networks with constant geometric dilation". in Thomas, Wolfgang; Weil, Pascal. 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. https://books.google.com/books?id=byesH9oM2mIC&pg=PA177&dq=%22weakly+simple+polygon%22#v=onepage&q=%22weakly%20simple%20polygon%22&f=false.
- ↑ 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. http://dl.acm.org/citation.cfm?id=2722239.
- ↑ The comp.graphics.algorithms FAQ, which lists solutions to mathematical problems with 2D and 3D polygons.
- ↑ Haines, Eric (1994). "Point in polygon strategies". in Heckbert, Paul S.. Graphics Gems IV. San Diego, CA, USA: Academic Press Professional, Inc.. pp. 24–46. ISBN 0-12-336155-9. https://books.google.com/books?id=CCqzMm_-WucC&pg=PA24.
- ↑ Bart Braden (1986). "The surveyor's area formula". The College Mathematics Journal 17 (4): 326–337. doi:10.2307/2686282. http://www.maa.org/pubs/Calc_articles/ma063.pdf.
- ↑ 7.0 7.1 Lee, D. T. (1998). "Chapter 19: Computational Geometry I". in Atallah, Mikhail J.. 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.
External links
 |
