Editing Point in polygon (section)

{{short description|Determining where a point is in relation to a coplanar polygon}}
[[Image:Simple polygon.svg|right|thumb|An example of a simple 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]], [[geographic information system]]s (GIS), [[motion planning]], and [[computer-aided design]] (CAD).

An early description of the problem in computer graphics shows two common approaches ([[ray casting]] and angle summation) in use as early as 1974.<ref>[[Ivan Sutherland]] et al.,"A Characterization of Ten Hidden-Surface Algorithms"  1974, ''[[ACM Computing Surveys]]'' vol. 6 no. 1.</ref>

An attempt of computer graphics veterans to trace the history of the problem and some tricks for its solution can be found in an issue of the ''Ray Tracing News''.<ref>{{cite| url=https://graphics.stanford.edu/pub/Graphics/RTNews/html/rtnv3n4.html#art22| title=Point in Polygon, One More Time...| author=Mark Vandewettering| author2=Eric Haines| author3=Edward John Kalenda| author4=Richard Parent| author5=Sam Uselton| author6="Zap" Andersson| author7=Bruce Holloway| display-authors=3| journal=Ray Tracing News| volume=3| number=4| date=October 1, 1990}}</ref>