Editing Point in polygon (section)

==Winding number algorithm==
Another technique used to check if a point is inside a polygon is to compute the given point's [[winding number]] with respect to the polygon. If the winding number is non-zero, the point lies inside the polygon. This algorithm is sometimes also known as the ''[[nonzero-rule]] algorithm''.

One way to compute the winding number is to sum up the [[Subtended angle|angles subtended]] by each side of the polygon.<ref name="Hormann">{{Cite journal | doi=10.1016/S0925-7721(01)00012-8 | title=The point in polygon problem for arbitrary polygons | journal=Computational Geometry | volume=20 | issue=3 | pages=131 | year=2001| last1=Hormann | first1=K. | last2=Agathos | first2=A. | doi-access=free }}</ref> However, this involves costly [[inverse trigonometric functions]], which generally makes this algorithm performance-inefficient (slower) compared to the ray casting algorithm. Luckily, these inverse trigonometric functions do not need to be computed. Since the result, the sum of all angles, can add up to 0 or <math>2\pi</math> (or multiples of <math>2\pi</math>) only, it is sufficient to track through which quadrants the polygon winds,<ref>{{citation | last=Weiler | first=Kevin | editor-last=Heckbert | editor-first=Paul S. | contribution=An Incremental Angle Point in Polygon Test | isbn=0-12-336155-9 | location=San Diego, CA, USA | pages=16–23 | publisher=Academic Press Professional, Inc. | title=Graphics Gems IV | year=1994 | url=https://archive.org/details/isbn_9780123361554/page/16 }}</ref> as it turns around the test point, which makes the winding number algorithm comparable in speed to counting the boundary crossings.

[[File:Winding number algorithm example.svg|thumb|Visualization of Dan Sunday's [[winding number]] algorithm. A winding number of 0 means the point is outside the polygon; other values indicate the point is inside the polygon]]
An improved algorithm to calculate the winding number was developed by Dan Sunday in 2001.<ref name="sunday">{{ cite web | last=Sunday | first=Dan | url=http://geomalgorithms.com/a03-_inclusion.html | title=Inclusion of a Point in a Polygon | year=2001 | url-status=usurped | archive-url=https://web.archive.org/web/20130126163405/http://geomalgorithms.com/a03-_inclusion.html | archive-date=26 January 2013}}</ref> It does not use angles in calculations, nor any trigonometry, and functions exactly the same as the ray casting algorithms described above. Sunday's algorithm works by considering an infinite horizontal ray cast from the point being checked. Whenever that ray crosses an edge of the polygon, Juan Pineda's edge crossing algorithm (1988)<ref>{{ cite conference | url=https://www.cs.drexel.edu/~david/Classes/Papers/comp175-06-pineda.pdf | title=A Parallel Algorithm for Polygon Rasterization | first=Juan | last=Pineda | journal=Computer Graphics | volume=22 | number=4 | date=August 1988 | conference=[[SIGGRAPH]]'88 | location=[[Atlanta]] | access-date=8 August 2021 }}</ref> is used to determine how the crossing will affect the winding number. As Sunday describes it, if the edge crosses the ray going "upwards", the winding number is incremented; if it crosses the ray "downwards", the number is decremented. Sunday's algorithm gives the correct answer for nonsimple polygons, whereas the boundary crossing algorithm fails in this case.<ref name="sunday"/>