Editing Simple polygon

{{good article}}
{{Short description|Shape bounded by non-intersecting line segments}}
{{Use mdy dates|cs1-dates=ly|date=July 2023}}
{{Use list-defined references|date=July 2023}}
[[File:Two simple polygons and a self-intersecting polygon.png|thumb|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 [[Intersection (Euclidean geometry)|intersect]] itself and has no holes. That is, it is a [[Piecewise linear curve|piecewise-linear]] [[Jordan curve]] consisting of finitely many [[line segment]]s. These polygons include as special cases the [[convex polygon]]s, [[star-shaped polygon]]s, and [[monotone polygon]]s.

The sum of [[external angle]]s of a simple polygon is <math>2\pi</math>. Every simple polygon with <math>n</math> sides can be [[polygon triangulation|triangulated]] by <math>n-3</math> of its diagonals, and by the [[art gallery theorem]] its interior is visible from some <math>\lfloor n/3\rfloor</math> 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 path]]s.

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

==Definitions==
[[File:Parts of a simple polygon.png|thumb|upright=1.25|Parts of a simple polygon]]
A simple polygon is a [[closed curve]] in the [[Euclidean plane]] consisting of [[line segment|straight line segments]], meeting end-to-end to form a [[polygonal chain]].{{r|milnor}} 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.{{r|preparata-shamos}} The qualifier ''simple'' is sometimes omitted, with the word ''polygon'' assumed to mean a simple polygon.{{r|everett-corneil}}

The line segments that form a polygon are called its ''edges'' or ''sides''. An endpoint of a segment is called a ''[[Vertex (geometry)|vertex]]'' (plural: vertices){{r|preparata-shamos}} 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 (graph theory)|graph]]; the more colloquial terms ''sides'' and ''corners'' can be used to avoid this ambiguity.{{r|compatible}} The number of edges always equals the number of vertices.{{r|preparata-shamos}} Some sources allow two line segments to form a [[straight angle]] (180°),{{r|malkevitch}} while others disallow this, instead requiring collinear segments of a closed polygonal chain to be merged into a single longer side.{{r|mccallum-avis}} Two vertices are ''neighbors'' if they are the two endpoints of one of the sides of the polygon.{{r|4marks}}

Simple polygons are sometimes called '''Jordan polygons''', because they are [[Jordan curve]]s; the [[Jordan curve theorem]] can be used to prove that such a polygon divides the plane into two regions.{{r|meisters}} Indeed, [[Camille Jordan]]'s original proof of this theorem took the special case of simple polygons (stated without proof) as its starting point.{{r|hales}} The region inside the polygon (its ''interior'') forms a [[bounded set]]{{r|preparata-shamos}} [[Homeomorphism|topologically equivalent]] to an [[open disk]] by the [[Jordan–Schönflies theorem]],{{r|thomassen}} with a finite but nonzero [[area]].{{r|margalit-knott}} The polygon itself is topologically equivalent to a [[circle]],{{r|niven-zuckerman}} and the region outside (the ''exterior'') is an unbounded [[Domain (mathematical analysis)|connected open set]], with infinite area.{{r|margalit-knott}} 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.{{r|preparata-shamos}}

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.{{r|aggarwal-suri}}

==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 <math>\pi</math> (a straight angle, 180°) and ''concave'' if the internal angle is greater than <math>\pi</math>. If the internal angle is <math>\theta</math>, the ''[[external angle]]'' at the same vertex is defined to be its [[supplementary angle|supplement]] <math>\pi-\theta</math>, 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 <math>2\pi</math> (one full turn, 360°). Thus the sum of the internal angles, for a simple polygon with <math>n</math> sides is <math>(n-2)\pi</math>.{{r|rich2}}

[[File:Triangulation 3-coloring.svg|thumb|left|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 <math>n</math> sides, this produces <math>n-2</math> triangles, separated by <math>n-3</math> diagonals. The resulting partition is called a ''[[polygon triangulation]]''.{{r|meisters}} The shape of a triangulated simple polygon can be uniquely determined by the internal angles of the polygon and by the [[cross-ratio]]s of the [[quadrilateral]]s formed by pairs of triangles that share a diagonal.{{r|cross-ratio}}

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.{{r|meisters}} 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 polygon]]s''.{{r|toussaint}}

