Point in Polygon — Ray Casting + Winding Number

Ray casting

boolean inside(Point p, Point[] poly) {
  boolean in = false;
  int n = poly.length;
  for (int i = 0, j = n - 1; i < n; j = i++) {
    if ((poly[i].y > p.y) != (poly[j].y > p.y) &&
        p.x < (poly[j].x - poly[i].x) * (p.y - poly[i].y) / (poly[j].y - poly[i].y) + poly[i].x)
      in = !in;
  }
  return in;
}

Winding number

Sum signed angle subtended by consecutive vertices from p. Nonzero → inside (2π for simple polygons).

Complex polygons

Ray casting: even-odd rule. Winding: nonzero rule. Different for self-intersecting polygons.

Complexity

O(N) per query. O(log N) with preprocessing for convex or via slab decomposition.