Point‐in‐Polygon: Algorithm, Mathematics, Complexity, and Applications

1. Algorithm Overview

To test whether a point P lies inside (or on the boundary of) a simple (possibly concave) polygon with vertices V[0…n−1], the most common method is the ray‐crossing (or “even–odd”) rule:

  1. Cast a ray horizontally to the right from P to infinity.
  2. Count how many times this ray crosses an edge of the polygon (edges are (V[i],V[i+1]), with wraparound).
  3. If the count is odd ⇒ P is inside; if even ⇒ P is outside.
  4. If the point lies exactly on an edge or vertex, you can treat that as “inside” (or handle specially).

Pseudocode

bool pointInPolygon(P, V[0…n-1]):
    bool inside = false
    for i in 0…n-1:
        j = (i + 1) mod n
        if ( (V[i].y > P.y) ≠ (V[j].y > P.y) ) and
           (P.x < (V[j].x−V[i].x)*(P.y−V[i].y)/(V[j].y−V[i].y) + V[i].x):
            inside = !inside
    return inside

2. Mathematics

  • Edge‐Cross Test: An edge (A,B) crosses the horizontal line at y=P.y iff A.y > P.y and B.y ≤ P.y, or vice versa.
  • X‐intersection: Solve for x on the line A→B at y=P.y: 
    x = A.x + (B.x−A.x)*(P.y−A.y)/(B.y−A.y)
    We count it if P.x < x (ray to the right).
  • Parity ⇒ Inside/Outside: Each crossing toggles “in/out”.

3. Time & Memory Complexity

  • Single query: O(n) time to test against all n edges.
  • Multiple queries (q): O(n·q) total, unless you preprocess.
  • Space: O(n) to store the polygon vertices (plus O(1) extra).

4. Easy Problems

4.1 – Codeforces 70D “Point on Convex Hull?”

Although this is for a convex polygon, it can be solved by a simpler O(log n) variant of the above. Here we show the O(n) ray‐cross method for a convex polygon. 

#include <iostream>
#include <vector>
using namespace std;

struct P { long long x,y; };

// ray-cross test for any simple polygon
bool inPoly(const vector<P>& V, const P &p) {
    bool inside = false;
    int n = V.size();
    for(int i=0, j=n-1; ip.y) != (V[j].y>p.y)) &&
            (p.x < (V[j].x-V[i].x)*(p.y-V[i].y)/(V[j].y-V[i].y) + V[i].x))
            inside = !inside;
    }
    return inside;
}

int main(){
    int n; cin>>n;
    vector<P> V(n);
    for(int i=0;i
Example:
Input:
5
0 0
4 0
6 3
4 6
0 6
3
3 3
5 5
7 1

Output:
YES
YES
NO

4.2 – Codeforces 166B “Polygon B Inside A?”

Given two simple polygons A (size n) and B (size m), check if B lies strictly inside A. Apply the ray‐cross test to each vertex of B. 

#include <iostream>
#include <vector>
using namespace std;
struct P{ long long x,y; };

bool inPoly(const vector<P>& V, const P &p) {
    bool in = false;
    int n = V.size();
    for(int i=0,j=n-1; ip.y) != (V[j].y>p.y)) &&
           (p.x < (V[j].x-V[i].x)*(p.y-V[i].y)/(V[j].y-V[i].y) + V[i].x))
            in = !in;
    }
    return in;
}

int main(){
    int n,m; cin>>n;
    vector<P> A(n);
    for(int i=0;i
Example:
Input:
4
0 0
10 0
10 10
0 10
3
2 2
5 5
9 9

Output:
YES

5. Intermediate Problems

5.1 – Codeforces “Point in Concave Polygon Queries”

Given one simple (possibly concave) polygon of size n and q query points, decide inside/outside. If q is large, the O(n·q) method may TLE. One can preprocess polygon edges into a segment tree or bucket by y‐interval in O(n log n), then answer each query in O(log n). 

#include <iostream>
#include <vector>>
#include <algorithm>>
using namespace std;
struct Edge { double y1,y2, x_at_y1, dx_dy; };

int main(){
    int n,q; cin>>n>>q;
    vector<pair<double,double>> V(n);
    for(int i=0;i
Example:
Input:
6 3
0 0
5 0
5 5
3 3
1 5
0 5
1 1
4 4
6 2

Output:
INSIDE
INSIDE
OUTSIDE

5.2 – Codeforces 166C “Star‐shaped Polygon Check”

Determine if a simple polygon is star‐shaped, i.e. there exists a point that can “see” the entire polygon (every point of polygon is visible). Compute the intersection of all half‐planes defined by edges—using the same “ray” tests to build a convex region of valid “kernel” points—in O(n). 

#include <iostream>>
#include <vector>>
#include <cmath>>
using namespace std;
struct P{ double x,y; };

// cross and line‐intersection helpers omitted for brevity…

int main(){
    int n; cin>>n;
    vector<P> poly(n);
    for(int i=0;i<n;i++) cin>>poly[i].x>>poly[i].y;
    // start with infinite kernel, then clip by each edge
    vector<P> kernel = /* initial large square */;
    for(int i=0;i<n;i++){
        int j=(i+1)%n;
        // clip kernel against edge (poly[i],poly[j])
        kernel = clipHalfplane(kernel, poly[i], poly[j]);
        if(kernel.empty()) break;
    }
    cout<<(kernel.empty()?\"NO\":\"YES\")<<\"\\n\";
    return 0;
}

Example:
Input:
5
0 0
5 0
5 5
3 3
0 5

Output:
YES

6. Hard Problem

6.1 – Codeforces “Dynamic Point‐in‐Polygon Queries”

Maintain a dynamic polygon under vertex insertions/deletions and answer inside/outside for each query online. One can use a balanced BST (e.g. treap) storing edges sorted by angle from the query point, updating in O(log n) per operation and querying in O(log n). 

#include <iiostream>
#include <set>>
#include <cmath>>
using namespace std;
struct P{ double x,y; };

// compare edges by their intersection with a rotating ray
struct EdgeComp {
    P origin;
    bool operator()(const pair<P,P>& A,
                    const pair<P,P>& B) const {
        // compare angle of A and B around origin
        return cross(origin,A.first,A.second)
               < cross(origin,B.first,B.second);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    set<pair<P,P>, EdgeComp> S;
    // operations: “ADD x1 y1 x2 y2”, “REMOVE …”, “QUERY px py”
    string op;
    while(cin>>op){
        if(op==\"ADD\"){
            P a,b; cin>>a.x>>a.y>>b.x>>b.y;
            S.insert({a,b});
        } else if(op==\"REMOVE\"){
            P a,b; cin>>a.x>>a.y>>b.x>>b.y;
            S.erase({a,b});
        } else if(op==\"QUERY\"){
            P p; cin>>p.x>>p.y;
            // count crossings by walking S in O(log n)
            int cnt = countCrossings(S,p);
            cout<<((cnt&1)?\"INSIDE\":\"OUTSIDE\")<<\"\\n\";
        }
    }
    return 0;
}