Hilbert Curve and Space-Filling Curves — Locality, Indexing & Compression

1. Peano's Paradox: A Line That Fills a Square

In 1890, Italian mathematician Giuseppe Peano constructed something that seemed to violate common sense: a continuous curve — a single, unbroken 1-dimensional path — that passes through every single point of a 2-dimensional square. Before Peano, mathematicians assumed a curve, being fundamentally 1-dimensional, simply could not have "enough points" to cover an entire 2D area. Georg Cantor had already shown that the set of points in a line and the set of points in a square have the exact same cardinality (both are uncountably infinite, in bijection with each other) — but Peano's construction went further, showing that this correspondence could be made continuous: you could trace out the mapping with a pen, never lifting it, and eventually paint every point of the square.

This class of curves is called space-filling curves. They are continuous (no jumps) but famously nowhere differentiable — they have no well-defined tangent direction at any point, because they double back and change direction infinitely often at every scale, similar in spirit to a fractal curve of dimension exactly 2.

David Hilbert refined Peano's construction in 1891 into a cleaner, more visually intuitive recursive rule, and it is Hilbert's version — not Peano's original zig-zag — that is used almost universally in computing today, because of one crucial extra property Hilbert's construction has: locality.

2. Hilbert's Recursive Construction

The Hilbert curve is built recursively. Start with a simple U-shaped path visiting the four quadrants of a square in order. To get the next level of detail, replace each of the four quadrants with a smaller, appropriately rotated and/or reflected copy of the same U-shape, chosen so that the exit point of one sub-curve lines up exactly with the entry point of the next. Repeat this substitution indefinitely, and in the limit the curve visits every point of the square.

The rotations at each recursive level are exactly what makes the Hilbert curve special: they guarantee that wherever one sub-square's path ends, the next sub-square's path picks up right next to it in physical space, not just in the abstract 1D ordering. Applied recursively, this gives a global guarantee: consecutive indices along the entire curve are always physically adjacent cells, at every scale, everywhere on the grid — a property no simpler recursive scheme achieves as well.

// Convert a 1D Hilbert distance d to (x, y) grid coordinates, order n
// (Classic bit-twiddling algorithm; n = number of bits per axis)
function hilbertD2XY(n, d) {
  let [x, y] = [0, 0];
  let t = d;
  for (let s = 1; s < n; s *= 2) {
    const rx = 1 & (t / 2 | 0);
    const ry = 1 & (t ^ rx);
    // Rotate the quadrant so its entry/exit aligns with the parent curve
    if (ry === 0) {
      if (rx === 1) { x = s - 1 - x; y = s - 1 - y; }
      [x, y] = [y, x];  // swap (reflect across diagonal)
    }
    x += s * rx;
    y += s * ry;
    t = Math.floor(t / 4);
  }
  return [x, y];
}

3. Hilbert vs. Morton (Z-Order) Curves

A simpler, faster-to-compute alternative is the Morton order, also called the Z-order curve: interleave the bits of the x and y coordinates directly to produce a single index. It shares the recursive quadrant idea with the Hilbert curve, but skips the rotation step — which makes it dramatically simpler and faster to compute, at a real cost in locality quality.

// Morton (Z-order) encode: interleave bits of x and y
function mortonEncode(x, y) {
  function spread(v) {
    v &= 0x0000ffff;
    v = (v | (v << 8)) & 0x00ff00ff;
    v = (v | (v << 4)) & 0x0f0f0f0f;
    v = (v | (v << 2)) & 0x33333333;
    v = (v | (v << 1)) & 0x55555555;
    return v;
  }
  return spread(x) | (spread(y) << 1);
}

The Z-order curve's weakness is visible in its name: tracing consecutive Morton indices draws a Z-shape, and every time the curve crosses from one quadrant to the next, it can leap clear across the grid — because a Morton code's high bits can flip while low bits reset, producing a large jump in physical space for a change of just 1 in the index. The Hilbert curve's rotations exist specifically to eliminate these jumps, making its locality provably optimal, at roughly 2–4× the computational cost of Morton encoding/decoding.

4. Why It Matters: Databases, Caches, Compression

Spatial database indexing. PostGIS, geographic information systems, and time-series-with-location databases map 2D or 3D coordinates to a single Hilbert index and store rows sorted by that index in a conventional B-tree. Because the Hilbert curve preserves locality so well, a contiguous range of Hilbert indices corresponds closely to a compact geographic region, turning expensive multidimensional range queries into fast 1D B-tree range scans.

CPU and GPU cache locality. Traversing a 2D texture, height field, or grid in raster (row-major) order causes cache-unfriendly access patterns whenever you move to a new row. Storing the same data in Hilbert-curve order instead means that any small local neighborhood of pixels or grid cells is also a small contiguous run of memory addresses — dramatically improving cache hit rates for algorithms like mipmap generation, tiled texture streaming, and image blur/convolution kernels.

Distributed systems and load balancing. Systems that shard data across many machines by geographic or spatial key (delivery routing, geospatial sharding, distributed hash tables with locality requirements) use Hilbert indices so that nearby real-world locations land on the same or nearby shards, minimizing costly cross-shard queries.

Image and video compression. Some image compression and dithering algorithms traverse pixels in Hilbert-curve order rather than raster order specifically because it keeps visually similar (spatially nearby) pixels close together in the resulting 1D data stream, which helps entropy coders and color-quantization algorithms exploit local correlation more effectively than a raster scan would.

Procedural generation and streaming worlds. Open-world games that stream terrain chunks in and out of memory as a player moves often use a Hilbert or Morton ordering for chunk indices, so that spatially nearby chunks are also nearby in the streaming priority queue and on-disk layout — reducing seek costs and improving prefetch accuracy.

Related Articles