Simple polygon

From Wikipedia, the free encyclopedia

Template:Short description Template:DMCA Template:DMCA

File:Two simple polygons and a self-intersecting polygon.svg
Two simple polygons (green and blue) and a self-intersecting polygon (red, in the lower right, not simple)

In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a piecewise-linear Jordan curve consisting of finitely many line segments. These polygons include as special cases the convex polygons, star-shaped polygons, and monotone polygons.

The sum of external angles of a simple polygon is 2π. Every simple polygon with n sides can be triangulated by n−3 of its diagonals, and by the art gallery theorem its interior is visible from some ⌊n/3⌋ of its vertices.

Simple polygons are commonly seen as the input to computational geometry problems, including point in polygon testing, area computation, the convex hull of a simple polygon, triangulation, and Euclidean shortest paths.

Other constructions in geometry related to simple polygons include Schwarz–Christoffel mapping, used to find conformal maps involving simple polygons, polygonalization of point sets, constructive solid geometry formulas for polygons, and visibility graphs of polygons.

Definitions

File:Parts of a simple polygon.png
Parts of a simple polygon

A simple polygon is a closed curve in the Euclidean plane consisting of straight line segments, meeting end-to-end to form a polygonal chain.[1]Template:R/superscript Two line segments meet at every endpoint, and there are no other points of intersection between the line segments. No proper subset of the line segments has the same properties.[2]Template:R/superscript The qualifier simple is sometimes omitted, with the word polygon assumed to mean a simple polygon.[3]Template:R/superscript

The line segments that form a polygon are called its edges or sides. An endpoint of a segment is called a vertex (plural: vertices)[2]Template:R/superscript or a corner. Edges and vertices are more formal, but may be ambiguous in contexts that also involve the edges and vertices of a graph; the more colloquial terms sides and corners can be used to avoid this ambiguity.[4]Template:R/superscript The number of edges always equals the number of vertices.[2]Template:R/superscript Some sources allow two line segments to form a straight angle (180°),[5]Template:R/superscript while others disallow this, instead requiring collinear segments of a closed polygonal chain to be merged into a single longer side.[6]Template:R/superscript Two vertices are neighbors if they are the two endpoints of one of the sides of the polygon.[7]Template:R/superscript

Simple polygons are sometimes called Jordan polygons, because they are Jordan curves; the Jordan curve theorem can be used to prove that such a polygon divides the plane into two regions.[8]Template:R/superscript Indeed, Camille Jordan's original proof of this theorem took the special case of simple polygons (stated without proof) as its starting point.[9]Template:R/superscript The region inside the polygon (its interior) forms a bounded set[2]Template:R/superscript topologically equivalent to an open disk by the Jordan–Schönflies theorem,[10]Template:R/superscript with a finite but nonzero area.[11]Template:R/superscript The polygon itself is topologically equivalent to a circle,[12]Template:R/superscript and the region outside (the exterior) is an unbounded connected open set, with infinite area.[11]Template:R/superscript Although the formal definition of a simple polygon is typically as a system of line segments, it is also possible (and common in informal usage) to define a simple polygon as a closed set in the plane, the union of these line segments with the interior of the polygon.[2]Template:R/superscript

A diagonal of a simple polygon is any line segment that has two polygon vertices as its endpoints, and that otherwise is entirely interior to the polygon.[13]Template:R/superscript

Properties

The internal angle of a simple polygon, at one of its vertices, is the angle spanned by the interior of the polygon at that vertex. A vertex is convex if its internal angle is less than π (a straight angle, 180°) and concave if the internal angle is greater than π. If the internal angle is θ, the external angle at the same vertex is defined to be its supplement π−θ, the turning angle from one directed side to the next. The external angle is positive at a convex vertex or negative at a concave vertex. For every simple polygon, the sum of the external angles is 2π (one full turn, 360°). Thus the sum of the internal angles, for a simple polygon with n sides is (n−2)π.[14]Template:R/superscript

File:Triangulation 3-coloring.svg
A triangulated polygon with 11 vertices: 11 sides and 8 diagonals form 9 triangles.

Every simple polygon can be partitioned into non-overlapping triangles by a subset of its diagonals. When the polygon has n sides, this produces n−2 triangles, separated by n−3 diagonals. The resulting partition is called a polygon triangulation.[8]Template:R/superscript The shape of a triangulated simple polygon can be uniquely determined by the internal angles of the polygon and by the cross-ratios of the quadrilaterals formed by pairs of triangles that share a diagonal.[15]Template:R/superscript

