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.
Read more about this topic: Point In Polygon
Famous quotes containing the words winding and/or number:
“The prevalence of suicide, without doubt, is a test of height in civilization; it means that the population is winding up its nervous and intellectual system to the utmost point of tension and that sometimes it snaps.”
—Havelock Ellis (1859–1939)
“I can’t quite define my aversion to asking questions of strangers. From snatches of family battles which I have heard drifting up from railway stations and street corners, I gather that there are a great many men who share my dislike for it, as well as an equal number of women who ... believe it to be the solution to most of this world’s problems.”
—Robert Benchley (1889–1945)