Point in Polygon (Ray Casting & Winding Number)
Point in Polygon tests whether a query point lies inside, on the boundary, or outside a 2D polygon in O(n) via Ray Casting (general polygons) or O(log n) via binary search (convex polygons).
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code
Point in Polygon (Ray Casting & Winding Number)
Given a simple polygon $P$ with $n$ vertices and a query point $Q$, Point in Polygon determines whether $Q$ is inside, on the boundary, or outside $P$.
- For any simple polygon (even non-convex!): shoot a horizontal ray from $Q$ to $+\infty$ and count edge crossings (odd = inside, even = outside) in $O(n)$.
- For a convex polygon: binary search the triangle fan from vertex
P[0]in $O(\log n)$!
Practice Problems
Intermediate
1. Exact Ray-Casting Point-in-Polygon Test (Inside / Boundary / Outside)
Classify a query point relative to an arbitrary simple polygon using exact integer/half-open edge crossings (avoiding double-counting shared vertices!).
Approach: First check onSegment for every edge. Then count edges strictly straddling q.y ((a.y > q.y) != (b.y > q.y)) whose intersection x-coordinate lies strictly to the right of q.x. Time: $O(n)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Pt { long long x, y; };
long long cross(const Pt& a, const Pt& b, const Pt& c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool onSeg(const Pt& a, const Pt& b, const Pt& p) {
return cross(a, b, p) == 0 &&
std::min(a.x, b.x) <= p.x && p.x <= std::max(a.x, b.x) &&
std::min(a.y, b.y) <= p.y && p.y <= std::max(a.y, b.y);
}
std::string pointInPolygon(const std::vector<Pt>& poly, const Pt& q) {
int n = static_cast<int>(poly.size());
bool inside = false;
for (int i = 0; i < n; ++i) {
Pt a = poly[i], b = poly[(i + 1) % n];
if (onSeg(a, b, q)) return "BOUNDARY";
if ((a.y > q.y) != (b.y > q.y)) {
// Check if crossing x > q.x without division
if (a.y > b.y) std::swap(a, b);
if (cross(a, b, q) > 0) inside = !inside;
}
}
return inside ? "INSIDE" : "OUTSIDE";
}
int main() {
std::vector<Pt> sq = {{0, 0}, {4, 0}, {4, 4}, {0, 4}};
std::cout << pointInPolygon(sq, {2, 2}) << " "
<< pointInPolygon(sq, {4, 2}) << " "
<< pointInPolygon(sq, {5, 2}) << "\n"; // INSIDE BOUNDARY OUTSIDE
return 0;
}
</details>
---