According to the two ears theorem, every simple polygon that is not a triangle has at least two ears, vertices whose two neighbors are the endpoints of a diagonal.[8]Template:R/superscript A related theorem states that every simple polygon that is not a convex polygon has a mouth, a vertex whose two neighbors are the endpoints of a line segment that is otherwise entirely exterior to the polygon. The polygons that have exactly two ears and one mouth are called anthropomorphic polygons.[16]Template:R/superscript

File:Art gallery problem.svg
This 42-vertex polygonal art gallery is entirely visible from cameras placed at the 4 marked vertices.

According to the art gallery theorem, in a simple polygon with n vertices, it is always possible to find a subset of at most ⌊n/3⌋ of the vertices with the property that every point in the polygon is visible from one of the selected vertices. This means that, for each point p in the polygon, there exists a line segment connecting p to a selected vertex, passing only through interior points of the polygon. One way to prove this is to use graph coloring on a triangulation of the polygon: it is always possible to color the vertices with three colors, so that each side or diagonal in the triangulation has two endpoints of different colors. Each point of the polygon is visible to a vertex of each color, for instance one of the three vertices of the triangle containing that point in the chosen triangulation. One of the colors is used by at most ⌊n/3⌋ of the vertices, proving the theorem.[17]Template:R/superscript

Special cases

Every convex polygon is a simple polygon. Another important class of simple polygons are the star-shaped polygons, the polygons that have a point (interior or on their boundary) from which every point is visible.[2]Template:R/superscript

A monotone polygon, with respect to a straight line L, is a polygon for which every line perpendicular to L intersects the interior of the polygon in a connected set. Equivalently, it is a polygon whose boundary can be partitioned into two monotone polygonal chains, subsequences of edges whose vertices, when projected perpendicularly onto L, have the same order along L as they do in the chain.[18]Template:R/superscript

Computational problems

File:RecursiveEvenPolygon.svg
To test whether a point is inside the polygon, construct any ray emanating from the point and count its intersections with the polygon. If it crosses only interior points of edges, an odd number of times, the point lies inside the polygon; if even, the point lies outside. Rays through polygon vertices or containing its edges need special care.[19]Template:R/superscript
File:Convex hull of a simple polygon.svg
A simple polygon (interior shaded blue) and its convex hull (surrounding both blue and yellow regions)

In computational geometry, several important computational tasks involve inputs in the form of a simple polygon.

Other computational problems studied for simple polygons include constructions of the longest diagonal or the longest line segment interior to a polygon,[13]Template:R/superscript of the convex skull (the largest convex polygon within the given simple polygon),[29]Template:R/superscript[30]Template:R/superscript and of various one-dimensional skeletons approximating its shape, including the medial axis[31]Template:R/superscript and straight skeleton.[32]Template:R/superscript Researchers have also studied producing other polygons from simple polygons using their offset curves,[33]Template:R/superscript unions and intersections,[11]Template:R/superscript and Minkowski sums,[34]Template:R/superscript but these operations do not always produce a simple polygon as their result. They can be defined in a way that always produces a two-dimensional region, but this requires careful definitions of the intersection and difference operations in order to avoid creating one-dimensional features or isolated points.[11]Template:R/superscript

According to the Riemann mapping theorem, any simply connected open subset of the plane can be conformally mapped onto a disk. Schwarz–Christoffel mapping provides a method to explicitly construct a map from a disk to any simple polygon using specified vertex angles and pre-images of the polygon vertices on the boundary of the disk. These pre-vertices are typically computed numerically.[35]Template:R/superscript

The black polygon is the shortest loop connecting every red dot, a solution to the traveling salesperson problem.

Every finite set of points in the plane that does not lie on a single line can be connected to form the vertices of a simple polygon (allowing 180° angles); for instance, one such polygon is the solution to the traveling salesperson problem.[36]Template:R/superscript Connecting points to form a polygon in this way is called polygonalization.[37]Template:R/superscript

Every simple polygon can be represented by a formula in constructive solid geometry that constructs the polygon (as a closed set including the interior) from unions and intersections of half-planes, with each side of the polygon appearing once as a half-plane in the formula. Converting an n-sided polygon into this representation can be performed in time O(nlog⁡n).[38]Template:R/superscript

