Alright, promise time. Last week we spent the whole episode dividing space - scattering seeds and letting each one claim the territory closest to it, carving the plane into those lovely organic Voronoi cells. And right at the end I slipped you a riddle for the road: instead of cutting the plane into separate pieces, what if we tried to thread it? Draw one single unbroken line that folds through the plane so tightly it eventually touches every corner. A curve that fills space. I said it sounds impossible, almost paradoxical. Allez, today we build one, and honestly it's one of the strangest and most satisfying things you can make with a few lines of code.
Let me set the paradox up properly, because it really is a proper head-scratcher. A line has length but no width - it's one-dimensional. A square region is two-dimensional - it has area. So how on earth can a 1D thing fill a 2D thing? For a long time mathematicians were sure it couldn't be done, and then in 1890 Giuseppe Peano showed a curve that does exactly that, and a year later David Hilbert showed an even prettier one. These space-filling curves genuinly broke people's intuition at the time. And the beautiful part for us: they're built by recursion, the same fold-inside-a-fold thinking we've used all series, and they turn out to be secretly useful for images, data, and maps. Let me show you what I figured out.
Here's the core intuition before any code. Take a short squiggle that visits four cells of a 2x2 grid without lifting the pen. Now imagine replacing each of those four cells with a smaller copy of the same squiggle, rotating some of them so the copies join up end to end into one continuous line. Do that again inside each smaller cell, and again, and again. Every level of recursion the line gets finer and visits four times as many cells, and in the limit it passes through every point. That's the whole idea. It's self-similar, exactly like the L-system plants and the fractals we've drawn before - a rule that contains itself.
The most famous version is the Hilbert curve, and it has a magic property we'll obsess over later: points that are close together along the line stay close together on the plane. That "keeps neighbours together" behaviour is what makes it more than a pretty picture. But first, let's just draw the thing.
The cleanest way to draw a Hilbert curve is a little recursive function that carries two direction vectors with it - one for the "across" axis and one for the "down" axis. At the deepest level it just drops a point in the middle of the current cell. Above that, it calls itself four times, once per sub-quadrant, flipping the orientation on the first and last so the four pieces link into one path. It looks dense, but read it as "visit my four quarters in an order that keeps the pen down":
// Hilbert curve by recursion. (x,y) is the corner of the current region.
// (xi,xj) is the "across" vector, (yi,yj) the "down" vector.
// n is how many levels of folding are left.
function hilbert(ctx, x, y, xi, xj, yi, yj, n) {
if (n <= 0) {
// deepest level: draw to the centre of this cell
const cx = x + (xi + yi) / 2;
const cy = y + (xj + yj) / 2;
ctx.lineTo(cx, cy);
} else {
// four sub-quadrants, first and last rotated so the ends join up
hilbert(ctx, x, y, yi / 2, yj / 2, xi / 2, xj / 2, n - 1);
hilbert(ctx, x + xi / 2, y + xj / 2, xi / 2, xj / 2, yi / 2, yj / 2, n - 1);
hilbert(ctx, x + xi / 2 + yi / 2, y + xj / 2 + yj / 2, xi / 2, xj / 2, yi / 2, yj / 2, n - 1);
hilbert(ctx, x + xi / 2 + yi, y + xj / 2 + yj, -yi / 2, -yj / 2, -xi / 2, -xj / 2, n - 1);
}
}
Don't panic at the arithmetic - it's just "here's my top-left corner, here are my two axes, split them in half four ways". The two rotated calls (the first and the fourth) are the secret sauce; without those flips the four little curves wouldn't connect and you'd get four disconnected squiggles instead of one continuous line. Now a wrapper to kick it off across the whole canvas:
// draw a Hilbert curve of the given order filling a square of side `size`.
function drawHilbert(ctx, size, order) {
ctx.beginPath();
ctx.moveTo(size / 2 / (2 ** order), size / 2 / (2 ** order));
hilbert(ctx, 0, 0, size, 0, 0, size, order);
ctx.strokeStyle = "#2ec4b6";
ctx.lineWidth = 1.5;
ctx.stroke();
}
Call drawHilbert(ctx, 512, 5) and watch it appear - a single line that snakes through a 32x32 grid, never crossing itself, filling the square with that unmistakable interlocking-U pattern. Bump the order to 6 or 7 and it gets so fine it starts to look like a solid textured block. That block is one line. I still find that a little bit unreal. Makes sense, right? Each level quadruples the detail, so order 7 is already visiting 16,384 cells with a single unbroken stroke.
The recursive draw is gorgeous, but there's a second way to think about the Hilbert curve that unlocks all its real-world uses. Instead of drawing the whole line, ask a sharper question: "if I walk a distance d along the curve, which cell do I land in?" That's a function from a single number to an (x, y) pair - a way of laying out a 1D sequence onto a 2D grid. It's the classic bit-twiddling routine, and it's worth having in your kit:
// map a 1D distance d along the Hilbert curve to its 2D (x, y) cell.
// n is the side length of the grid (must be a power of two).
function d2xy(n, d) {
let rx, ry, t = d;
let x = 0, y = 0;
for (let s = 1; s < n; s *= 2) {
rx = 1 & Math.floor(t / 2);
ry = 1 & (t ^ rx);
// rotate this quadrant so the curve stays continuous
if (ry === 0) {
if (rx === 1) {
x = s - 1 - x;
y = s - 1 - y;
}
const tmp = x; x = y; y = tmp; // swap x and y
}
x += s * rx;
y += s * ry;
t = Math.floor(t / 4);
}
return { x, y };
}
And because it's a proper one-to-one mapping, it runs backwards too. Give it a cell and it tells you how far along the line that cell sits. That inverse is the one you reach for most in practice - it turns a 2D position into a single sortable number:
// the inverse: map a 2D cell (x, y) back to its 1D distance along the curve.
function xy2d(n, x, y) {
let rx, ry, d = 0;
for (let s = n / 2; s > 0; s = Math.floor(s / 2)) {
rx = (x & s) > 0 ? 1 : 0;
ry = (y & s) > 0 ? 1 : 0;
d += s * s * ((3 * rx) ^ ry);
if (ry === 0) {
if (rx === 1) {
x = s - 1 - x;
y = s - 1 - y;
}
const tmp = x; x = y; y = tmp;
}
}
return d;
}
These two little functions are the whole reason databases and mapping systems care about Hilbert curves. But before I sell you on that, let me draw the curve a completely different way using d2xy, just to prove the two views agree. We walk d from zero to the end, ask where each step lands, and connect the dots:
// draw ANY 1D->2D ordering as a path: walk d upward, look up where
// cell d lives, and connect the centres. swap the mapping in and out here.
function drawOrder(ctx, n, cell, mapFn) {
ctx.beginPath();
for (let d = 0; d < n * n; d++) {
const p = mapFn(n, d);
const px = p.x * cell + cell / 2;
const py = p.y * cell + cell / 2;
if (d === 0) ctx.moveTo(px, py);
else ctx.lineTo(px, py);
}
ctx.stroke();
}
Run drawOrder(ctx, 32, 16, d2xy) and you get the exact same Hilbert curve as the recursive version. Two totally different pieces of code, same beautiful fold. That's the sign you've understood something properly - when two roads lead to the identical picture.
The Hilbert curve isn't the only way to thread a grid. There's a much simpler cousin called the Z-order curve, or Morton order, and it's so easy to compute that hardware and databases love it. The idea: take the binary digits of x and the binary digits of y, and just interleave them into one number. Bit of y, bit of x, bit of y, bit of x, all the way up. That's it. No rotations, no recursion, just shuffling bits together:
// Morton (Z-order) code: interleave the bits of x and y into one number.
// this is the OTHER famous space-filling order, and it's dead simple.
function morton(x, y) {
let d = 0;
for (let i = 0; i < 16; i++) {
d |= ((x >> i) & 1) << (2 * i); // x's bits go to even positions
d |= ((y >> i) & 1) << (2 * i + 1); // y's bits go to odd positions
}
return d >>> 0; // force unsigned
}
// decode a Morton code back into (x, y) by pulling the bits apart again.
function mortonDecode(d) {
let x = 0, y = 0;
for (let i = 0; i < 16; i++) {
x |= ((d >> (2 * i)) & 1) << i;
y |= ((d >> (2 * i + 1)) & 1) << i;
}
return { x, y };
}
Wrap mortonDecode so it fits our drawOrder helper (it wants an (n, d) signature) and draw it next to the Hilbert curve:
// adapter so mortonDecode plugs into drawOrder, which passes (n, d).
function mortonMap(n, d) {
return mortonDecode(d);
}
// drawOrder(ctx, 32, 16, mortonMap); // draws the Z-order path
Do that and you'll immediately see the difference. The Z-order curve traces little "Z" or "N" shapes, and every so often it makes a huge diagonal leap clear across the grid - from the end of one big Z back to the start of the next. It fills the space, sure, but it jumps. The Hilbert curve never jumps; it only ever steps to a touching neighbour. That single distinction is the whole ballgame, so let's measure it.
Here's the property that makes space-filling curves useful rather than merely pretty. We want the curve to preserve locality: things that are near each other along the 1D line should be near each other on the 2D plane, and vice versa. A quick way to measure that is to walk the curve and, at each step, ask "how far did I just jump in 2D?" Small jumps mean good locality:
// locality test: average 2D distance between consecutive steps along the curve.
// a GOOD space-filling curve keeps this tiny - 1D neighbours stay 2D neighbours.
function averageJump(n, mapFn) {
let total = 0;
for (let d = 1; d < n * n; d++) {
const a = mapFn(n, d - 1);
const b = mapFn(n, d);
total += Math.abs(a.x - b.x) + Math.abs(a.y - b.y); // grid (taxicab) distance
}
return total / (n * n - 1);
}
console.log("Hilbert:", averageJump(32, d2xy)); // exactly 1 - always a neighbour
console.log("Morton :", averageJump(32, mortonMap)); // bigger - those diagonal leaps hurt
The Hilbert curve scores exactly 1: every single step moves to an edge-adjacent cell, no exceptions. The Morton curve scores higher because of those big diagonal jumps. Compare that to naive row-by-row scanning (go left to right, then snap back to the start of the next row) and it's even worse - every end-of-row is a full-width leap. This is not academic. When you store 2D data in 1D memory and want nearby pixels to sit near each other in cache, or you're indexing map tiles so a database can fetch a region in one contiguous read, that "average jump" number is literally performance. Hilbert's answer of exactly 1 is why it keeps showing up in the guts of real systems.
I can't resist showing you one more way to make the Hilbert curve, because it ties straight back to the L-system plants we grew earlier in the series. Remember those? A tiny grammar, a couple of rewrite rules, and a turtle that walks the resulting string. The Hilbert curve has a famous two-rule grammar. A and B are abstract "states" that expand into each other, F means draw forward, and + / - mean turn ninety degrees:
// the Hilbert curve as an L-system (remember growing plants from grammar?).
// A and B expand into rotated versions of each other; F draws, +/- turn 90 deg.
const hilbertLSystem = {
axiom: "A",
rules: {
A: "+BF-AFA-FB+",
B: "-AF+BFB+FA-",
},
};
// expand the axiom by applying the rules `iterations` times.
function expand(system, iterations) {
let s = system.axiom;
for (let i = 0; i < iterations; i++) {
let next = "";
for (const ch of s) next += system.rules[ch] || ch; // A/B rewrite, rest passes through
s = next;
}
return s;
}
Then the same turtle interpreter we've used since the L-system episodes walks that string and draws it. A and B produce nothing on the page themselves - they only exist to steer the recursion - so the turtle just ignores them:
// turtle-draw the expanded string: F steps forward, + turns left, - turns right.
function turtle(ctx, str, step, angle) {
let x = 20, y = 20, dir = 0;
ctx.beginPath();
ctx.moveTo(x, y);
for (const ch of str) {
if (ch === "F") {
x += Math.cos(dir) * step;
y += Math.sin(dir) * step;
ctx.lineTo(x, y);
} else if (ch === "+") {
dir -= angle;
} else if (ch === "-") {
dir += angle;
}
}
ctx.stroke();
}
// expand 4 times, walk it with 90-degree turns:
turtle(ctx, expand(hilbertLSystem, 4), 12, Math.PI / 2);
Three completely seperate roads - hand-rolled recursion, bit-twiddling d2xy, and now a grammar plus a turtle - and every one of them draws the identical Hilbert fold. When a shape shows up that many different ways, that's the universe telling you it's a deep one. The trig from our angles episode is quietly doing the turning here too, by the way - Math.cos and Math.sin steering the turtle exactly like they steered our rotations.
So what do we actually do with this beyond gawping at it? My favourite creative use is laying 1D data onto a 2D image while keeping neighbours together. Say you have a long signal - a sound wave, a stream of sensor readings, a gradient, whatever - and you want to splash it across a square. If you fill row by row, values that were next to each other in the signal end up split across a hard seam every time a row wraps. Fill along the Hilbert order instead and consecutive values always land in touching pixels, so smooth data stays smooth on the canvas:
// lay a 1D signal onto a 2D image using the Hilbert order, so nearby
// samples land in nearby pixels - no harsh row-wrap seams.
function paintSignalHilbert(ctx, n, cell, signal) {
for (let d = 0; d < n * n; d++) {
const { x, y } = d2xy(n, d);
const v = signal[d % signal.length] & 255; // clamp to a 0..255 grey
ctx.fillStyle = `rgb(${v}, ${v}, ${v})`;
ctx.fillRect(x * cell, y * cell, cell, cell);
}
}
// a slow gradient signal - watch it stay smooth across the whole square:
const n = 64;
const signal = [];
for (let d = 0; d < n * n; d++) signal.push(Math.floor(128 + 127 * Math.sin(d * 0.01)));
paintSignalHilbert(ctx, n, 8, signal);
Feed that a gentle sine and the square fills with soft, connected bands of light and dark that fold around each other with no visible tears - because the curve carried the smoothness with it. Try the same signal painted row-by-row and you'll see the ugly striping the Hilbert version avoids. This exact trick is how people make those "map a whole hard drive's contents to one image" visualisations, and how some dithering and image-compression schemes order their pixels: walk the Hilbert curve so local detail stays local. You can also colour the curve itself by distance - tint each segment by its d value - and you get a gorgeous rainbow ribbon folding through the plane, which is a lovely #genuary prompt in its own right.
Step back and look at what we pulled off. We took a genuine mathematical paradox - a one-dimensional line filling a two-dimensional area - and built it three different ways: raw recursion folding four rotated copies of itself, a bit-twiddling d2xy that maps any number to a point, and an L-system grammar walked by a turtle. We met its simpler rival the Z-order curve, measured why Hilbert's locality is better (average jump of exactly 1, never a leap), and then cashed that property in for something real - painting 1D data onto 2D without seams. From a fold that shouldn't be possible, all the way to a practical tool. That's the whole arc of this series in one episode, honestly.
So here's your homework, and it's a fun one. Get drawHilbert running and crank the order from 1 up to 7 one step at a time - actually watch the line subdivide, because seeing each level quadruple is where the "ohhh" lands. Then draw the Hilbert and the Z-order side by side with drawOrder and stare at the difference in how they move. And if you're feeling bold, feed paintSignalHilbert a real signal - grab some audio samples or just a noisy sine - and compare it against the same data painted row by row. Feel the seams disappear. That's locality you can see.
And carry this thread with you, because it's about to matter a lot. All this while, we've been threading and dividing a flat, finite square. But a space-filling curve is really a way of traversing a region in an order that keeps neighbours together - and that idea of walking through space intelligently, cell by connected cell, is exactly what you need when you stop decorating a fixed canvas and start generating whole worlds that stretch further than any one screen. How do you lay out an endless landscape so the piece under your feet connects smoothly to the piece just over the hill? That question is where we go next, and today's fold is a big part of the answer. 't Was plezant to bend a line until it filled a square with you - now go make one snake across your screen and colour it like a ribbon :-).
d2xy / xy2d to map a single number to a grid cell and back. Same curve, and the mapping is what real systems actually useSo that's space-filling curves, from an impossible-sounding paradox all the way to a genuinly practical tool for images and data - and every step of it was just one line, folded cleverly enough to be everywhere at once. The big takeaway, one more time: a space-filling curve is a way to walk a whole region while keeping neighbours together, and that "keep neighbours together" superpower is what turns a party trick into engineering. Go fold a line until it fills a square, then colour it and watch the ribbon snake. And hold onto that idea of traversing space smoothly, because next time we stop filling one fixed square and start generating worlds that run right off the edge of the screen. Merci voor het lezen, en tot de volgende keer :-).
Sallukes! Thanks for reading.
X
@femdev