Chapter 121

Point in Polygon

Cast a ray from the point to infinity (e.g., to the right). Count how many polygon edges it crosses. Odd = inside, even = outside. Handle edge cases where the ray passes through vertices.

Ray Casting

C++ — point in polygon (ray casting)

bool point_in_polygon(Point p, vector& poly) {
    int n = poly.size();
    bool inside = false;
    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)
            inside = !inside;
    }
    return inside;
}

// O(N) per query. For many queries, precompute for convex polygons.