Point in Polygon

Quick Revisit
USE WHEN: testing if a point lies inside, outside, or on the boundary of a polygon
INVARIANT: ray casting — count edge crossings; odd = inside, even = outside
TIME: O(n) general polygon; O(log n) convex polygon | SPACE: O(n)
CLASSIC BUG: ray through a vertex — count edge only if endpoints straddle the ray's y-coordinate
PRACTICE: 08-ladder-mixed

Given a polygon and a query point, determine whether the point lies inside, outside, or on the boundary. This is one of the most common geometry subtasks -- it shows up everywhere from interactive problems to area queries.

Difficulty: [Intermediate]Prerequisites: Geometry BasicsCF Rating Range: 1400 -- 1900

Why This Matters

Many geometry problems don't ask "is the point inside?" directly. Instead, it appears as a subroutine: checking feasibility of a placement, filtering points by region, or validating a solution. Having a reliable, bug-free point-in-polygon test saves you from reinventing it under contest pressure.

The Ray Casting Idea

Shoot a horizontal ray from the query point toward $+ \infty$ . Count how many polygon edges it crosses. Odd count -> inside. Even count -> outside.

  Outside       Inside        Outside
     .     ___________
          /     .     \         .
         /             \
        /_______________\

  Ray ->  - - -|= = = = =|- - - - ->
         0 crossings  1 crossing  2 crossings
         (even=out)   (odd=in)    (even=out)

This works for any simple polygon (convex or not) in $O (n)$ per query.

Edge Cases That Will Burn You

Ray passes through a vertex: count the edge only if its endpoints straddle the ray's y-coordinate (one strictly above, one on or below). This avoids double-counting.
Point exactly on an edge: check separately using cross product (collinearity) + bounding box.
Horizontal edges: skip them entirely -- they can't contribute a crossing with a horizontal ray.

Winding Number (Alternative)

Sum the signed angles subtended by each edge as seen from the query point. If the total is $\pm 2 π$ , the point is inside. More robust for some applications but slower if you use atan2. In practice, ray casting is preferred for contests.

O(log n) Test for Convex Polygons

When the polygon is convex (and you know it), you can do much better. The fan-binary-search test runs in $O (\log n)$ per query — but it has preconditions that, if violated, silently produce wrong answers.

Assumptions the binary search depends on:

The polygon is strictly convex. All cross products around the boundary have the same sign. If three consecutive vertices are collinear, the angle-sector layout still works only if you treat the collinear vertex as a separator — many implementations do not. Either deduplicate collinear hull points first, or use the inclusive variant of the test (compare with >= 0 / <= 0 instead of strict > / <).
Vertices are listed in counter-clockwise order, and the order is consistent (no reversal, no shuffling).
The pivot $v_{0}$ is an extreme vertex in some direction (e.g., the leftmost-then-bottom vertex, or any hull vertex that is on the boundary of the convex hull of the polygon). The convex-hull construction in 02-convex-hull returns vertices starting at the leftmost-bottom point; that vertex is a safe pivot. A pivot in the interior of a polygon edge breaks the monotonic angular sweep that the binary search relies on.
The query is not at $v_{0}$ . Handle that as a separate base case before the binary search.

Under these preconditions, the polygon is a fan of triangles $(v_{0}, v_{1}, v_{2}), (v_{0}, v_{2}, v_{3}), \dots, (v_{0}, v_{n - 2}, v_{n - 1})$ , and the angles $∠ v_{0} v_{i}$ increase monotonically. Binary search on $i$ to find the sector containing $q$ , then check which side of the closing edge $v_{i} v_{i + 1}$ it falls on.

        v3 ---- v2
       / \    / |
      /   \  /  |      Binary search by angle from v0
     /     v0   |      to find which "slice" the query
    /       \   |      point falls into.
   v4 ------ v1

Failure mode if you misuse this test: if the polygon is not guaranteed convex, the angular sectors around $v_{0}$ overlap or reverse, the binary search converges to the wrong slice, and the final cross-product check returns the opposite sign in roughly half the cases. Symptom: the test passes a CCW square but fails on a general polygon. Fix: fall back to the $O (n)$ ray cast above, or compute the convex hull first.

Implementation

cpp

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
struct P { ll x, y; };

ll cross(P a, P b, P c) {
    return (ll)(b.x-a.x)*(c.y-a.y) - (ll)(b.y-a.y)*(c.x-a.x);
}

bool on_segment(P a, P b, P p) {
    return cross(a, b, p) == 0
        && min(a.x,b.x) <= p.x && p.x <= max(a.x,b.x)
        && min(a.y,b.y) <= p.y && p.y <= max(a.y,b.y);
}

