This site's Z-order Curve already showed one way
to index points with no bespoke tree at all: interleave every coordinate's bits into one sorted flat
array. A Spatial Hash Grid answers the same "which points are near X" question with no
tree either, but by a completely different mechanism — it never sorts anything, and it never looks at
any point other than the one being inserted. Pick a cell size up front, and every point's index is just
(floor(x / cellSize), floor(y / cellSize)) — an integer division, nothing else. Points that
land on the same pair of integers share a bucket. There's no comparison against other points, no
recursive split, no median to compute: inserting a point costs exactly one hash-map lookup, every time,
regardless of how many points are already there.
That makes it the only entry on this site whose entire index is fixed before a single point is ever
inserted. A KD-tree's split points depend on which points
happen to be in the tree; even a Quadtree's boundaries,
though data-independent in shape, only come into existence once a region's point count crosses its
capacity threshold. A grid's cell boundaries exist for every possible coordinate the moment
cellSize is chosen — which is exactly why insert, update, and delete are all O(1): there is
never anything to rebalance, because the structure never changes shape at all.
Fourteen points, one query point Q with a radius circle. Press Step or Run: first each point drops straight into its own grid cell (no comparisons, just an integer divide), then the radius query runs — it works out which cells could possibly hold a point within the radius, checks only those cells' points against the real distance, and leaves every other cell (and every point in it) untouched. Watch the cell count: most of the grid never gets looked at.
Build: for every point p, compute
cx = Math.floor(p.x / cellSize) and cy = Math.floor(p.y / cellSize), and push
p into the bucket keyed by (cx, cy) (a plain Map keyed by a
"cx,cy" string works fine — no fixed-size hash table or collision handling needed, since the
key space is the cell coordinates themselves, not a compressed hash of them). That's the entire build:
one bucket push per point, in any order, with no dependency on any other point.
Query: given a query point q and radius r, any point within
r of q must lie inside the axis-aligned square
[q.x - r, q.x + r] × [q.y - r, q.y + r] — so it must live in a cell whose index falls in
cx ∈ [floor((q.x - r) / cellSize), floor((q.x + r) / cellSize)] and the same for
cy. That's a small, fixed rectangle of cell indices — visit exactly those cells (skipping any
that don't exist in the map at all, since most of a sparse grid's cells hold nothing), and for every point
found in them, check the real distance. A cell's own membership only proves "within one cell-width
in each axis," not "within radius r" — the diagonal of a cell is wider than its side, so a
point can sit in a checked cell and still be farther than r away. That's exactly why every
candidate still needs the real distance check, the same shape of "structure narrows the search, exact math
confirms the answer" every tree-based Spatial entry on this site also relies on — a grid cell is just a
much cheaper thing to compute membership in than a tree node's bounding region.
function cellKey(x, y, cellSize) {
return Math.floor(x / cellSize) + ',' + Math.floor(y / cellSize);
}
function buildGrid(points, cellSize) {
const grid = new Map();
for (const p of points) {
const key = cellKey(p.x, p.y, cellSize);
if (!grid.has(key)) grid.set(key, []);
grid.get(key).push(p);
}
return grid;
}
function rangeQuery(grid, cellSize, q, r) {
const minCx = Math.floor((q.x - r) / cellSize), maxCx = Math.floor((q.x + r) / cellSize);
const minCy = Math.floor((q.y - r) / cellSize), maxCy = Math.floor((q.y + r) / cellSize);
const hits = [];
for (let cx = minCx; cx <= maxCx; cx++) {
for (let cy = minCy; cy <= maxCy; cy++) {
const bucket = grid.get(cx + ',' + cy);
if (!bucket) continue;
for (const p of bucket) {
if (Math.hypot(p.x - q.x, p.y - q.y) <= r) hits.push(p);
}
}
}
return hits;
}
// moving a point: remove it from its OLD cell before re-inserting at the new position
function movePoint(grid, cellSize, p, nx, ny) {
const oldBucket = grid.get(cellKey(p.x, p.y, cellSize));
oldBucket.splice(oldBucket.indexOf(p), 1);
p.x = nx; p.y = ny;
const key = cellKey(p.x, p.y, cellSize);
if (!grid.has(key)) grid.set(key, []);
grid.get(key).push(p);
}Only checking the query point's own cell — wrong 36.2% of the time. The tempting shortcut: since the query point's own cell is already known, just look inside that one bucket and skip computing the whole cell range. It's a plausible reading of "grid lookup" if the mental model is "hash table, single key" rather than "hash table, one key per axis, range of keys per query." Stress-tested directly: 20,000 trials of random point sets (15–35 points each) with the query radius set equal to the cell size, the reference implementation above against a brute-force linear-scan oracle, then a single-cell-only version against the same oracle. The reference implementation matched brute force in all 20,000 trials. The single-cell-only version disagreed in 7,234 — 36.2% of them. Even with the radius shrunk to half a cell width, it's still wrong 6.7% of the time — the bug doesn't need a generously large radius to bite, just a query point that happens to land near a cell boundary with a real neighbor just across it. The demo above is built from exactly this shape: Q's own cell is empty, so a single-cell-only implementation would report zero matches on this page's own example, when the real answer (found by checking the full range) is two.
A moved point left in its old cell — wrong 34.6% of the time, and the buckets never stop
growing. A grid's big advantage over every tree on this site is O(1) update: a game object moves
every frame, and a spatial hash grid can just re-bucket it, no rebalancing required. But
movePoint's first line matters: the point has to be removed from its old cell's
bucket before the new entry goes in. Skip that removal — just insert a fresh record at the new position
and never touch the old one — and the old cell keeps a frozen snapshot of the point at a location it no
longer occupies. Stress-tested directly: 5,000 trials, 25 points each, 15 random moves per trial, querying
with a radius equal to the cell size afterward. The correct (remove-then-insert) implementation matched an
independently-tracked ground truth in all 5,000 trials. The version that never removes the stale entry was
wrong in 1,730 — 34.6% of trials, every one of them a false-positive "ghost" match at
a position the point had already moved away from — even after de-duplicating the query's own result
list by ID, which hides the problem in the 1.7% of trials where the stale record and the live record land
in the same checked range and the duplicate is visible directly. The failure isn't just occasional
wrong answers, either: bucket entries accumulate with every move whether or not a query ever notices. Twenty-five
points that start with 25 total bucket entries end up with 225 after just 200 moves —
9× the entries for the same 25 real points — a leak that grows forever with no
query ever needing to run.
No adaptivity — a fixed cell size can't respond to clustering, and there's no rebalancing to fix it. Every other tree-shaped entry on this site's own Spatial category can restructure around dense regions: a KD-tree's median split still bisects a cluster, a Quadtree still subdivides a crowded box. A grid's cells never split, because they were never built from the data in the first place. Measured directly: 300 points spread uniformly across a 2000×2000 area, cell size 40, touch an average of 1.05 points per radius query across 2,000 trials. The same 300 points crammed into a region a tenth of one cell's width — a realistic worst case, not a contrived one, since real data does cluster — and a query anywhere near that cluster touches every point sharing its cell: exactly 300 of 300 every time the query lands on the cluster's own cell, and an average of 204.82 touched across 2,000 trials with the query point itself randomized nearby. This isn't a bug to fix, since there's no wrong answer here — it's the structural cost of choosing a fixed resolution before seeing the data, and it's why the cell size itself has to be chosen with the data's real density in mind, not picked once and forgotten.
Anywhere objects move every frame and the index has to keep up at the same rate: game engines' broad-phase collision detection (which pairs of objects are even worth a precise collision check this frame?), particle systems, flocking/boids-style neighbor queries in crowd and swarm simulations, and physics engines that need "what's near this object right now" far more often than they need a guaranteed-balanced worst case. The trade that makes it fit there and nowhere else on this site: every tree-based Spatial entry here assumes the data is relatively static between builds, because updating one point can mean re-splitting a subtree. A spatial hash grid assumes the opposite — that the data moves constantly and the index has to be cheap to keep current, not cheap to query on a worst-case adversarial layout.
This site's guide, Choosing a Spatial Structure, compares this entry against the other seven Spatial entries that share the same "index points, query later" question.
Build: O(n) — one bucket push per point, no sorting, no recursion,
no comparison against any other point. Every tree-based entry on this site needs at least
O(n log n) to build.
Insert / update / delete after build: O(1) amortized — a bucket
push, or a bucket splice-then-push for a move. No other structure in this site's Spatial category supports
this: the tree-based entries either don't cover single-point updates at all in their own reference
implementations, or risk needing a rebalance the moment one does.
Query: O(k + m), where k is the number of points actually
found in the checked cells and m is the number of cells checked —
O((r / cellSize + 1)²) for a 2D radius query. On uniformly distributed data with a
sensible cell size, both stay small and roughly constant regardless of n. Under clustering
(see Pitfalls above), k degrades toward n with no bound at all — unlike a
KD-tree or Range Tree, a grid has no structural guarantee to fall back on, because it never adapted to the
data to begin with.
Space: O(n) for the point records themselves, plus one map entry per
non-empty cell — a sparse grid over a large area with few points costs far less than one
entry per possible cell, since empty cells never get a map key at all.