Hilbert Weave

About this piece

A space-filling curve is a continuous line that passes through every point of a square. Giuseppe Peano built the first one in 1890 and it caused a small scandal: a line is one-dimensional and a square is two-dimensional, and here was a map from one onto the other. David Hilbert published his own version a year later, in 1891, and it is Hilbert’s that everybody draws — because he described it as a limit of finite stages you can actually see, and each stage is what this plate renders.

Take a square and quarter it. Visit the quarters bottom-left, top-left, top-right, bottom-right. Now do the same inside each quarter, reflecting each sub-curve so that where one quarter ends the next one begins — that is the whole trick, and it is why the line never has to jump. Repeat k times and you have an order-k curve through 4^k cells: 256 at order 4, 1,024 at order 5, 4,096 at order 6. Click the canvas to step through those three orders.

Why anyone cares: locality

The property that made the Hilbert curve useful long after it stopped being a curiosity is that cells that are close along the line stay close on the plate. Formally the map is Hölder-continuous with exponent ½ — travel a fraction d of the way along the line and you have moved at most on the order of √d across the square.

Compare the obvious alternatives. A plain raster scan (left to right, row by row) puts two vertically adjacent pixels a whole row apart in index — at order 6 that is 64 steps for a one-pixel move. The Morton, or Z-order, curve is much better and far cheaper to compute (interleave the bits of x and y, done), but it is discontinuous: at every quadrant boundary it leaps clear across the region it just finished. The Hilbert curve is the one with no leaps at all, which is why it shows up in Hilbert R-trees, in database index keys for geographic data, in cache-friendly image tiling, and in the familiar poster-sized maps of IPv4 address space where each /8 stays in one contiguous blob.

How this plate is built

The curve is computed by bit arithmetic rather than by recursion or a lookup table. For each distance d, the loop reads two bits of d per scale, decides which quadrant those two bits name, and reflects the coordinates accumulated so far into that quadrant’s local frame — O(k) work per cell, no stack. At order 5 the whole path is 1,024 points and rebuilding it costs well under a millisecond, so it is built once per resize and re-stroked as a single Path2D each frame.

A square curve fits a 16:10 plate badly, so several square curves are laid side by side instead of stretched. That is free rather than a fudge: the standard curve enters at cell (0,0) and leaves at cell (n−1,0), both on the bottom row, so one block’s exit and the next block’s entry are already neighbouring cells. On a typical laptop stage that gives two blocks of 32×32 — a 64×32 lattice, 2,048 cells, one continuous line. Every consecutive pair of cells is a single orthogonal step apart; that was checked at orders 2, 3 and 4 against a brute-force count, with no cell visited twice and none missed.

What to look for

Follow the bright head. It never travels diagonally and it never revisits a cell, yet within a few seconds it has been everywhere. Watch it enter a quadrant: it fills that entire region before it leaves, which is the locality property made visible — a long unbroken stretch of the line occupies one compact blob of the plate rather than smearing across it. And look at the seams where two blocks meet: the head steps across in a single move, with no visible discontinuity.

The head ping-pongs rather than looping. A head that wrapped from the last cell back to the first would drag its tail along the one straight line a Hilbert curve does not contain, so it runs to the end and comes back.

Honest limits: this piece is deterministic. A Hilbert curve of a given order is unique, so unlike most of this gallery it draws the same picture on every load — the only variation is the size of the plate and the order you click to. Locality is guaranteed within a block, not across the whole rectangle: two cells sitting near each other on opposite sides of a seam can be a full block apart along the line. And the order is capped by the pixels available — below about 6 CSS pixels a cell the strokes merge into a solid block, so a narrow window silently drops an order rather than showing a smear. Reduced-motion visitors get the complete weave with the head parked partway along it, which loses nothing but the travel, because the curve was never the part that moved.

Curious how the loop and canvas fit together? Read how it works →