// Returns: 1 = inside, 0 = on boundary, -1 = outside
int point_in_polygon(vector<P>& poly, P p) {
    int n = poly.size(), cnt = 0;
    for (int i = 0; i < n; i++) {
        P a = poly[i], b = poly[(i+1)%n];
        if (on_segment(a, b, p)) return 0;
        // ray casting: count crossings of rightward ray from p
        if ((a.y <= p.y) != (b.y <= p.y)) {
            // x-coordinate of intersection of edge with y = p.y
            ll num = (ll)(p.y - a.y) * (b.x - a.x);
            ll den = b.y - a.y;
            // p.x < intersection_x  ⟹  crossing is to the right
            if ((num > (ll)p.x * den) == (den > 0)) cnt++;
        }
    }
    return cnt % 2 == 1 ? 1 : -1;
}

Integer-only note: the implementation above avoids floating point entirely by rearranging the inequality. This eliminates epsilon issues -- a huge win for contest geometry.

Detailed Ray Casting Trace

Consider polygon $P = [(1, 1), (5, 1), (6, 4), (3, 6), (0, 3)]$ and query point $Q = (3, 3)$ .

  y
  6 |        P3(3,6)
  5 |       / \
  4 |      /   P2(6,4)
  3 | P4(0,3)   Q*- - - - - - - -> +inf     Ray from Q
  2 |    \      / \      |
  1 |    P0(1,1)---P1(5,1)
  0 +--+--+--+--+--+--+---> x
    0  1  2  3  4  5  6

  Ray y = 3, starting at x = 3, going right:

  Edge P4->P0 (0,3)->(1,1): straddles y=3? y4=3, y0=1.
    (3 <= 3) != (1 <= 3)? (true) != (true) -> NO. Skip.

  Edge P0->P1 (1,1)->(5,1): both y=1 < 3. No straddle. Skip.

  Edge P1->P2 (5,1)->(6,4): straddles y=3? (1<=3)!=(4<=3)?
    true != false -> YES.
    Intersection x = 5 + (3-1)*(6-5)/(4-1) = 5 + 2/3 ~= 5.67
    5.67 > 3 -> crossing is RIGHT of Q. Count: 1  OK

  Edge P2->P3 (6,4)->(3,6): straddles y=3? (4<=3)!=(6<=3)?
    false != false -> NO. Skip.

  Edge P3->P4 (3,6)->(0,3): straddles y=3? (6<=3)!=(3<=3)?
    false != true -> YES.
    Intersection x = 3 + (3-6)*(0-3)/(3-6) = 3 + 3 = 6... wait:
    x = 3 + (3-6)*(0-3)/(3-6) = 3 + (-3)(-3)/(-3) = 3 + (-3) = 0
    0 < 3 -> crossing is LEFT of Q. Don't count.

  Total crossings to the right: 1 (odd) -> Q is INSIDE OK

Gotchas

Trap	What happens	Fix
Forgetting boundary check	Point on edge reported as inside/outside	Check `on_segment` first
Vertex touching ray	Double-counted crossing	Use strict/non-strict y comparison asymmetry
Floating-point polygon	Epsilon creep in cross product	Use integer coords or careful EPS
Collinear vertices in polygon	Degenerate edges of length 0	Skip zero-length edges

Self-Test

Q1. Why does ray casting use a horizontal ray specifically, and what changes if you use a vertical ray instead?
Answer
The direction is arbitrary -- a vertical ray works identically. Horizontal is conventional because the "straddle" check compares y-coordinates, which is slightly simpler. With a vertical ray, you'd compare x-coordinates instead and count crossings above/below.

Q2. A polygon has 1000 vertices. You need to answer 100,000 point-in-polygon queries. What's the best approach if the polygon is (a) general, (b) convex?
Answer
(a) General polygon: $O(n)$ per query via ray casting -> $O(n \cdot q) = O(10^8)$, borderline. No faster general method without preprocessing. (b) Convex polygon: $O(\log n)$ per query via the fan binary search -> $O(q \log n) \approx 10^6$, very fast.

Q3. Why does the implementation check on_segment before ray casting, not after?
Answer
A point exactly on an edge is a boundary case that ray casting handles ambiguously -- depending on the ray direction, it might count as 0 or 1 crossings. Checking first and returning early (`return 0`) gives a clean, deterministic answer without epsilon issues.

Q4. The winding number method sums signed angles. Why is it more robust than ray casting for polygons with self-intersections?
Answer
For self-intersecting polygons, the "inside" is ambiguous under the even-odd rule (ray casting). The winding number counts how many times the polygon wraps around the point, giving a well-defined answer even when edges cross. A winding number != 0 means "inside" under the nonzero winding rule.

Practice Problems

Problem	What it tests
CF 166B -- Polygons	Convex point-in-polygon
CSES -- Point in Polygon	General ray casting with boundary
Kattis -- Point in Polygon	Classic implementation exercise
SPOJ -- INPOLY	Ray casting with large polygons
Any problem with "polygon" + "query point"	This is the subroutine

Point in Polygon ​

Why This Matters ​

The Ray Casting Idea ​

Edge Cases That Will Burn You ​

Winding Number (Alternative) ​

O(log n) Test for Convex Polygons ​

Implementation ​

Detailed Ray Casting Trace ​

Gotchas ​

Self-Test ​

Practice Problems ​

Further Reading ​