The Hilbert Curve, Explained

After reading this you can construct the Hilbert curve by hand at any order, count the cells it visits, and explain why sorting 2D points along it keeps neighbours close.

What a space-filling curve is

Draw a single unbroken line that starts in one corner of a square and never lifts off the page. Now demand that the line eventually passes through every point of the square, not just a lattice of dots but the whole solid region. That sounds impossible for a one-dimensional line. In 1891 David Hilbert built a sequence of curves whose limit does exactly that.

The explorer draws that sequence one order at a time. At order 1 the curve is a simple U shape with three straight joints, visiting the centres of a 2 by 2 grid. At order 2 the square splits into a 4 by 4 grid and the curve visits all 16 cells. At order 6 it threads through 4096 cells. Each order doubles the grid resolution in both directions, so the line gets four times longer and squeezes into cells four times smaller.

The hook is the colouring. Colour the line by how far along it you have travelled, from blue at the start to red at the end. Then look at any small patch of the square. Its colours vary smoothly, because points that sit near each other in the plane also sit near each other along the curve. That property, not the fractal art, is why the Hilbert curve earns its place in databases and mapping.

How the curve is built: four copies and three joints

The construction is recursive. To draw the order-n curve, take four copies of the order n-1 curve, shrink each to half size, place one in each quadrant, and connect them with three short line segments.

The trick is orientation. If you dropped four identical copies in the four quadrants, the ends would not line up and you could not join them into one continuous path. So the two bottom copies are rotated and reflected. The bottom-left copy is reflected across the main diagonal; the bottom-right copy is reflected across the anti-diagonal. The two top copies keep the parent orientation. With those two flips, the exit of one quadrant lands right next to the entrance of the next, and three joints stitch the four pieces into a single line.

Because each step replaces one curve with four half-size copies, the number of cells visited multiplies by 4 each order:

Here n is the order and N(n) is the number of grid cells the curve visits. Order 1 gives 4, order 2 gives 16, order 3 gives 64. The grid side length is 2^n, so order n resolves a 2^n \times 2^n grid.

From distance to coordinates: the d2xy map

The curve defines a one-to-one map between a single number d (distance along the curve, an integer from 0 to 4^n - 1) and a grid cell (x, y). Converting d to (x, y) is called d2xy; the reverse is xy2d. Both run in O(n) steps, one step per order.

The idea: read the base-4 digits of d from the coarsest level down. Each pair of bits picks one of the four quadrants, and moving into the two bottom quadrants triggers a rotate-and-flip of the coordinate frame, exactly the reflections from the construction. The core rotation, applied at each level with side length s, is:

Here r_x and r_y are the two quadrant bits extracted at that level, and the flip means replacing x with s-1-x and y with s-1-y. You do not need to memorise this. The point is that the map is cheap and exact, so a database can turn any (x, y) pair into a single sortable integer and back.

Why locality matters for databases and maps

Storage and search work in one dimension. A B-tree index, a sorted file, a range of map tiles: all of them are lines of records, one after another. Geographic data is two-dimensional. To ask "give me everything inside this rectangle" against a one-dimensional index, you need a way to flatten 2D into 1D that keeps nearby points nearby.

Compare two flattening schemes on the same 4 by 4 grid. Row-major order (scan left to right, then jump to the next row) puts cell (3,0) at position 3 and cell (0,1) at position 4, right next to each other. But those cells are far apart in the plane: opposite ends of the grid vertically. Hilbert order never makes a jump that big. The chart below plots, for every pair of cells that are 1 apart in the index, how far apart they are in the plane.

The practical payoff: a query for a small rectangle touches a small number of contiguous ranges of the index, so the disk reads fewer scattered blocks. This is why systems that linearise coordinates, including some spatial indexes and map-tile addressing schemes, prefer Hilbert order over the simpler Z-order (Morton) curve, whose diagonal jumps are longer.

The dimension paradox

The finished curve is one continuous line, which sounds one-dimensional, yet it fills a solid square, which is two-dimensional. Both are true. The resolution is Hausdorff dimension, a way of measuring how a shape's size scales when you shrink your ruler.

Here N is the number of self-similar pieces and r is the scale factor of each piece. For the Hilbert curve, each step makes N = 4 copies at scale r = 1/2. So D = \log 4 / \log 2 = 2. The line has topological dimension 1 but fractal dimension 2. It is a genuine curve that is also, in the limit, a filled square.

Common mistakes

Confusing the drawn curve with the limit. No finite order fills the square. Each order leaves gaps; the gaps just shrink. Claims about area or dimension 2 are limit statements only.

Assuming perfect locality. The curve keeps most neighbours close, but not all. Two cells that touch in the plane can be far apart on the curve when they straddle a joint between quadrants. In the order-2 example, cells (0,0) and (0,3) touch across the grid's left edge only in a stretched sense, but the honest bad case is any point pair split by a high-level fold. Locality is strong on average, not guaranteed for every pair.

Mixing up axis conventions. The d2xy result depends on whether the origin is top-left or bottom-left and which quadrant you call "first." Flip a convention and your coordinates reflect. Pick one and stay consistent, or the same d will land in the wrong cell.

Expecting the curve to be unique. Hilbert's is one space-filling curve among many. The Peano curve, the Z-order curve, and the Gosper flowsnake all fill regions. They differ in locality and in visual shape. Hilbert wins on locality because it never makes a long jump.

Related tools

If the recursion here interested you, the same replace-and-shrink idea drives the Penrose tiling generator and the shape-building in the Chaos game. To measure a fractal's dimension the empirical way, lay grids over a shape in the Box-counting dimension lab (the log-log slope reproduces the D = \log N / \log(1/r) formula above). For other fractals with exact self-similarity, try the Mandelbrot explorer and the Newton fractal. The recursive doubling that gives 4^n cells is the same counting pattern as the 2^n - 1 moves in the Tower of Hanoi. And for another path that visits every cell once, see the Knight's tour.

Related tools

3D Geometry Board

Points, lines, planes, spheres and polyhedra on an orbiting camera — slice solids with planes, unfold nets, drop the Dandelin spheres into a cone and drag everything.

Bézier Curve Playground

Drag control points and watch De Casteljau’s algorithm construct a Bézier curve step by step.

Central Limit Theorem Demo

Sample from any lopsided distribution and watch the averages pile up into a bell curve.

Conway’s Game of Life

Paint cells and watch Conway’s cellular automaton breed gliders, guns and oscillators.

Dynamic Geometry Board

Construct with points, lines, circles and transformations, then drag anything — the construction stays true, and a checker tells you which relations are theorems.

Fantasy Map Generator

Roll a seed and get a continent: coastlines, mountains, rivers, biomes and named towns, ready for your campaign.