Point in Polygon

General (possibly non-convex) polygon — $O(n)$

Ray casting: shoot a horizontal ray from $p$ and count edge crossings. Odd = inside.

// returns 1 inside, 0 outside, -1 on the boundary
int inPolygon(P p, const vector<P>& poly) {
    int n = poly.size(), cnt = 0;
    for (int i = 0; i < n; i++) {
        P a = poly[i], b = poly[(i + 1) % n];
        if (orient(a, b, p) == 0 && dot(p - a, p - b) <= 0) return -1;   // on an edge
        if (a.y > b.y) swap(a, b);
        if (p.y <= a.y || p.y > b.y) continue;        // HALF-OPEN in y
        if (orient(a, b, p) > 0) cnt++;
    }
    return cnt & 1;
}

The half-open $y$-range is the whole trick

Using p.y <= a.y || p.y > b.y — inclusive at one end, exclusive at the other — makes each vertex count exactly once and makes horizontal edges harmless. Symmetric conditions double-count vertices and produce wrong answers on inputs where the ray happens to pass through one.

Everything here is exact integer arithmetic; there is no epsilon and no intersection point.

Convex polygon, many queries — $O(\log n)$

With the polygon given CCW, binary search the angular sector from vertex 0:

// poly is CCW, poly[0] is the lowest-then-leftmost vertex
int inConvex(P p, const vector<P>& poly) {
    int n = poly.size();
    if (orient(poly[0], poly[1], p) < 0) return 0;
    if (orient(poly[0], poly[n-1], p) > 0) return 0;
 
    int lo = 1, hi = n - 1;
    while (hi - lo > 1) {                             // find the wedge containing p
        int mid = (lo + hi) / 2;
        if (orient(poly[0], poly[mid], p) >= 0) lo = mid; else hi = mid;
    }
    int o = orient(poly[lo], poly[lo + 1], p);
    if (o < 0) return 0;
    if (o == 0) return -1;                            // on the boundary
    return 1;
}

Preprocess by rotating the polygon so poly[0] is the bottom-most (then left-most) vertex.

Winding number — the alternative

Sum the signed angle subtended by each edge. Non-zero winding means inside. Equivalent to ray casting for simple polygons, but differs for self-intersecting ones: ray casting uses the even-odd rule, winding uses the non-zero rule. Graphics APIs let you choose; contest problems almost always mean simple polygons where they agree.

An exact integer version counts upward and downward crossings separately rather than summing angles.

The decision table

Situation	Method	Cost
One query, any polygon	ray casting	$O(n)$
Many queries, convex	angular binary search	$O(\log n)$
Many queries, non-convex	triangulate + point location, or a sweep	$O(\log n)$ after $O(n\log n)$
Many queries, offline	sort queries by $x$ and sweep	$O((n+q)\log n)$
Point in a triangle	three orientation tests, or barycentric coordinates	$O(1)$
Point in a circle	compare squared distances	$O(1)$
Point in a half-plane	one orientation test	$O(1)$

Point in a triangle

bool inTriangle(P p, P a, P b, P c) {
    int d1 = orient(a, b, p), d2 = orient(b, c, p), d3 = orient(c, a, p);
    bool hasNeg = (d1 < 0) || (d2 < 0) || (d3 < 0);
    bool hasPos = (d1 > 0) || (d2 > 0) || (d3 > 0);
    return !(hasNeg && hasPos);                       // all the same sign (or zero)
}

Handles either orientation of the triangle and counts boundary points as inside.

Boundary handling

Decide up front whether “on the boundary” counts as inside, and make it explicit in the return value (as the -1 above). Problems differ, and a silent choice is a silent bug.

Related queries

Query	Method
Is the polygon convex?	all orientations agree
Is a segment inside the polygon?	both endpoints inside and no proper crossing with any edge
Is one polygon inside another?	all vertices inside and no edge crossings
Nearest boundary point	minimum over distToSegment for each edge
Which triangle of a triangulation contains $p$?	point location (a trapezoidal map, or a KD-tree)

See also: Polygon Area · Orientation Test · Convex Hull