The site's Z-order Curve entry names a Hilbert curve directly and sets it aside: "production systems frequently swap in a Hilbert curve instead of Z-order for the same bit-interleaving role... a genuinely different (and more involved) bit-twiddling scheme, worth its own entry rather than a variant of this one." This page is that entry. Both curves solve the identical problem — turn a 2D point into one integer, sort points by that integer, index the sorted order instead of building a tree — but they disagree about the path through 2D space that produces that integer, and the difference is not cosmetic. Z-order's Morton code jumps between quadrants; a Hilbert curve rotates its own recursive sub-curve at each level specifically so that it never has to. That single design choice buys real, measured locality along the curve itself — and, as this page's Pitfalls section demonstrates on the exact same ten points and query rectangle as the Z-order page, does not mean Z-order's own corner-to-corner range-query trick is safe to carry over unchanged.
The same ten points, same grid, and same query rectangle as the Z-order Curve demo — deliberately, so the two are directly comparable. Press Step or Run to watch the build phase draw the Hilbert curve itself (compare its path to Z-order's zigzag: no diagonal jumps, only single-step moves to a neighboring cell), then watch a query attempt that ports Z-order's own trick verbatim — compute the curve index at each rectangle corner, scan the sorted array between the smaller and larger of the two. Watch what happens to J in particular.
A Hilbert curve is built the same recursive way Z-order's quadrant split is — divide the domain into four quadrants, recurse — but visits those four quadrants in an order that changes based on which quadrant it's already inside, by rotating (and sometimes reflecting) the sub-curve at each level. Z-order always visits its four quadrants in the same fixed low-low, low-high, high-low, high-high order regardless of context, which is exactly what produces its "Z" shape and exactly what causes the diagonal jump from the end of one quadrant to the start of the next: the curve's own mid-level endpoints aren't spatially adjacent. A Hilbert curve's rotation is chosen specifically so that wherever one quadrant's sub-curve ends, the next quadrant's sub-curve begins right next to it.
Checked directly, not just asserted: walking every one of the 256 cells of a 16×16 grid in curve order and measuring the Manhattan distance between each consecutive pair, the Hilbert curve makes 0 non-unit jumps out of 255 transitions (every single step moves to an orthogonally adjacent cell — max jump distance 1). The same walk over Z-order's Morton order makes 127 non-unit jumps out of 255, with one jump spanning a Manhattan distance of 16 — the full width of the grid, the exact "diagonal jump between quadrants" the intro paragraph above describes, measured rather than described.
The classic bit-rotation formulation (Wikipedia's own xy2d/d2xy, restated
here): rot applies the same rotate-and-possibly-reflect step responsible for the locality
property above, one recursion level (bit-pair) at a time.
function rot(n, x, y, rx, ry) {
if (ry === 0) {
if (rx === 1) {
x = n - 1 - x;
y = n - 1 - y;
}
// swap x and y
const t = x; x = y; y = t;
}
return [x, y];
}
// point -> curve index, for an n x n grid (n must be a power of 2 -- see Pitfalls)
function xy2d(n, x, y) {
let rx, ry, d = 0;
for (let s = n >> 1; s > 0; s >>= 1) {
rx = (x & s) > 0 ? 1 : 0;
ry = (y & s) > 0 ? 1 : 0;
d += s * s * ((3 * rx) ^ ry);
[x, y] = rot(n, x, y, rx, ry);
}
return d;
}
// curve index -> point, the exact inverse
function d2xy(n, d) {
let rx, ry, t = d, x = 0, y = 0;
for (let s = 1; s < n; s <<= 1) {
rx = 1 & (t >> 1);
ry = 1 & (t ^ rx);
[x, y] = rot(s, x, y, rx, ry);
x += s * rx;
y += s * ry;
t = Math.floor(t / 4);
}
return [x, y];
}Confirmed bijective over a full 16×16 domain: all 256 cells produce 256 distinct d
values in [0, 255], and d2xy(n, xy2d(n, x, y)) round-trips to the exact
original (x, y) for every one of them — this page's build demo above is driving this exact
code, not a simplified stand-in.
Z-order's corner-to-corner range-query trick is not safe to port to a Hilbert curve — it can
silently miss a real match, not just waste time scanning false candidates. The Z-order Curve page proves (by exhaustive check over a
full 32×32 domain) that its own [zmin, zmax] window always contains every point genuinely
inside the query rectangle. That guarantee comes from a specific property of bit-interleaving — it does
not come from "the curve visits every point in some order," which both curves share, and a Hilbert curve
does not have it. On this page's own demo — the identical ten points and query rectangle
x∈[6,11], y∈[6,13] as the Z-order page — the low corner's index is d=40 and
the high corner's is d=156, so the naive scan covers d∈[40,156]. Point
J at (11,6) is genuinely inside that rectangle, but its Hilbert index is
d=209 — outside the scanned window entirely. The scan never visits it and reports it as not
found, a wrong answer, not a slow one. Checked at scale, not just on this one demo: sweeping every
rectangle on a 32×32 domain (corners on a stride-3 grid, 4,356 rectangles total), 3,684 of them
(84.6%) miss at least one genuine match this way, 184,442 points missed in total,
worst single rectangle missing 322 real matches. The fix used in practice is to 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 to keep this page's reference implementation matching its own
demo exactly.
The grid side length must be a power of two — a silent requirement, not a checked one.
xy2d/d2xy above assume n is a power of 2 (the s >>= 1
halving and t / 4 quartering both rely on it); pass anything else and nothing throws. Tried
directly at n=12: only 25 distinct d values come out of 144 cells
(should be 144) — 119 real collisions, e.g. (0,0) and (0,8)
both mapping to d=0. Two genuinely different points become indistinguishable in the sorted
index, the same silent-merge failure mode Z-order
Curve's own bit-width pitfall describes for a different cause (there, a coordinate exceeding the bit
width; here, a domain size that isn't a power of 2). The fix is the same shape both times: round the
domain up to the next power of 2 explicitly, rather than assuming an implementation-convenient size was
already checked somewhere upstream.
The single-window range query this page's first Pitfall breaks is exactly the use case Z-order Curve is built for — which is why real systems that need range queries on an infrastructure-level sorted index (a database column, a distributed key-value store) overwhelmingly reach for Z-order/geohash instead, despite its worse per-query locality. A Hilbert curve earns its keep in a different role: wherever the curve order itself is the artifact being used, not just a temporary sort key for a one-shot window scan. Hilbert R-trees (Kamel & Faloutsos, 1994) sort points into Hilbert order before bulk-loading an R-tree's leaves, specifically because tighter curve locality produces tighter leaf bounding boxes than the same bulk-load using Z-order — measured directly here, not just cited: grouping 2,000 uniformly scattered points into leaves of 10 gives a total leaf perimeter sum of 56,264 in Hilbert order versus 77,498 in Z-order (27.4% tighter), and 669,440 left ungrouped by either curve (raw insertion order) — the R-tree's own query performance depends directly on how tight its bounding boxes are, so this locality gap is a real downstream win, not a curiosity. The same "order itself is the payload" shape shows up in image processing (traversing a bitmap in Hilbert order keeps cache-line accesses spatially local far more consistently than row-major or Z order), and in visualizations that map a 1D range (an IP address block, a file's byte offset) onto a 2D image specifically because nearby positions in the 1D range should stay visually clustered rather than occasionally jumping across the image.
Encode/decode: O(log n) — xy2d and d2xy both
loop once per bit of the domain's side length, identical to Z-order Curve's per-coordinate interleave loop.
Build: O(n log n) to encode every point and sort. Space:
O(n) — one curve index per point, no pointers, same as Z-order.
Query: not a single well-defined bound the way Z-order Curve's O(log n + scanned) is — this
page's first Pitfall is precisely that the naive single-window version of that bound doesn't hold here at
all (it can return a wrong answer, not just a slow one), and a correct decomposition-based query's cost
depends on how many sub-ranges the rectangle splits into, not built or measured on this page. This site's
guide, Choosing a Spatial Structure, does not yet
cover this entry.