⚙️AlgorithmIntermediate

Point in Polygon

Key Points

  • •
    Point-in-polygon decides whether a point lies outside, inside, or on the boundary of a polygon.
  • •
    Ray casting counts how many times a horizontal ray from the point crosses polygon edges; an odd count means inside.
  • •
    Winding number sums signed angle turns around the point; a nonzero sum means inside.
  • •
    Robust implementations must special-case points on edges and avoid double-counting crossings at vertices.
  • •
    For convex polygons, you can locate the containing triangle by binary search in O( n) time.
  • •
    Use integer arithmetic and orientation tests with 128-bit intermediates to avoid precision bugs.
  • •
    Adopt a half-open interval rule on y-coordinates to make ray-casting consistent.
  • •
    Pre-check bounding boxes to quickly reject obvious outside points in batch queries.

Prerequisites

  • →2D vectors and basic operations — Point differences form vectors, and cross/dot products are defined on vectors.
  • →Orientation (CCW) test — Determines left/right/collinear relations used in all PIP methods.
  • →Binary search — Used to locate the triangle sector in the convex polygon method.
  • →Integer overflow and 128-bit arithmetic — Ensures robust cross product computations for large coordinates.
  • →Triangle point containment — Final step in convex method reduces to checking within a triangle.
  • →Modular indexing / cyclic arrays — Iterating edges requires wrapping from the last vertex to the first.

Detailed Explanation

Tap terms for definitions

01Overview

Point in Polygon (PIP) is a classic computational geometry problem: given a polygon and a query point, determine if the point is outside, inside, or exactly on the polygon’s boundary. Two mainstream techniques dominate: ray casting (also called the even–odd rule) and the winding number test. Ray casting shoots a conceptual horizontal ray to the right from the point and counts how many times this ray crosses polygon edges; an odd count implies inside, even implies outside. The winding number method measures how many times the polygon winds around the point by summing signed angle changes; a nonzero total indicates the point is inside. For convex polygons, there is a faster O(\log n) solution using binary search and orientation tests to find which triangle fan sector might contain the point. Correctness and robustness hinge on careful handling of edge cases such as rays passing through vertices, horizontal edges, and points exactly on edges or vertices. In competitive programming and graphics, PIP is used in hit-testing, clipping, GIS queries, and collision checks. Implementations can be made numerically stable using integer arithmetic with 128-bit intermediates for cross products, avoiding floating-point pitfalls.

02Intuition & Analogies

Imagine you’re standing at the query point and shining a laser pointer directly to the right. Each time your beam crosses a fence segment (an edge of the polygon), you flip a light switch: off to on, on to off. If after scanning all fences the light is on, you’re inside; if it’s off, you’re outside. That is ray casting in a nutshell. Now think of winding number: hold a compass at your point and walk along the fence in order. As you move from one fence post to the next, your compass needle turns some angle to keep pointing toward the moving vertex. If by the time you finish the loop your compass has turned a net of one full revolution (or more), the fence has wrapped around you—you are inside. If the compass ends up with zero net rotation, you’re outside. For convex polygons, picture a fan made of triangles sharing a common hinge at vertex 0. Your point lies in exactly one triangular slice or none. You can find the right slice by asking binary search style questions: is the point to the left of this fan rib or to the right? By halving the search space repeatedly, you quickly locate the correct sector, then do a small triangle containment check. Across all methods, the tricky scenario is when your laser hits a fence post exactly: do you count it once or twice? The fix is to be consistent, e.g., only count crossings that go upward and treat horizontal edges and vertices with a half-open rule.

03Formal Definition

Let P be a polygon defined by ordered vertices V = (, , , ) with edges = (, ). For a query point q, define the ray r(t) = q + t(1, 0) for t 0. Ray casting defines the crossing number C(q) as the number of edges that intersect r(t), counting each edge under a consistent half-open convention on y to avoid vertex double counts. Then q is inside if C(q) is odd and outside if even; q is on-boundary if q lies on any . The winding number method defines the winding number wn(q) as the total signed angle swept by the polygon around q, typically computed as wn(q) = ((-q, -q), (-q, -q)). If wn(q) 0, then q is inside; if wn(q) = 0, outside; again with explicit boundary checks. For convex polygons with vertices in counterclockwise order, q lies inside if and only if it is to the left of every directed edge; operationally, one tests that q lies inside triangle fan sectors formed by and binary searches the correct sector using orientation predicates. Orientation is captured by the sign of the 2D cross product cross(a, b) = - , where the sign indicates left turn (>0), right turn (<0), or collinear (=0).

