Point in Polygon Algorithm

The point-in-polygon problem in computational geometry asks whether a given point on a plane lies inside, outside or exactly on the boundary of a polygon, a question that comes up throughout computer graphics, computer vision, geographic information systems, motion planning and computer-aided design. The oldest and most widely used solution is the ray casting algorithm, also called the crossing number or even-odd rule algorithm and documented since 1962, which draws a ray from the test point in any fixed direction and counts how many times that ray crosses the polygon's edges, relying on the Jordan curve theorem to guarantee that an even number of crossings means the point is outside and an odd number means it is inside; implementations have to handle the edge cases of a ray that happens to pass exactly through a vertex and of rounding error when a point sits very close to the boundary. An alternative approach computes the point's winding number with respect to the polygon, where a nonzero winding number means the point is inside; the direct version of this method needs comparatively expensive trigonometric calculations, but Dan Sunday published an optimized winding-number algorithm in 2001 that tracks quadrant transitions instead of computing explicit angles and so runs about as fast as ray casting.