One of the most basic geometric tests is if a point, , is inside a polygon .
The most common method for this test is casting a ray from the point either horizontally or vertically and checking how many times it intersects the polygon. If the number of intersections is odd then is inside . If the number of intersections is even then is outside . In the below illustration the horizontal ray cast from black point intersects the polygon 3 times. Thus the black point is inside the polygon.
There are a few corner cases that have to be carefully handled.
Case 1. The point is on the boundary of the polygon. In this case the algorithm may return true or false because of floating point issues.
Case 2. The casted ray intersects a vertex of the polygon. In this case the naive implementation of the algorithm would return two intersections because of the top line segment and the bottom line segment. The way to fix this is to only count an intersection if (1) it’s not an end-point intersection or (2) it’s an end-point intersection and the end-point of the line segment lies below the casted ray.
Case 3. The casted ray overlaps a line segment, . In this case the casted ray intersects an end-point of the overlapping line segment, and the line segment does not lie below the casted ray. So do not count the line segment intersection(s).
By implementing the special cases this point-in-polygon method should work extremely well. It’s a fast method since the only operations used are compares. The big-O is O(n) where n is the number of line segments for the polygon.