Inside or outside
Given a polygon and a query point, the point in polygon test decides whether the point lies inside the boundary. The classic method is ray casting: imagine firing a ray from the point off to infinity and counting how many polygon edges it crosses.
The parity rule
The count of crossings determines the answer:
- An odd number of crossings means the point is inside.
- An even number of crossings means the point is outside.
Each time the ray crosses an edge it flips between inside and outside, so the parity of the total captures the final state. A horizontal ray going to the right is a common choice because the crossing test then reduces to simple coordinate comparisons.
Edge cases that bite
The hard part is when the ray grazes a vertex or runs along an edge. A careless implementation may count one crossing as two. The usual fix is a consistent half open rule: count an edge only if the point's height falls within a half open vertical range of that edge. Convex polygons admit a faster alternative that checks the point against every edge with the orientation test instead.
Key idea
Cast a ray and count edge crossings: odd means inside and even means outside, with a half open rule to handle vertex grazes consistently.