Hilbert Curve's own Pitfalls section proves that porting Z-order Curve's single-window range query — scan every curve index between the query rectangle's two corners — is not just slower on a Hilbert curve, it is wrong: a point genuinely inside the rectangle can sit outside that window entirely and never get scanned. That page names the real fix and stops short of building it: "decompose the query rectangle into several curve-index sub-ranges instead of one — genuinely more involved than Z-order's single-window trick, and not built here." This page is that decomposition.
The identical ten points, 16×16 grid, and query rectangle x∈[6,11], y∈[6,13] as the
Hilbert Curve page — deliberately, so the two
demos are directly comparable. Press Step or Run to watch the
recursion walk the domain as nested quadrants: a faded dashed box means skip (no
overlap with the rectangle at all, its whole subtree is dropped in one step); a solid dashed box
means split (the rectangle's edge cuts through this box, recurse into its four
quadrants); a filled box means match (this box sits entirely inside the rectangle,
so its whole curve-index range is a match — no need to look at a single cell inside it
individually). Watch J in particular: the point Hilbert Curve's own demo scanned right past.
A Hilbert curve is built by recursively splitting the domain into four quadrants and visiting them one after another, never interleaved — that is exactly what makes it a curve at all, rather than four independent smaller curves. A direct consequence: every axis-aligned, power-of-two-sized, power-of-two-aligned square sub-region of the domain is a single contiguous block of curve indices. Z-order's own Pitfalls section leans on the same fact for a different purpose (proving its single-window trick is safe); here it becomes the basis for a correct query on a curve where that trick fails.
The decomposition walks the same recursive quadrant structure the curve itself is built from, top-down from the full domain. At each box: if it doesn't overlap the query rectangle at all, skip its entire subtree — none of its cells can possibly match, no matter how many there are. If it sits entirely inside the rectangle, its whole index range is a match — emit it as one range, again without looking at a single cell. Only when a box's edge genuinely straddles the rectangle's boundary does the recursion split it into four quadrants and repeat. This bottoms out on its own: a 1×1 box can never partially overlap a rectangle (it's either fully in or fully out), so recursion never needs to go deeper than the domain's own bit-depth. The resulting ranges come out already sorted (curve index only ever increases as the recursion proceeds) and are merged where two adjacent ranges' boundaries touch, collapsing runs of neighboring matched quadrants into one range instead of several.
Hilbert Curve's own xy2d/d2xy
bit-rotation formulation doesn't expose a quadrant's bounding box directly — it processes one bit
per level in an already-rotated local frame, which is exactly why that page's Pitfalls section
called this "genuinely more involved." The construction below builds the identical curve a
different way, tracking each quadrant's real corner coordinates as it recurses (Wikipedia's
"generate2d" formulation, restated here): (xi,xj) and (yi,yj) are the
current square's two edge vectors, halved and rotated/reflected at each level exactly the way the
curve's own path folds. Cross-checked bijectively against xy2d over the full 16×16
domain used in the demo above: all 256 cells agree on all 256 indices.
// Same curve as xy2d/d2xy, built by tracking each quadrant's real
// corner instead of bit-rotating an already-local (x, y).
function corner(x0, y0, xi, xj, yi, yj) {
return [
Math.min(x0, x0 + xi, x0 + yi, x0 + xi + yi),
Math.min(y0, y0 + xj, y0 + yj, y0 + xj + yj),
];
}
// Recursively decompose [qx0,qx1] x [qy0,qy1] into contiguous curve-index
// ranges. n0 must be a power of 2 (same silent requirement as xy2d/d2xy).
function decompose(n0, qx0, qy0, qx1, qy1) {
const ranges = [];
let idx = 0;
function walk(x0, y0, xi, xj, yi, yj, size) {
const [bx0, by0] = corner(x0, y0, xi, xj, yi, yj);
const bx1 = bx0 + size - 1, by1 = by0 + size - 1;
const cellCount = size * size;
const noOverlap = bx1 < qx0 || bx0 > qx1 || by1 < qy0 || by0 > qy1;
if (noOverlap) { idx += cellCount; return; }
const fullyIn = bx0 >= qx0 && bx1 <= qx1 && by0 >= qy0 && by1 <= qy1;
if (fullyIn) { ranges.push([idx, idx + cellCount - 1]); idx += cellCount; return; }
const s2 = size / 2;
walk(x0, y0, yi / 2, yj / 2, xi / 2, xj / 2, s2);
walk(x0 + xi / 2, y0 + xj / 2, xi / 2, xj / 2, yi / 2, yj / 2, s2);
walk(x0 + xi / 2 + yi / 2, y0 + xj / 2 + yj / 2, xi / 2, xj / 2, yi / 2, yj / 2, s2);
walk(x0 + xi / 2 + yi, y0 + xj / 2 + yj, -yi / 2, -yj / 2, -xi / 2, -xj / 2, s2);
}
walk(0, 0, 0, n0, n0, 0, n0);
// merge adjacent ranges
const merged = [];
for (const r of ranges) {
if (merged.length && merged[merged.length - 1][1] + 1 === r[0]) merged[merged.length - 1][1] = r[1];
else merged.push(r.slice());
}
return merged;
}Note there is no separate base case for a single cell (size === 1): the overlap
check alone already forces fullyIn true whenever a 1×1 box isn't skipped outright (a
1-wide, 1-tall box can't partially straddle anything), so the general case handles it without extra
code — the same "bottoms out on its own" fact from the previous section, visible directly in the
code rather than just asserted.
Verified first, on this page's own demo: the decomposition above finds all three real
matches (F, G, and J — the point Hilbert Curve's own naive scan missed) while scanning fewer
indices than the broken trick did, with zero false positives. The naive single-window scan
on this exact rectangle covers d∈[40,156], 117 indices, and still misses J (d=209).
This page's decomposition produces 9 quadrant-level ranges that merge down to 5:
[40,43], [108,115], [124,147], [156,159], [208,215] — 48 indices total,
exactly the query rectangle's own area (6×8 cells), covering J, F, and G and nothing else. Checked
at scale, not just on this demo: 20,000 random rectangles on a 32×32 domain against a brute-force
oracle, 0 mismatches; an exhaustive sweep of all 1,296 rectangles on an 8×8 grid,
also 0 mismatches. Average 11.3 merged ranges per query across that 20,000-trial
sweep.
Computing a quadrant's bounding box from bx0 + size instead of
bx0 + size - 1 doesn't miss anything — it silently reintroduces the false-positive
problem this technique exists to avoid. The off-by-one makes every box look one cell wider
and taller than it really is, which lets boxes that only almost overlap the rectangle sneak
past the "skip" check, and lets boxes that only almost fit be counted as fully matched.
Measured directly on this page's own demo rectangle: 45 raw ranges instead of 9 (still 9 after
merging, not 5), 63 indices scanned instead of 48 — 15 of them
false positives that would need a further filter to discard, quietly reintroducing exactly the
per-candidate check-and-discard cost this decomposition was built to eliminate. At scale: 20,000
random trials on a 32×32 domain, wrong 99.4% of the time, 453,464
total false-positive indices returned, but 0 real matches ever missed — a
performance bug, not a correctness one, but one that erases the entire advantage over Z-order's own
already-cheaper single-window trick. Minimal counterexample (8×8 grid): querying the single cell
(0,1) returns indices {0,1} instead of just {1} — the extra
width lets the unrelated neighboring cell (0,0) sneak into a supposedly single-cell
box.
Computing a quadrant's bounding box from only (x0, xi) and (y0,
yj) — assuming the two edge vectors are always pure axis vectors — drops real matches, the
same failure this page's own parent demonstrates for a completely different reason. After
an odd number of the 90° rotations the curve's own construction applies, an edge vector that starts
axis-aligned picks up a component on the other axis (the xj/yi terms the
correct corner() above accounts for); ignoring them computes a corner that's just
plain wrong, not merely off by one. On this page's own demo, this bug drops the range
[208,211] — which contains J's index, d=209 — and replaces it with the unrelated range
[44,47], silently missing J exactly the way the naive single-window scan did, for an
unrelated reason. At scale: 20,000 random trials on a 32×32 domain, wrong 97.0% of
the time, 382,699 real matches missed in total (plus 209,069 unrelated false
positives). Minimal counterexample (8×8 grid): a 1-cell-wide, 3-cell-tall rectangle at
x=0, y∈[0,2] — the correct answer is {0,1,14}, this bug returns
{0,1}, dropping index 14 without any indication anything went wrong.
This is the piece that makes a Hilbert-ordered index usable for range queries at all in practice, not just for the bulk-load-order role Hilbert Curve's own "Where it shows up" section describes. A system that has already committed to Hilbert ordering — for its better path locality, or because it's reusing an existing Hilbert-ordered key space — needs exactly this recursive decomposition to answer "which rows/keys fall in this 2D window" correctly; without it, the honest options are either accepting Z-order's worse locality in exchange for its safe single-window query, or running this page's more involved decomposition on top of Hilbert's better locality. Geospatial and time-series databases that index by a Hilbert-curve key (space-filling-curve libraries built on top of systems like HBase or a Hilbert R-tree's own underlying sorted array) use this exact recursive-quadrant technique, often under the name "curve covering" or "range covering," to turn one 2D window into the handful of 1D index scans the underlying sorted storage actually supports.
Decompose: not a single clean closed form. The recursion visits at most one
node per box in a perfect quadtree over the n×n domain (4 children per level,
log₂ n levels), so O(n) node visits in the worst case — reached only when
the rectangle's boundary is maximally jagged relative to the grid, cutting through nearly every box
down to individual cells. In practice far fewer: this page's own 16×16 demo needed 41
node visits to produce 9 ranges (5 after merging) covering a 48-cell rectangle out of 256 total
cells; the 20,000-trial sweep above averaged 11.3 merged ranges per query on a 32×32 domain.
Query: each of the k merged ranges costs one binary search plus a
linear scan of that range against the sorted index — O(log n + scanned) per range,
identical to Z-order Curve's own single-window
cost, just paid k times instead of once. Unlike that single window, every cell scanned
this way is a genuine match — no filtering step needed afterward. Space:
O(n), unchanged from Hilbert Curve —
this page adds a query algorithm, not a new structure. This site's guide, Choosing a Spatial Structure, sets Hilbert
Curve itself aside as answering a different question than its main comparison; this page inherits
that same exclusion rather than forcing a fit.