AntInLoop

Point in Polygon (Ray Casting & Winding Number)

Point in Polygon tests whether a query point lies inside, on the boundary, or outside a 2D polygon in O(n) via Ray Casting (general polygons) or O(log n) via binary search (convex polygons).

Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code

Point in Polygon (Ray Casting & Winding Number)

Given a simple polygon $P$ with $n$ vertices and a query point $Q$, Point in Polygon determines whether $Q$ is inside, on the boundary, or outside $P$.

  • For any simple polygon (even non-convex!): shoot a horizontal ray from $Q$ to $+\infty$ and count edge crossings (odd = inside, even = outside) in $O(n)$.
  • For a convex polygon: binary search the triangle fan from vertex P[0] in $O(\log n)$!

Practice Problems

Intermediate

1. Exact Ray-Casting Point-in-Polygon Test (Inside / Boundary / Outside)

Classify a query point relative to an arbitrary simple polygon using exact integer/half-open edge crossings (avoiding double-counting shared vertices!).

Approach: First check onSegment for every edge. Then count edges strictly straddling q.y ((a.y > q.y) != (b.y > q.y)) whose intersection x-coordinate lies strictly to the right of q.x. Time: $O(n)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct Pt { long long x, y; };

long long cross(const Pt& a, const Pt& b, const Pt& c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

bool onSeg(const Pt& a, const Pt& b, const Pt& p) {
    return cross(a, b, p) == 0 &&
           std::min(a.x, b.x) <= p.x && p.x <= std::max(a.x, b.x) &&
           std::min(a.y, b.y) <= p.y && p.y <= std::max(a.y, b.y);
}

std::string pointInPolygon(const std::vector<Pt>& poly, const Pt& q) {
    int n = static_cast<int>(poly.size());
    bool inside = false;
    for (int i = 0; i < n; ++i) {
        Pt a = poly[i], b = poly[(i + 1) % n];
        if (onSeg(a, b, q)) return "BOUNDARY";
        if ((a.y > q.y) != (b.y > q.y)) {
            // Check if crossing x > q.x without division
            if (a.y > b.y) std::swap(a, b);
            if (cross(a, b, q) > 0) inside = !inside;
        }
    }
    return inside ? "INSIDE" : "OUTSIDE";
}

int main() {
    std::vector<Pt> sq = {{0, 0}, {4, 0}, {4, 4}, {0, 4}};
    std::cout << pointInPolygon(sq, {2, 2}) << " "
              << pointInPolygon(sq, {4, 2}) << " "
              << pointInPolygon(sq, {5, 2}) << "\n"; // INSIDE BOUNDARY OUTSIDE
    return 0;
}

</details>

---

Related Algorithms