04When to Use

Use ray casting when the polygon can be arbitrary (simple but not necessarily convex), and you need a straightforward O(n) per query method with minimal preprocessing. It is great for single or few queries and is easy to implement robustly with integer math. Use the winding number method for polygons with possible self-touching structures where even–odd parity could differ from the intended inside; winding detects multiple wraps and holes when properly defined, although handling holes often requires an outer–inner ring model. Prefer the convex polygon binary search method when the polygon is guaranteed convex and you have many queries: O(\log n) per query gives a substantial speedup, common in computational geometry and physics engines. In competitive programming, if constraints include up to 2e5 vertices and 2e5 queries and the polygon is convex, the binary search method is near-mandatory. If coordinates are integers within 32-bit range, adopt 128-bit intermediates for cross products to stay safe from overflow. Consider pre-checks like bounding box rejection or spatial indexing when doing massive batch queries to reduce constant factors.

⚠️Common Mistakes

  • Vertex double-counting in ray casting: counting an intersection when the ray meets a vertex and again when it meets the adjacent edge. Fix this with a half-open rule on y (e.g., treat edges as [minY, maxY) for crossing tests) and by excluding perfectly horizontal edges from crossing counts.
  • Ignoring points on edges: many solutions forget to return boundary separately. Always check collinearity and that the point projects within the segment’s bounding box before computing crossings.
  • Floating-point instability: computing intersections with doubles and then doing equality comparisons leads to flaky outcomes. Prefer integer arithmetic with 128-bit intermediate cross products; if using floating point, use eps tolerances and never rely on exact equality.
  • Non-CCW or non-convex input for the convex method: the binary search trick assumes a strictly convex polygon in counterclockwise order. If the input is clockwise or has collinearities/repeated points, reorder and deduplicate or fall back to O(n) methods.
  • Mishandling horizontal edges: including them in crossing counts can overcount. Either skip horizontal edges for counting purposes or consistently apply the y half-open convention.
  • Overflow in cross products: 64-bit products may overflow when coordinates approach 1e9. Use __int128 for products before casting the sign.
  • Forgetting modular edge indexing: when iterating edges, always wrap i+1 with modulo n to include the closing edge.

Key Formulas

2D Orientation Cross Product

Explanation: The sign of this value tells whether c is left of, right of, or collinear with the directed segment . Positive means left turn, negative means right turn, and zero means collinear.

Crossing Number

Explanation: C(q) counts how many edges the rightward ray from q intersects, using a consistent half-open rule. The parity of C(q) determines inside/outside in ray casting.

Winding Number via Angle Sum

Explanation: Adds the signed angles subtended by consecutive vertices around q. A nonzero winding number indicates the polygon wraps around q and thus q is inside.

Left-of-All-Edges Test

Explanation: For a CCW convex polygon, being to the left of every edge means the point lies inside or on the boundary. Strictly positive means strictly inside.

Time Complexities

Explanation: General polygons require O(n) per query for ray casting or winding number. Convex polygons support O( n) per query using binary search over the triangle fan.

Batch Complexity Summation

Explanation: When analyzing multiple queries or preprocessing steps that involve cumulative work, this identity helps bound total operations. It shows growth is quadratic in n for nested loops.

Complexity Analysis

For an n-vertex polygon, both ray casting and winding number perform a constant amount of work per edge, leading to O(n) time per query. Space usage is O(1) beyond the storage of the polygon itself if we stream through edges. The primary constant factors come from conditional logic handling the half-open rule and potential division if you compute intersection x-coordinates; our recommended integer-only orientation-based crossing test avoids divisions, improving robustness and often speed. For convex polygons in counterclockwise order, we can reduce query time to O( n) using binary search. We fix one anchor vertex v0 and perform an angular search among the rays to find the sector containing the query point; subsequent membership reduces to an O(1) point-in-triangle test. This approach uses O(1) extra space and yields large speedups when answering many queries against a static convex polygon. In batch-query scenarios (Q queries), complexities are O(Qn) for general polygons and O(Q n) for convex polygons. If needed, preprocessing like building an AABB or sorting edges by y can improve practical performance (e.g., sweep-line or bucketed acceleration), but worst-case asymptotics remain as stated. With 64-bit coordinates up to about 1e9, we must compute cross products in 128-bit to prevent overflow; this does not change asymptotic complexity but ensures correctness. Boundary checks add only O(1) per edge and don’t affect big-O.