[[File:Art gallery problem.svg|thumb|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 <math>n</math> vertices, it is always possible to find a subset of at most <math>\lfloor n/3\rfloor</math> 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 <math>p</math> in the polygon, there exists a line segment connecting <math>p</math> 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 <math>\lfloor n/3\rfloor</math> of the vertices, proving the theorem.{{r|fisk}}

==Special cases==
Every [[convex polygon]] is a simple polygon. Another important class of simple polygons are the [[star-shaped polygon]]s, the polygons that have a point (interior or on their boundary) from which every point is visible.{{r|preparata-shamos}}

A [[monotone polygon]], with respect to a straight line <math>L</math>, is a polygon for which every line perpendicular to <math>L</math> 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 <math>L</math>, have the same order along <math>L</math> as they do in the chain.{{r|preparata-supowit}}

== Computational problems==
[[Image:RecursiveEvenPolygon.svg|upright=1.25|thumb|To test whether a point is inside the polygon, construct any [[ray (geometry)|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.{{r|schirra}}]]
[[File:Convex hull of a simple polygon.svg|thumb|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.
* [[Point in polygon]] testing involves determining, for a simple polygon <math>P</math> and a query point <math>q</math>, whether <math>q</math> lies interior to <math>P</math>. It can be solved in [[linear time]]; alternatively, it is possible to process a given polygon into a data structure, in linear time, so that subsequent point in polygon tests can be performed in logarithmic time.{{r|snoeyink}}
* Simple formulae are known for computing the [[area]] of the interior of a polygon. These include the [[shoelace formula]] for arbitrary polygons,{{r|braden}} and [[Pick's theorem]] for polygons with integer vertex coordinates.{{r|niven-zuckerman|grunbaum-shephard}}
* The [[convex hull of a simple polygon]] can also be found in linear time, faster than algorithms for finding [[convex hull]]s of points that have not been connected into a polygon.{{r|mccallum-avis}}
* Constructing a triangulation of a simple polygon can also be performed in linear time, although the algorithm is complicated. A modification of the same algorithm can also be used to test whether a closed polygonal chain forms a simple polygon (that is, whether it avoids self-intersections) in linear time.{{r|chazelle}} This also leads to a linear time algorithm for solving the art gallery problem using at most <math>\lfloor n/3\rfloor</math> points, although not necessarily using the optimal number of points for a given polygon.{{r|urrutia}} Although it is possible to transform any two triangulations of the same polygon into each other by [[Flip graph|flips]] that replace one diagonal at a time, determining whether one can do so using only a limited number of flips is [[NP-complete]].{{r|amp}}
* A [[geodesic]] path,{{r|abbcko}} the [[Euclidean shortest path|shortest path]] in the plane that connects two points interior to a polygon, without crossing to the exterior, may be found in linear time by an algorithm that uses triangulation as a subroutine.{{r|ghlst}} The same is true for the ''geodesic center'', a point in the polygon that minimizes the maximum length of its geodesic paths to all other points.{{r|abbcko}}
* The [[visibility polygon]] of an interior point of a simple polygon, the points that are directly visible from the given point by line segments interior to the polygon, can be constructed in linear time.{{r|avis-elgindy}} The same is true for the subset that is visible from at least one point of a given line segment.{{r|ghlst}}

Other computational problems studied for simple polygons include constructions of the longest diagonal or the longest line segment interior to a polygon,{{r|aggarwal-suri}} of the [[convex skull]] (the largest convex polygon within the given simple polygon),{{r|chang-yap|ccksv}} and of various one-dimensional ''skeletons'' approximating its shape, including the [[medial axis]]{{r|csl}} and [[straight skeleton]].{{r|cmv}} Researchers have also studied producing other polygons from simple polygons using their [[offset curve]]s,{{r|palfrader-held}} unions and intersections,{{r|margalit-knott}} and [[Minkowski sum]]s,{{r|oks-sharir}} 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.{{r|margalit-knott}}

== Related constructions ==
According to the [[Riemann mapping theorem]], any simply connected open subset of the plane can be [[conformal map|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.{{r|trefethen-driscoll}}

[[File:GLPK solution of a travelling salesman problem.svg|thumb|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]].{{r|quintas-supnick}} Connecting points to form a polygon in this way is called [[polygonalization]].{{r|dfkkm}}

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-plane]]s, with each side of the polygon appearing once as a half-plane in the formula. Converting an <math>n</math>-sided polygon into this representation can be performed in time <math>O(n\log n)</math>.{{r|dghs}}

The [[visibility graph]] of a simple polygon connects its vertices by edges representing the sides and diagonals of the polygon.{{r|everett-corneil}} 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.{{r|ghosh-goswami}}

==See also==
*[[Carpenter's rule problem]], on continuous motion of a simple polygon into a convex polygon
*[[Erdős–Nagy theorem]], a process of reflecting pockets of a non-convex simple polygon to make it convex
*[[Net (polyhedron)]], a simple polygon that can be folded and glued to form a given polyhedron
*[[Spherical polygon]], an analogous concept on the surface of a sphere
*[[Weakly simple polygon]], a generalization of simple polygons allowing the edges to touch in limited ways
{{clear}}
==References==
{{reflist|refs=

<ref name=4marks>{{cite book
 | last1 = de Berg | first1 = M. | author1-link = Mark de Berg
 | last2 = van Kreveld | first2 = M. | author2-link = Marc van Kreveld
 | last3 = Overmars | first3 = Mark | author3-link = Mark Overmars
 | last4 = Schwarzkopf | first4 = O. | author4-link = Otfried Cheong
 | doi = 10.1007/978-3-540-77974-2
 | edition = 3rd
 | page = 58
 | publisher = Springer
 | title = Computational Geometry: Algorithms and Applications
 | year = 2008}}</ref>

<ref name=abbcko>{{cite journal
 | last1 = Ahn | first1 = Hee-Kap
 | last2 = Barba | first2 = Luis
 | last3 = Bose | first3 = Prosenjit | author3-link = Jit Bose
 | last4 = De Carufel | first4 = Jean-Lou
 | last5 = Korman | first5 = Matias
 | last6 = Oh | first6 = Eunjin
 | arxiv = 1501.00561
 | doi = 10.1007/s00454-016-9796-0
 | issue = 4
 | journal = [[Discrete & Computational Geometry]]
 | mr = 3561791
 | pages = 836–859
 | title = A linear-time algorithm for the geodesic center of a simple polygon
 | volume = 56
 | year = 2016}}</ref>

<ref name=aggarwal-suri>{{cite journal
 | last1 = Aggarwal | first1 = Alok
 | last2 = Suri | first2 = Subhash | author2-link = Subhash Suri
 | doi = 10.1016/0020-0190(90)90167-V
 | issue = 1
 | journal = [[Information Processing Letters]]
 | mr = 1069001
 | pages = 13–18
 | title = Computing the longest diagonal of a simple polygon
 | volume = 35
 | year = 1990}}</ref>

<ref name=amp>{{cite journal
 | last1 = Aichholzer | first1 = Oswin
 | last2 = Mulzer | first2 = Wolfgang
 | last3 = Pilz | first3 = Alexander
 | doi = 10.1007/s00454-015-9709-7
 | issue = 2
 | journal = [[Discrete & Computational Geometry]]
 | mr = 3372115
 | pages = 368–389
 | title = Flip distance between triangulations of a simple polygon is NP-complete
 | volume = 54
 | year = 2015| arxiv = 1209.0579
 }}</ref>

<ref name=avis-elgindy>{{cite journal
 | last1 = El Gindy | first1 = Hossam
 | last2 = Avis | first2 = David | author2-link = David Avis
 | doi = 10.1016/0196-6774(81)90019-5
 | issue = 2
 | journal = Journal of Algorithms
 | pages = 186–197
 | title = A linear algorithm for computing the visibility polygon from a point
 | volume = 2
 | year = 1981}}</ref>

<ref name=braden>{{cite journal
 | last = Braden | first = Bart
 | doi = 10.2307/2686282
 | issue = 4
 | journal = [[The College Mathematics Journal]]
 | jstor = 2686282
 | pages = 326–337
 | title = The surveyor's area formula
 | url = https://www.maa.org/pubs/Calc_articles/ma063.pdf
 | archive-url = https://web.archive.org/web/20121107190918/http://www.maa.org/pubs/Calc_articles/ma063.pdf
 | archive-date = 2012-11-07
 | url-status = dead
 | volume = 17
 | year = 1986}}</ref>

<ref name=ccksv>{{cite journal
 | last1 = Cabello | first1 = Sergio
 | last2 = Cibulka | first2 = Josef
 | last3 = Kynčl | first3 = Jan
 | last4 = Saumell | first4 = Maria
 | last5 = Valtr | first5 = Pavel
 | arxiv = 1406.1368
 | doi = 10.1137/16M1079695
 | issue = 5
 | journal = [[SIAM Journal on Computing]]
 | mr = 3708542
 | pages = 1574–1602
 | title = Peeling potatoes near-optimally in near-linear time
 | volume = 46
 | year = 2017}}</ref>

<ref name=chang-yap>{{cite journal
 | last1 = Chang | first1 = J. S.
 | last2 = Yap | first2 = C.-K.
 | doi = 10.1007/BF02187692 | doi-access = free
 | issue = 2
 | journal = [[Discrete & Computational Geometry]]
 | mr = 834056
 | pages = 155–182
 | title = A polynomial solution for the potato-peeling problem
 | volume = 1
 | year = 1986}}</ref>

<ref name=chazelle>{{cite journal
 | last = Chazelle | first = Bernard | author-link = Bernard Chazelle
 | doi = 10.1007/BF02574703
 | issue = 5
 | journal = [[Discrete & Computational Geometry]]
 | mr = 1115104
 | pages = 485–524
 | title = Triangulating a simple polygon in linear time
 | volume = 6
 | year = 1991| doi-access = free
 }}</ref>

<ref name=cmv>{{cite journal
 | last1 = Cheng | first1 = Siu-Wing
 | last2 = Mencel | first2 = Liam
 | last3 = Vigneron | first3 = Antoine
 | arxiv = 1405.4691
 | title = A faster algorithm for computing straight skeletons
 | pages = 44:1–44:21
 | journal = [[ACM Transactions on Algorithms]]
 | volume = 12
 | number = 3
 | year = 2016
 | doi = 10.1145/2898961}}</ref>

<ref name=compatible>{{cite journal
 | last1 = Aronov | first1 = Boris | author1-link = Boris Aronov
 | last2 = Seidel | first2 = Raimund | author2-link = Raimund Seidel
 | last3 = Souvaine | first3 = Diane | author3-link = Diane Souvaine
 | doi = 10.1016/0925-7721(93)90028-5
 | issue = 1
 | journal = [[Computational Geometry (journal)|Computational Geometry: Theory & Applications]]
 | mr = 1222755
 | pages = 27–35
 | title = On compatible triangulations of simple polygons
 | volume = 3
 | year = 1993| doi-access = free
 }}</ref>

<ref name=cross-ratio>{{cite journal
 | last = Snoeyink | first = Jack
 | doi = 10.1007/PL00009481
 | issue = 4
 | journal = [[Discrete & Computational Geometry]]
 | mr = 1721028
 | pages = 619–631
 | title = Cross-ratios and angles determine a polygon
 | volume = 22
 | year = 1999| doi-access = free
 }}</ref>

<ref name=csl>{{cite journal
 | last1 = Chin | first1 = Francis Y. L. | author1-link = Francis Y. L. Chin
 | last2 = Snoeyink | first2 = Jack
 | last3 = Wang | first3 = Cao An
 | doi = 10.1007/PL00009429
 | issue = 3
 | journal = [[Discrete & Computational Geometry]]
 | mr = 1672988
 | pages = 405–420
 | title = Finding the medial axis of a simple polygon in linear time
 | volume = 21
 | year = 1999| doi-access = free
 }}</ref>

<ref name=dfkkm>{{cite journal
 | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
 | last2 = Fekete | first2 = Sándor P.
 | last3 = Keldenich | first3 = Phillip
 | last4 = Krupke | first4 = Dominik
 | last5 = Mitchell | first5 = Joseph S. B. | author5-link = Joseph S. B. Mitchell
 | doi = 10.1145/3504000
 | journal = ACM Journal of Experimental Algorithmics
 | mr = 4390039
 | pages = A2.4:1–12
 | title = Area-optimal simple polygonalizations: the CG challenge 2019
 | volume = 27
 | year = 2022| hdl = 1721.1/146480
 | hdl-access = free
 }}</ref>

<ref name=dghs>{{cite journal
 | last1 = Dobkin | first1 = David | author1-link = David P. Dobkin
 | last2 = Guibas | first2 = Leonidas | author2-link = Leonidas J. Guibas
 | last3 = Hershberger | first3 = John | author3-link = John Hershberger
 | last4 = Snoeyink | first4 = Jack
 | doi = 10.1007/BF01908629
 | issue = 1
 | journal = [[Algorithmica]]
 | mr = 1230699
 | pages = 1–23
 | title = An efficient algorithm for finding the CSG representation of a simple polygon
 | volume = 10
 | year = 1993}}</ref>

<ref name=everett-corneil>{{cite journal
 | last1 = Everett | first1 = Hazel
 | last2 = Corneil | first2 = Derek | author2-link = Derek Corneil
 | doi = 10.1016/0925-7721(95)00021-Z
 | issue = 2
 | journal = [[Computational Geometry (journal)|Computational Geometry: Theory & Applications]]
 | mr = 1353288
 | pages = 51–63
 | title = Negative results on characterizing visibility graphs
 | volume = 5
 | year = 1995}}</ref>

<ref name=fisk>{{cite journal
 | last = Fisk | first = S.
 | doi = 10.1016/0095-8956(78)90059-X | doi-access = free
 | issue = 3
 | journal = [[Journal of Combinatorial Theory, Series B]]
 | page = 374
 | title = A short proof of Chvátal's watchman theorem
 | volume = 24
 | year = 1978}}</ref>

<ref name=ghosh-goswami>{{cite journal
 | last1 = Ghosh | first1 = Subir Kumar
 | last2 = Goswami | first2 = Partha P.
 | arxiv = 1012.5187
 | doi = 10.1145/2543581.2543589
 | issue = 2
 | journal = [[ACM Computing Surveys]]
 | pages = 22:1–22:29
 | title = Unsolved problems in visibility graphs of points, segments, and polygons
 | volume = 46
 | year = 2013}}</ref>

<ref name=ghlst>{{cite journal
 | last1 = Guibas | first1 = Leonidas | author1-link = Leonidas J. Guibas
 | last2 = Hershberger | first2 = John | author2-link = John Hershberger
 | last3 = Leven | first3 = Daniel
 | last4 = Sharir | first4 = Micha | author4-link = Micha Sharir
 | last5 = Tarjan | first5 = Robert E. | author5-link = Robert Tarjan
 | doi = 10.1007/BF01840360
 | issue = 2
 | journal = [[Algorithmica]]
 | mr = 895445
 | pages = 209–233
 | title = Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
 | volume = 2
 | year = 1987}}</ref>

<ref name=grunbaum-shephard>{{cite journal
 | last1 = Grünbaum | first1 = Branko | author1-link = Branko Grünbaum
 | last2 = Shephard | first2 = G. C. | author2-link = Geoffrey Colin Shephard
 | date = February 1993
 | doi = 10.2307/2323771
 | issue = 2
 | journal = [[The American Mathematical Monthly]]
 | jstor = 2323771
 | mr = 1212401
 | pages = 150–161
 | title = Pick's theorem
 | volume = 100}}</ref>

<ref name=hales>{{cite journal
 | last = Hales | first = Thomas C. | author-link = Thomas Callister Hales
 | department = From Insight to Proof: Festschrift in Honour of Andrzej Trybulec
 | issue = 23
 | journal = [[Studies in Logic, Grammar and Rhetoric]]
 | publisher = University of Białystok
 | title = Jordan's proof of the Jordan curve theorem
 | url = https://www.maths.ed.ac.uk/~v1ranick/papers/hales1.pdf
 | volume = 10
 | year = 2007}}</ref>

<ref name=malkevitch>{{cite web
 | last = Malkevitch | first = Joseph
 | title = Are precise definitions a good idea?
 | url = https://www.ams.org/publicoutreach/feature-column/fc-2016-01
 | publisher = American Mathematical Society
 | work = AMS Feature Column
 | year = 2016}}</ref>

<ref name=margalit-knott>{{cite journal
 | last1 = Margalit | first1 = Avraham
 | last2 = Knott | first2 = Gary D.
 | doi = 10.1016/0097-8493(89)90059-9
 | issue = 2
 | journal = Computers & Graphics
 | pages = 167–183
 | title = An algorithm for computing the union, intersection or difference of two polygons
 | volume = 13
 | year = 1989}}</ref>

<ref name=mccallum-avis>{{cite journal
 | last1 = McCallum | first1 = Duncan
 | last2 = Avis | first2 = David | author2-link = David Avis
 | doi = 10.1016/0020-0190(79)90069-3
 | issue = 5
 | journal = [[Information Processing Letters]]
 | mr = 552534
 | pages = 201–206
 | title = A linear algorithm for finding the convex hull of a simple polygon
 | volume = 9
 | year = 1979}}</ref>

<ref name=meisters>{{cite journal
 | last = Meisters | first = G. H.
 | doi = 10.2307/2319703
 | issue = 6
 | journal = [[The American Mathematical Monthly]]
 | jstor = 2319703
 | mr = 0367792
 | pages = 648–651
 | title = Polygons have ears
 | volume = 82
 | year = 1975}}</ref>

<ref name=milnor>{{cite journal
 | last = Milnor | first = John W.
 | doi = 10.2307/1969467
 | journal = Annals of Mathematics |series=2nd Series
 | pages = 248–257
 | title = On the total curvature of knots
 | volume = 52
 | year = 1950}}</ref>

<ref name=niven-zuckerman>{{cite journal
 | last1 = Niven | first1 = Ivan | author1-link = Ivan M. Niven
 | last2 = Zuckerman | first2 = H. S.
 | doi = 10.1080/00029890.1967.12000095
 | journal = [[The American Mathematical Monthly]]
 | mr = 225216
 | pages = 1195–1200
 | title = Lattice points and polygonal area
 | volume = 74
 | issue = 10 | jstor = 2315660 
 | year = 1967}}</ref>

<ref name=oks-sharir>{{cite journal
 | last1 = Oks | first1 = Eduard
 | last2 = Sharir | first2 = Micha | author2-link = Micha Sharir
 | doi = 10.1007/s00454-005-1206-y
 | issue = 2
 | journal = [[Discrete & Computational Geometry]]
 | mr = 2195052
 | pages = 223–240
 | title = Minkowski sums of monotone and general simple polygons
 | volume = 35
 | year = 2006| doi-access = free
 }}</ref>

<ref name=palfrader-held>{{cite journal
 | last1 = Palfrader | first1 = Peter
 | last2 = Held | first2 = Martin
 | date = February 2015
 | doi = 10.1080/16864360.2014.997637
 | issue = 4
 | journal = Computer-Aided Design and Applications
 | pages = 414–424
 | title = Computing mitered offset curves based on straight skeletons
 | volume = 12| doi-access = free
 }}</ref>

<ref name=preparata-shamos>{{cite book
 | last1 = Preparata | first1 = Franco P. | author1-link = Franco P. Preparata
 | last2 = Shamos | first2 = Michael Ian | author2-link = Michael Ian Shamos
 | doi = 10.1007/978-1-4612-1098-6
 | isbn = 978-1-4612-1098-6
 | page = 18
 | publisher = Springer-Verlag
 | series = Texts and Monographs in Computer Science
 | title = Computational Geometry: An Introduction
 | url = https://books.google.com/books?id=_p3eBwAAQBAJ&pg=PA18
 | year = 1985}}</ref>

<ref name=preparata-supowit>{{cite journal
 | last1 = Preparata | first1 = Franco P. | author1-link = Franco P. Preparata
 | last2 = Supowit | first2 = Kenneth J.
 | doi = 10.1016/0020-0190(81)90091-0
 | issue = 4
 | journal = [[Information Processing Letters]]
 | pages = 161–164
 | title = Testing a simple polygon for monotonicity
 | volume = 12
 | year = 1981}}</ref>

<ref name=quintas-supnick>{{cite journal
 | last1 = Quintas | first1 = L. V.
 | last2 = Supnick | first2 = Fred
 | doi = 10.2307/2313333
 | issue = 9
 | journal = [[The American Mathematical Monthly]]
 | jstor = 2313333
 | mr = 188872
 | pages = 977–980
 | title = On some properties of shortest Hamiltonian circuits
 | volume = 72
 | year = 1965}}</ref>

<ref name=rich2>{{cite book
 | last1 = Richmond | first1 = Bettina | author1-link = Bettina Richmond
 | last2 = Richmond | first2 = Thomas
 | edition = 2nd
 | isbn = 9781470472047
 | page = 421
 | publisher = American Mathematical Society
 | series = Pure and Applied Undergraduate Texts
 | title = A Discrete Transition to Advanced Mathematics
 | url = https://books.google.com/books?id=BQDUEAAAQBAJ&pg=PA421
 | volume = 63
 | year = 2023}}</ref>

<ref name=schirra>{{cite conference
 | last = Schirra | first = Stefan
 | editor1-last = Halperin | editor1-first = Dan
 | editor2-last = Mehlhorn | editor2-first = Kurt
 | book-title = Algorithms – ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15–17, 2008. Proceedings
 | doi = 10.1007/978-3-540-87744-8_62
 | pages = 744–755
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = How reliable are practical point-in-polygon strategies?
 | url = http://wwwisg.cs.uni-magdeburg.de/ag/pointInPolygonReliability/pointPolygon.pdf
 | volume = 5193
 | year = 2008}}</ref>

<ref name=snoeyink>{{cite book
 | last = Snoeyink | first = Jack
 | editor1-last = Toth | editor1-first = Csaba D.
 | editor2-last = O'Rourke | editor2-first = Joseph
 | editor3-last = Goodman | editor3-first = Jacob E.
 | contribution = Point Location
 | contribution-url = https://www.csun.edu/~ctoth/Handbook/chap38.pdf
 | edition = 3rd
 | pages = 1005–1023
 | publisher = Chapman and Hall/CRC Press
 | title = Handbook of Discrete and Computational Geometry
 | year = 2017
 | isbn = 978-1-498-71139-5}}</ref>

<ref name=thomassen>{{cite journal
 | last = Thomassen | first = Carsten | author-link = Carsten Thomassen (mathematician)
 | doi = 10.1080/00029890.1992.11995820
 | issue = 2
 | journal = [[The American Mathematical Monthly]]
 | jstor = 2324180
 | mr = 1144352
 | pages = 116–130
 | title = The Jordan-Schönflies theorem and the classification of surfaces
 | volume = 99
 | year = 1992}}</ref>

<ref name=toussaint>{{cite journal
 | last = Toussaint | first = Godfried | authorlink = Godfried Toussaint
 | doi = 10.2307/2324033
 | issue = 1
 | journal = [[The American Mathematical Monthly]]
 | jstor = 2324033
 | mr = 1083611
 | pages = 31–35
 | title = Anthropomorphic polygons
 | volume = 98
 | year = 1991}}</ref>

<ref name=trefethen-driscoll>{{cite conference
 | last1 = Trefethen | first1 = Lloyd N. | author1-link = Nick Trefethen
 | last2 = Driscoll | first2 = Tobin A.
 | book-title = Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998)
 | mr = 1648186
 | pages = 533–542
 | series = Documenta Mathematica
 | title = Schwarz–Christoffel mapping in the computer era
 | year = 1998}}</ref>

<ref name=urrutia>{{cite book
 | last = Urrutia | first = Jorge | author1-link = Jorge Urrutia Galicia
 | editor1-last = Sack | editor1-first = Jörg-Rüdiger | editor1-link = Jörg-Rüdiger Sack
 | editor2-last = Urrutia | editor2-first = Jorge
 | contribution = Art gallery and illumination problems
 | doi = 10.1016/B978-044482537-7/50023-1
 | isbn = 0-444-82537-1
 | location = Amsterdam
 | mr = 1746693
 | pages = 973–1027
 | publisher = North-Holland
 | title = Handbook of Computational Geometry
 | year = 2000}}</ref>

}}

== External links ==
*{{Mathworld | urlname=SimplePolygon | title=Simple polygon }}

{{Polygons}}

{{bots|deny=Citation bot}}
[[Category:Types of polygons]]