Editing Simple polygon (section)

== 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}}