Point in Polygon - Winding Number Algorithm

Winding Number Algorithm

Another algorithm 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. One way to compute the winding number is to sum up the angles subtended by each side of the polygon. However, this involves costly inverse trigonometric functions, which generally makes this algorithm slower than 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 2*PI (or multiples of 2*PI) only, it is sufficient to track through which quadrants the polygon winds, as it turns around the test point, which makes the winding number algorithm comparable in speed to counting the boundary crossings.

For simple polygons, both algorithms will always give the same results for all points. However, for complex polygons, the algorithms may give different results for points in the regions where the polygon intersects itself, where the polygon does not have a clearly defined inside and outside. In this case, the former algorithm is called the even-odd rule.