Point in Polygon
Classify a point as outside, on the boundary, or inside a polygon with a contest-ready ray-crossing routine.
Point in Polygon
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Point-in-polygon is the routine that turns polygon input into actual queries. In contests the goal is usually modest: given a simple polygon and many query points, classify each point as outside, on the boundary, or strictly inside.
When to Use It
Use this when:
the input polygon is fixed and many query points follow,
the statement distinguishes inside from boundary,
you want a simple, reliable predicate rather than heavy geometry machinery.
Core Idea
The standard parity test casts a ray from the query point and counts how many polygon edges cross it. If the number of crossings is odd, the point is inside; if even, it is outside.
Before applying parity, check whether the point lies on an edge. That boundary case should be handled explicitly.
Key Insight
The difficult part is not the odd/even rule. It is choosing a crossing convention that does not double-count vertices. The common fix is to count an edge only when its endpoints straddle the horizontal line in a half-open way.
Operations / Main Technique
test every edge for boundary contact,
apply a ray-crossing parity count,
return a three-way classification.
Worked example.
If a horizontal ray from the query point crosses the polygon boundary three times, the point is inside. If it crosses zero or two times, it is outside. If the point lies on one of the edges, the parity rule is skipped.
Correctness Intuition
A ray from an outside point enters and leaves the polygon in pairs, so the crossing count is even. A ray from an inside point has one unmatched exit, so the count is odd. The boundary check removes degenerate cases where the point lies exactly on the polygon.
Complexity Analysis
For a polygon with \(n\) vertices, one query takes \(O(n)\) time and \(O(1)\) extra memory.
Implementation
The sample code returns:
0for outside,1for boundary,2for inside.For many queries on the same polygon, that linear routine is often enough unless the constraints are very large.
Common Pitfalls
Double-counting vertices in the ray-crossing loop.
Forgetting the boundary case and classifying it by parity.
Assuming the polygon is convex when the problem does not say so.
Using floating-point comparisons when an integer boundary test is available.
Variants / Extensions
Winding-number interpretation instead of parity.
Faster query structures for many points against one polygon.
Convex-polygon queries in \(O(\log n)\) after preprocessing.
Practice Problems
Classify query points relative to a simple polygon.
Count how many points lie strictly inside.
Combine point-in-polygon with polygon area or intersection tasks.
References
Code
Contest-ready reference implementation for the idea explained above.
struct Point {
long long x;
long long y;
};
long long cross(Point a, Point b, Point c) {
long long x1 = b.x - a.x;
long long y1 = b.y - a.y;
long long x2 = c.x - a.x;
long long y2 = c.y - a.y;
return x1 * y2 - y1 * x2;
}
bool on_segment(Point a, Point b, Point p) {
if (cross(a, b, p) != 0) return false;
return 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);
}
int point_in_polygon(const vector<Point>& poly, Point p) {
bool inside = false;
int n = (int)poly.size();
for (int i = 0; i < n; ++i) {
Point a = poly[i];
Point b = poly[(i + 1) % n];
if (on_segment(a, b, p)) {
return 1;
}
bool crosses = (a.y > p.y) != (b.y > p.y);
if (crosses) {
long double x = a.x + (long double)(b.x - a.x) * (p.y - a.y) / (b.y - a.y);
if (x > p.x) {
inside = !inside;
}
}
}
return inside ? 2 : 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.