Segments
Length
Fractal dimension
Position

More information about space-filling curves

Space-filling curve explorer

A line has length but no area, and a square has area. Yet a line can be bent so that it passes through every part of a square. Start with a few cells and one bent line through them; cut every cell into smaller cells and bend the line through all of those; repeat. Watch a pen draw Hilbert's curve, Peano's curve and their relatives level by level, then put the pen anywhere on the curve to see which point of the line lands in which cell of the square. A space-filling curve is one line that visits every cell of a grid; each level cuts every cell into smaller cells and bends the line through all of them. Press Play to watch the pen draw each level from start to end, or Step to draw the next level. Choose Hilbert's, Moore's or Peano's curve, the Z-order, Gosper's flowsnake or Sierpiński's arrowhead. Click or drag on the picture, on the coloured line under it or on the Pen slider to move the pen along the curve: the Position tile gives the number of the step and the cell it is in. The colours run along the line, so cells with nearby colours are nearby steps.

How it works

  1. Press Play to watch the pen draw each level from start to end, or Step to draw the next level; drag Level to jump to any level.
  2. Choose the Hilbert, Moore or Peano curve, the Z-order, the Gosper curve or the Sierpiński arrowhead.
  3. Click or drag on the picture, on the coloured line under it or on the Pen slider to move the pen along the curve.
  4. Read the number of segments, the length, the fractal dimension and the pen's position in the tiles.

A line that visits every cell

Hilbert's curve of level n runs through a grid of 2ⁿ by 2ⁿ cells, visiting each cell once and always stepping to a neighbouring cell. Level 1 is a single bend through 4 cells. Each next level replaces every cell by 4 smaller cells and every step by a small copy of the bend, turned so that the ends join up. The line through 4ⁿ cells has 4ⁿ − 1 steps and a length of 2ⁿ − 2⁻ⁿ times the side of the square: it doubles, near enough, with every level, while the picture stays the same size. Peano's curve does the same with 9 cells per cell, in S-bends, and Moore's curve joins four Hilbert curves into a closed loop.

From a number line to a square

The coloured line under the picture is the number line from 0 to 1, and the curve is that line folded into the square. Move the pen and the Position tile tells you which step it is on and which cell that is. On Hilbert's curve, steps with nearby numbers are always in nearby cells, which you can see in the colours: each colour stays together in one patch. This is why Hilbert's curve is used to store maps, images and other two-dimensional data in one-dimensional memory. The Z-order is easier to compute, because the cell's coordinates are just the bits of the step number dealt out in turn, but it jumps: nearly half of its steps do not go to a neighbouring cell.

Curves that fill other shapes

Gosper's curve, the flowsnake, replaces each segment by seven on a grid of triangles and fills a shape with a fractal coast, the Gosper island. Its dimension is 2, like that of the square-filling curves: log 7 / log √7. Sierpiński's arrowhead curve replaces each segment by three, each half as long. It never fills an area: it closes in on the Sierpiński triangle, and its dimension is log 3 / log 2 ≈ 1.585, between a line and a surface.

Frequently asked questions

How can a line fill a square?

No single level does: every level is an ordinary line with a length and no area. But the levels settle down. The point a given share of the way along the line moves less and less from level to level, and the limit of all levels is a continuous curve that passes through every point of the square. Giuseppe Peano proved in 1890 that such a curve exists, to the surprise of the mathematicians of his time.

Does the curve visit every point exactly once?

Each level visits every cell of its grid exactly once. The limit curve, though, must pass through some points of the square more than once: in 1879 Eugen Netto proved that a line cannot be mapped onto a square continuously and one-to-one at the same time. Hilbert's curve passes through some points two, three or four times.

What is the difference between the Hilbert curve and the Z-order?

Both put the cells of a grid in one long row. Hilbert's curve always steps to a neighbouring cell, so cells that are close in the row are close in the grid. The Z-order is quicker to compute, by interleaving the bits of the two coordinates, but nearly half of its steps jump, some of them across the whole square. The Length tile counts the jumps.

What are space-filling curves used for?

For putting two-dimensional data in a one-dimensional order that keeps neighbours together. Databases and map services index places along a Hilbert curve or in Z-order, image programs walk the pixels along a Hilbert curve to spread out rounding errors, and maps of the internet's address space use it to keep related addresses side by side.

Why does the Sierpiński arrowhead not fill the square?

Because it cuts each segment into only three pieces of half the length; to fill an area it would need four. The curve closes in on the Sierpiński triangle, a shape with no area and a dimension of log 3 / log 2 ≈ 1.585.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Go to Editor