Code Examples

Robust Ray Casting with Boundary Detection (Even–Odd Rule)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Point {
5    long long x, y;
6};
7
8static inline __int128 cross128(long long ax, long long ay, long long bx, long long by) {
9    return (__int128)ax * (__int128)by - (__int128)ay * (__int128)bx;
10}
11
12static inline __int128 cross(const Point& a, const Point& b, const Point& c) {
13    // cross((b - a), (c - a))
14    return cross128(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
15}
16
17static inline int sgn128(__int128 v) {
18    if (v > 0) return 1;
19    if (v < 0) return -1;
20    return 0;
21}
22
23static bool onSegment(const Point& a, const Point& b, const Point& p) {
24    if (sgn128(cross(a, b, p)) != 0) return false; // not collinear
25    // within bounding box
26    return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
27           min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
28}
29
30// Returns: 2 if on boundary, 1 if strictly inside, 0 if outside
31int pointInPolygonRayCast(const vector<Point>& poly, const Point& q) {
32    int n = (int)poly.size();
33    bool inside = false;
34    for (int i = 0, j = n - 1; i < n; j = i++) {
35        const Point &a = poly[j], &b = poly[i];
36        // Boundary check first
37        if (onSegment(a, b, q)) return 2;
38        // Apply half-open rule on y: include lower endpoint, exclude upper
39        bool y1 = (a.y <= q.y);
40        bool y2 = (b.y > q.y);
41        if (y1 != y2) {
42            // Edge crosses the horizontal line at y = q.y
43            // Determine if the intersection is to the right of q.x without division.
44            // If cross((b - a), (q - a)) > 0 for an upward crossing (b.y > a.y), toggle.
45            __int128 cr = cross(a, b, q);
46            bool up = (b.y > a.y);
47            if ((cr > 0) == up) inside = !inside;
48        }
49    }
50    return inside ? 1 : 0;
51}
52
53int main() {
54    ios::sync_with_stdio(false);
55    cin.tie(nullptr);
56
57    // Example polygon: a simple pentagon
58    vector<Point> poly = {{0,0}, {5,0}, {6,3}, {3,6}, {0,3}}; // CCW
59
60    vector<Point> queries = {
61        {3, 3},   // inside
62        {6, 3},   // on vertex (boundary)
63        {5, 1},   // inside near edge
64        {7, 3},   // outside
65        {3, 6},   // on vertex (boundary)
66        {2, 0}    // on edge (boundary)
67    };
68
69    for (auto q : queries) {
70        int res = pointInPolygonRayCast(poly, q);
71        if (res == 2) cout << "boundary\n";
72        else if (res == 1) cout << "inside\n";
73        else cout << "outside\n";
74    }
75    return 0;
76}
77

This program implements the even–odd rule using integer arithmetic and a half-open y-interval to avoid vertex double counting. It first checks if the point lies on any edge (boundary). For counting crossings, it toggles the inside flag only on upward or downward crossings that meet the half-open condition, using a sign test on the cross product to avoid floating divisions.

Time: O(n)Space: O(1) extra (O(n) to store the polygon)
Winding Number Method with Signed Angle Increments
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Point { long long x, y; };
5
6static inline __int128 cross128(long long ax, long long ay, long long bx, long long by) {
7    return (__int128)ax * (__int128)by - (__int128)ay * (__int128)bx;
8}
9
10static inline __int128 cross(const Point& a, const Point& b, const Point& c) {
11    return cross128(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
12}
13
14static inline int sgn128(__int128 v) {
15    if (v > 0) return 1; if (v < 0) return -1; return 0;
16}
17
18static bool onSegment(const Point& a, const Point& b, const Point& p) {
19    if (sgn128(cross(a, b, p)) != 0) return false;
20    return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
21           min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
22}
23
24// Returns: 2 boundary, 1 inside, 0 outside
25int pointInPolygonWinding(const vector<Point>& poly, const Point& q) {
26    int n = (int)poly.size();
27    int wn = 0;
28    for (int i = 0; i < n; ++i) {
29        int j = (i + 1) % n;
30        const Point &a = poly[i], &b = poly[j];
31        if (onSegment(a, b, q)) return 2;
32        // upward crossing
33        if (a.y <= q.y && b.y > q.y) {
34            if (cross(a, b, q) > 0) ++wn;
35        }
36        // downward crossing
37        else if (a.y > q.y && b.y <= q.y) {
38            if (cross(a, b, q) < 0) --wn;
39        }
40    }
41    return (wn != 0) ? 1 : 0;
42}
43
44int main() {
45    ios::sync_with_stdio(false);
46    cin.tie(nullptr);
47
48    vector<Point> poly = {{0,0}, {5,0}, {6,3}, {3,6}, {0,3}}; // CCW simple
49    vector<Point> qs = {{3,3}, {7,3}, {0,2}, {6,3}};
50    for (auto q : qs) {
51        int res = pointInPolygonWinding(poly, q);
52        if (res == 2) cout << "boundary\n";
53        else if (res == 1) cout << "inside\n";
54        else cout << "outside\n";
55    }
56    return 0;
57}
58

This code computes the winding number by incrementing on upward crossings when the point is left of the edge and decrementing on downward crossings when the point is right of the edge. If the winding number is nonzero, the point lies inside. A boundary check is performed first to report edge cases correctly.

Time: O(n)Space: O(1) extra (O(n) polygon storage)
O(log n) Point Location in a Convex Polygon (Binary Search + Triangle Test)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Point { long long x, y; };
5
6static inline __int128 cross128(long long ax, long long ay, long long bx, long long by) {
7    return (__int128)ax * (__int128)by - (__int128)ay * (__int128)bx;
8}
9
10static inline __int128 cross(const Point& a, const Point& b, const Point& c) {
11    return cross128(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
12}
13
14static inline int sgn128(__int128 v) { if (v > 0) return 1; if (v < 0) return -1; return 0; }
15
16static bool onSegment(const Point& a, const Point& b, const Point& p) {
17    if (sgn128(cross(a, b, p)) != 0) return false;
18    return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
19           min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
20}
21
22// Assumes: P is strictly convex, CCW, size >= 3. Returns 2 boundary, 1 inside, 0 outside.
23int pointInConvexPolygon(const vector<Point>& P, const Point& q) {
24    int n = (int)P.size();
25    const Point &o = P[0];
26    // Quick boundary checks on edges adjacent to o
27    if (onSegment(o, P[1], q) || onSegment(o, P[n-1], q)) return 2;
28    // Outside the fan wedge?
29    if (sgn128(cross(o, P[1], q)) < 0) return 0; // right of o->P1
30    if (sgn128(cross(o, P[n-1], q)) > 0) return 0; // left of o->P(n-1)
31    // Binary search to find sector [l, l+1] containing q
32    int l = 1, r = n - 1;
33    while (r - l > 1) {
34        int m = (l + r) >> 1;
35        if (sgn128(cross(o, P[m], q)) >= 0) l = m; else r = m;
36    }
37    // Now test within triangle (o, P[l], P[l+1])
38    const Point &a = o, &b = P[l], &c = P[l+1];
39    if (onSegment(b, c, q)) return 2;
40    // For CCW triangle, inside if q is left of each edge
41    __int128 c1 = cross(a, b, q);
42    __int128 c2 = cross(b, c, q);
43    __int128 c3 = cross(c, a, q);
44    if (c1 == 0 || c2 == 0 || c3 == 0) return 2; // touches boundary
45    if (c1 > 0 && c2 > 0 && c3 > 0) return 1;
46    return 0;
47}
48
49int main() {
50    ios::sync_with_stdio(false);
51    cin.tie(nullptr);
52
53    // Regular octagon (CCW)
54    vector<Point> P = {
55        {2,0},{4,0},{6,2},{6,4},{4,6},{2,6},{0,4},{0,2}
56    };
57    vector<Point> qs = {{3,3}, {7,3}, {4,0}, {1,5}};
58    for (auto q : qs) {
59        int res = pointInConvexPolygon(P, q);
60        if (res == 2) cout << "boundary\n";
61        else if (res == 1) cout << "inside\n";
62        else cout << "outside\n";
63    }
64    return 0;
65}
66

Assuming a strictly convex polygon in CCW order, this function rejects points outside the initial wedge (edges from vertex 0 to vertices 1 and n−1). It then binary-searches among the rays from vertex 0 to find the sector containing the query point and concludes with an O(1) point-in-triangle test using orientation. All cross products use 128-bit intermediates to prevent overflow.

Time: O(log n)Space: O(1) extra (O(n) polygon storage)