Given a simple polygon and a query point, is the point inside? Unlike every entry in this site's
Convex Hull category, the polygon here doesn't have to be convex —
it can bend inward as sharply as it likes. That rules out the shortcut a convex shape would allow
(checking which side of every edge's line the point falls on, and requiring it to be consistently
"inside" for all of them at once): a concave polygon can have a point that's on the inner side of
every nearby edge yet still sits outside, in a notch the boundary cuts back through. The test that
works regardless of convexity is ray casting: draw a ray from the query point off
to infinity in any fixed direction, and count how many times it crosses the polygon's boundary. An
odd number of crossings means the point is inside; an even number, including zero, means it's
outside. Like Line Segment Intersection,
this site's other Geometry entry, the whole test reduces to per-edge arithmetic — no sorting, no
recursion — but here every one of the polygon's n edges has to be checked once per
query, so the cost is O(n), not O(1).
A seven-vertex arrow: a rectangular body with a triangular head, the head's two "wings" cut back in to meet the tip — two genuine concave notches. Six preset query points; the ray is drawn rightward from the point to the edge of the canvas, every polygon edge the ray actually crosses highlights, and the crossing count decides the verdict live from the point's real coordinates. upper notch is the one to check first: it sits inside the bounding box of the arrow's head, on the inner side of the wing's slanted edge if you only glance at that one edge, but the ray from it crosses the boundary zero times — outside.
Think of the ray as a path from the query point out to somewhere unambiguously outside the polygon. Each time that path crosses the boundary, it switches which region it's in — inside to outside, or outside to inside — because a simple polygon's boundary is exactly the set of places where "inside" and "outside" meet. Start at the query point in whatever region it's actually in, end far away in the outside region for certain; the number of switches along the way tells you whether the start and end regions are the same (even number of switches) or different (odd). Since the end is always outside, an odd crossing count means the start — the query point — was inside, and an even count means it was already outside.
The one piece of care needed is what happens when the ray doesn't cleanly cross an edge in its
interior but grazes a vertex instead — two edges meeting exactly at the ray's height. Testing each
edge with (yi > y) !== (yj > y), using the endpoint's y-coordinate
strictly above the query's y on both sides, means that of the two edges sharing a
vertex sitting exactly on the ray, at most one of them ever registers — never both, never neither, for
a vertex where the boundary genuinely passes through top-to-bottom. (A vertex that's a genuine peak or
valley — both adjoining edges heading the same direction, up or down, in y — can register
on both sides at once, but two crossings cancel out anyway: a ray tangent to a peak shouldn't count as
entering the polygon at all, and it doesn't.) A horizontal edge, where yi equals
yj, fails the strict inequality on both sides identically and never registers regardless
of the query point's x — which also sidesteps a division by that edge's zero
y-span before it would ever happen.
function pointInPolygon(point, poly) {
let inside = false;
for (let i = 0, j = poly.length - 1; i < poly.length; j = i++) {
const xi = poly[i].x, yi = poly[i].y;
const xj = poly[j].x, yj = poly[j].y;
// does edge (j, i) cross the rightward ray from `point`?
const crosses = ((yi > point.y) !== (yj > point.y)) &&
(point.x < (xj - xi) * (point.y - yi) / (yj - yi) + xi);
if (crosses) inside = !inside; // each real crossing flips inside/outside
}
return inside;
}A concave notch defeats any per-edge "which side" shortcut, even though ray casting
handles it without special-casing. This page's own upper notch preset,
(340, 80), sits inside the bounding box of the arrow's triangular head and on the
polygon-interior side of the wing's single slanted edge — a check against that one edge alone would
call it inside. Ray casting disagrees, correctly: cast rightward from (340, 80), and the
ray crosses the polygon's actual boundary zero times before leaving the canvas,
because the notch cut back out of the head means the boundary never separates that point from the
outside at all. Verified independently before writing a line of this page's HTML: a from-scratch
winding-number implementation — a genuinely different algorithm, accumulating signed turn angles
around the point rather than counting crossings — agreed with ray casting on every one
of 50,000 random query points against this exact polygon, including this preset. That
winding-number test is now its own page — see
Winding Number Algorithm for where the two
methods stop agreeing (a polygon that winds around itself more than once).
Changing the strict > to >= on both sides of the crossing
test looks like a harmless simplification and isn't one. It still agreed with the
canonical version across the same 200,000 random trials used above — because the divergence only
shows up for a query point sitting at exactly the same height as a vertex, a probability-zero event
for random floating-point coordinates. Targeting that case directly finds real, verified
divergences: at query point (200, 100) — sitting exactly on this polygon's top edge —
the canonical (strict-both-sides) version reports inside; the
>=-both-sides version reports outside. Same divergence, mirrored, at
(200, 280) on the bottom edge. A stress test that only samples randomly, however many
trials it runs, will never surface a bug that only manifests at an exact coincidence — this one
needed a query built specifically to land on the boundary, not just a lot of them.
Time: O(n) per query, where n is the polygon's vertex
count — every edge gets one constant-time crossing test, no early exit possible in general since a
point past the last crossing could always still flip the answer. Space:
O(1) beyond the polygon itself, just a running boolean and loop counters. If the same
polygon is queried repeatedly, a preprocessing structure can answer each later query in
O(log n) instead of rescanning every edge — see
Slab Decomposition, this site's own such
structure, straightforward to build but O(n²) in the worst case; a fancier
randomized incremental trapezoidal map
gets preprocessing down to O(n log n) expected while keeping the same
O(log n) query.
This site's guide, Choosing a Geometry Algorithm, places this entry first among the site's eleven Geometry pages: the default answer when a polygon is asked to contain a point once, or a handful of times, and might change between queries — reach for Winding Number Algorithm instead the moment the polygon might self-intersect, or for Slab Decomposition/Trapezoidal Map once the same polygon needs to answer many queries.