The visibility graph of a simple polygon connects its vertices by edges representing the sides and diagonals of the polygon.[3]Template:R/superscript It always contains a Hamiltonian cycle, formed by the polygon sides. The computational complexity of reconstructing a polygon that has a given graph as its visibility graph, with a specified Hamiltonian cycle as its cycle of sides, remains an open problem.[39]Template:R/superscript

See also

References

  1. ^ Page Module:Citation/CS1/styles.css has no content.Milnor, John W. (1950). "On the total curvature of knots". Annals of Mathematics. 2nd Series. 52: 248–257. doi:10.2307/1969467.
  2. ^ a b c d e f Page Module:Citation/CS1/styles.css has no content.Preparata, Franco P.; Shamos, Michael Ian (1985). Computational Geometry: An Introduction. Texts and Monographs in Computer Science. Springer-Verlag. p. 18. doi:10.1007/978-1-4612-1098-6. ISBN 978-1-4612-1098-6.
  3. ^ a b Page Module:Citation/CS1/styles.css has no content.Everett, Hazel; Corneil, Derek (1995). "Negative results on characterizing visibility graphs". Computational Geometry: Theory & Applications. 5 (2): 51–63. doi:10.1016/0925-7721(95)00021-Z. MR 1353288.
  4. ^ Page Module:Citation/CS1/styles.css has no content.Aronov, Boris; Seidel, Raimund; Souvaine, Diane (1993). "On compatible triangulations of simple polygons". Computational Geometry: Theory & Applications. 3 (1): 27–35. doi:10.1016/0925-7721(93)90028-5. MR 1222755.
  5. ^ Page Module:Citation/CS1/styles.css has no content.Malkevitch, Joseph (2016). "Are precise definitions a good idea?". AMS Feature Column. American Mathematical Society.
  6. ^ a b Page Module:Citation/CS1/styles.css has no content.McCallum, Duncan; Avis, David (1979). "A linear algorithm for finding the convex hull of a simple polygon". Information Processing Letters. 9 (5): 201–206. doi:10.1016/0020-0190(79)90069-3. MR 0552534.
  7. ^ Page Module:Citation/CS1/styles.css has no content.de Berg, M.; van Kreveld, M.; Overmars, Mark; Schwarzkopf, O. (2008). Computational Geometry: Algorithms and Applications (3rd ed.). Springer. p. 58. doi:10.1007/978-3-540-77974-2.
  8. ^ a b c Page Module:Citation/CS1/styles.css has no content.Meisters, G. H. (1975). "Polygons have ears". The American Mathematical Monthly. 82 (6): 648–651. doi:10.2307/2319703. JSTOR 2319703. MR 0367792.
  9. ^ Page Module:Citation/CS1/styles.css has no content.Hales, Thomas C. (2007). "Jordan's proof of the Jordan curve theorem" (PDF). From Insight to Proof: Festschrift in Honour of Andrzej Trybulec. Studies in Logic, Grammar and Rhetoric. 10 (23). University of Białystok.
  10. ^ Page Module:Citation/CS1/styles.css has no content.Thomassen, Carsten (1992). "The Jordan-Schönflies theorem and the classification of surfaces". The American Mathematical Monthly. 99 (2): 116–130. doi:10.1080/00029890.1992.11995820. JSTOR 2324180. MR 1144352.
  11. ^ a b c d Page Module:Citation/CS1/styles.css has no content.Margalit, Avraham; Knott, Gary D. (1989). "An algorithm for computing the union, intersection or difference of two polygons". Computers & Graphics. 13 (2): 167–183. doi:10.1016/0097-8493(89)90059-9.
  12. ^ a b Page Module:Citation/CS1/styles.css has no content.Niven, Ivan; Zuckerman, H. S. (1967). "Lattice points and polygonal area". The American Mathematical Monthly. 74 (10): 1195–1200. doi:10.1080/00029890.1967.12000095. JSTOR 2315660. MR 0225216.
  13. ^ a b Page Module:Citation/CS1/styles.css has no content.Aggarwal, Alok; Suri, Subhash (1990). "Computing the longest diagonal of a simple polygon". Information Processing Letters. 35 (1): 13–18. doi:10.1016/0020-0190(90)90167-V. MR 1069001.
  14. ^ Page Module:Citation/CS1/styles.css has no content.Richmond, Bettina; Richmond, Thomas (2023). A Discrete Transition to Advanced Mathematics. Pure and Applied Undergraduate Texts. Vol. 63 (2nd ed.). American Mathematical Society. p. 421. ISBN 9781470472047.
  15. ^ Page Module:Citation/CS1/styles.css has no content.Snoeyink, Jack (1999). "Cross-ratios and angles determine a polygon". Discrete & Computational Geometry. 22 (4): 619–631. doi:10.1007/PL00009481. MR 1721028.
  16. ^ Page Module:Citation/CS1/styles.css has no content.Toussaint, Godfried (1991). "Anthropomorphic polygons". The American Mathematical Monthly. 98 (1): 31–35. doi:10.2307/2324033. JSTOR 2324033. MR 1083611.
  17. ^ Page Module:Citation/CS1/styles.css has no content.Fisk, S. (1978). "A short proof of Chvátal's watchman theorem". Journal of Combinatorial Theory, Series B. 24 (3): 374. doi:10.1016/0095-8956(78)90059-X.
  18. ^ Page Module:Citation/CS1/styles.css has no content.Preparata, Franco P.; Supowit, Kenneth J. (1981). "Testing a simple polygon for monotonicity". Information Processing Letters. 12 (4): 161–164. doi:10.1016/0020-0190(81)90091-0.
  19. ^ Page Module:Citation/CS1/styles.css has no content.Schirra, Stefan (2008). "How reliable are practical point-in-polygon strategies?" (PDF). In Halperin, Dan; Mehlhorn, Kurt (eds.). Algorithms – ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15–17, 2008. Proceedings. Lecture Notes in Computer Science. Vol. 5193. Springer. pp. 744–755. doi:10.1007/978-3-540-87744-8_62.
  20. ^ Page Module:Citation/CS1/styles.css has no content.Snoeyink, Jack (2017). "Point Location" (PDF). In Toth, Csaba D.; O'Rourke, Joseph; Goodman, Jacob E. (eds.). Handbook of Discrete and Computational Geometry (3rd ed.). Chapman and Hall/CRC Press. pp. 1005–1023. ISBN 978-1-498-71139-5.
  21. ^ Page Module:Citation/CS1/styles.css has no content.Braden, Bart (1986). "The surveyor's area formula" (PDF). The College Mathematics Journal. 17 (4): 326–337. doi:10.2307/2686282. JSTOR 2686282. Archived from the original (PDF) on 2012-11-07.
  22. ^ Page Module:Citation/CS1/styles.css has no content.Grünbaum, Branko; Shephard, G. C. (February 1993). "Pick's theorem". The American Mathematical Monthly. 100 (2): 150–161. doi:10.2307/2323771. JSTOR 2323771. MR 1212401.
  23. ^ Page Module:Citation/CS1/styles.css has no content.Chazelle, Bernard (1991). "Triangulating a simple polygon in linear time". Discrete & Computational Geometry. 6 (5): 485–524. doi:10.1007/BF02574703. MR 1115104.
  24. ^ Page Module:Citation/CS1/styles.css has no content.Urrutia, Jorge (2000). "Art gallery and illumination problems". In Sack, Jörg-Rüdiger; Urrutia, Jorge (eds.). Handbook of Computational Geometry. Amsterdam: North-Holland. pp. 973–1027. doi:10.1016/B978-044482537-7/50023-1. ISBN 0-444-82537-1. MR 1746693.
  25. ^ Page Module:Citation/CS1/styles.css has no content.Aichholzer, Oswin; Mulzer, Wolfgang; Pilz, Alexander (2015). "Flip distance between triangulations of a simple polygon is NP-complete". Discrete & Computational Geometry. 54 (2): 368–389. arXiv:1209.0579. doi:10.1007/s00454-015-9709-7. MR 3372115.
  26. ^ a b Page Module:Citation/CS1/styles.css has no content.Ahn, Hee-Kap; Barba, Luis; Bose, Prosenjit; De Carufel, Jean-Lou; Korman, Matias; Oh, Eunjin (2016). "A linear-time algorithm for the geodesic center of a simple polygon". Discrete & Computational Geometry. 56 (4): 836–859. arXiv:1501.00561. doi:10.1007/s00454-016-9796-0. MR 3561791.
  27. ^ a b Page Module:Citation/CS1/styles.css has no content.Guibas, Leonidas; Hershberger, John; Leven, Daniel; Sharir, Micha; Tarjan, Robert E. (1987). "Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons". Algorithmica. 2 (2): 209–233. doi:10.1007/BF01840360. MR 0895445.
  28. ^ Page Module:Citation/CS1/styles.css has no content.El Gindy, Hossam; Avis, David (1981). "A linear algorithm for computing the visibility polygon from a point". Journal of Algorithms. 2 (2): 186–197. doi:10.1016/0196-6774(81)90019-5.
  29. ^ Page Module:Citation/CS1/styles.css has no content.Chang, J. S.; Yap, C.-K. (1986). "A polynomial solution for the potato-peeling problem". Discrete & Computational Geometry. 1 (2): 155–182. doi:10.1007/BF02187692. MR 0834056.
  30. ^ Page Module:Citation/CS1/styles.css has no content.Cabello, Sergio; Cibulka, Josef; Kynčl, Jan; Saumell, Maria; Valtr, Pavel (2017). "Peeling potatoes near-optimally in near-linear time". SIAM Journal on Computing. 46 (5): 1574–1602. arXiv:1406.1368. doi:10.1137/16M1079695. MR 3708542.
  31. ^ Page Module:Citation/CS1/styles.css has no content.Chin, Francis Y. L.; Snoeyink, Jack; Wang, Cao An (1999). "Finding the medial axis of a simple polygon in linear time". Discrete & Computational Geometry. 21 (3): 405–420. doi:10.1007/PL00009429. MR 1672988.
  32. ^ Page Module:Citation/CS1/styles.css has no content.Cheng, Siu-Wing; Mencel, Liam; Vigneron, Antoine (2016). "A faster algorithm for computing straight skeletons". ACM Transactions on Algorithms. 12 (3): 44:1–44:21. arXiv:1405.4691. doi:10.1145/2898961.
  33. ^ Page Module:Citation/CS1/styles.css has no content.Palfrader, Peter; Held, Martin (February 2015). "Computing mitered offset curves based on straight skeletons". Computer-Aided Design and Applications. 12 (4): 414–424. doi:10.1080/16864360.2014.997637.
  34. ^ Page Module:Citation/CS1/styles.css has no content.Oks, Eduard; Sharir, Micha (2006). "Minkowski sums of monotone and general simple polygons". Discrete & Computational Geometry. 35 (2): 223–240. doi:10.1007/s00454-005-1206-y. MR 2195052.
  35. ^ Page Module:Citation/CS1/styles.css has no content.Trefethen, Lloyd N.; Driscoll, Tobin A. (1998). "Schwarz–Christoffel mapping in the computer era". Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998). Documenta Mathematica. pp. 533–542. MR 1648186.
  36. ^ Page Module:Citation/CS1/styles.css has no content.Quintas, L. V.; Supnick, Fred (1965). "On some properties of shortest Hamiltonian circuits". The American Mathematical Monthly. 72 (9): 977–980. doi:10.2307/2313333. JSTOR 2313333. MR 0188872.
  37. ^ Page Module:Citation/CS1/styles.css has no content.Demaine, Erik D.; Fekete, Sándor P.; Keldenich, Phillip; Krupke, Dominik; Mitchell, Joseph S. B. (2022). "Area-optimal simple polygonalizations: the CG challenge 2019". ACM Journal of Experimental Algorithmics. 27: A2.4:1–12. doi:10.1145/3504000. hdl:1721.1/146480. MR 4390039.
  38. ^ Page Module:Citation/CS1/styles.css has no content.Dobkin, David; Guibas, Leonidas; Hershberger, John; Snoeyink, Jack (1993). "An efficient algorithm for finding the CSG representation of a simple polygon". Algorithmica. 10 (1): 1–23. doi:10.1007/BF01908629. MR 1230699.
  39. ^ Page Module:Citation/CS1/styles.css has no content.Ghosh, Subir Kumar; Goswami, Partha P. (2013). "Unsolved problems in visibility graphs of points, segments, and polygons". ACM Computing Surveys. 46 (2): 22:1–22:29. arXiv:1012.5187. doi:10.1145/2543581.2543589.
  • Script error: No such module "Template wrapper".

Lua error in package.lua at line 80: module 'Module:Navbox/configuration' not found.

Retrieved from "https://cosmopedia.co/index.php?title=Simple_polygon&oldid=620191"