← all categories

Point In Polygon aa16bff9

Point-in-polygon test for a simple polygon (convex or not). Returns 1 if strictly inside, 0 if strictly outside, -1 if on the boundary.

Time: O(n). tested

content/geometry/point-in-polygon.h

int pointInPolygon(vector<Point> &poly, Point p) {
    int n = (int)poly.size();
    bool inside = false;
    for (int i = 0, j = n - 1; i < n; j = i++) {
        Point a = poly[i], b = poly[j];
        // on-segment check: collinear and within the bounding box
        if (abs(p.cross(a, b)) < 1e-9 && min(a.x,b.x) - 1e-9 <= p.x && p.x <= max(a.x,b.x) + 1e-9
                                       && min(a.y,b.y) - 1e-9 <= p.y && p.y <= max(a.y,b.y) + 1e-9) return -1;
        if ((a.y > p.y) != (b.y > p.y)) {
            ld xCross = a.x + (p.y - a.y) * (b.x - a.x) / (b.y - a.y);
            if (p.x < xCross) inside = !inside;
        }
    }
    return inside ? 1 : 0;
}