Hilbert Curves

By Michael Doornbos

- 5 minutes read - 872 words

Can a line fill a square? Not just outline it, but actually visit every single point inside?

It sounds impossible. A line is one-dimensional; a square is two-dimensional. But in 1891, mathematician David Hilbert proved it could be done—and the result is one of the most beautiful fractals in mathematics.

A Curve That Fills Space

Hilbert’s curve was a response to Giuseppe Peano’s discovery a year earlier. Both curves challenged the very notion of what a “curve” could be—mathematicians at the time called them “monster curves” because they defied intuition.

The trick is iteration. At each step, the curve becomes more intricate, visiting more points in the square. Given infinite iterations, it would touch every single point. The curve never crosses itself, yet somehow manages to fill all of two-dimensional space.

What makes the Hilbert curve special is locality. Points that are close together on the curve tend to be close together in space. This elegant property emerges naturally from the recursive construction.

Building the Curve

The Hilbert curve is built from a simple shape: a U-shaped cup. At level 1, you draw a basic cup. At each subsequent level, you replace each cup with four smaller cups, rotated and connected appropriately.

Think of it as recursive origami. Each fold creates more detail, and the pattern becomes increasingly complex while following the same fundamental rules.

The key insight is that there are four orientations for the cup (opening up, down, left, or right), and the algorithm carefully chooses which orientation to use at each recursive step to ensure the curve remains continuous.

Let’s draw some Hilbert curves on the Commodore 64. The recursive nature of Logo makes it perfect for this task.

TO HILBERT :LEVEL :ANGLE :STEP
  IF :LEVEL = 0 [STOP]
  RT :ANGLE
  HILBERT :LEVEL - 1 (- :ANGLE) :STEP
  FD :STEP
  LT :ANGLE
  HILBERT :LEVEL - 1 :ANGLE :STEP
  FD :STEP
  HILBERT :LEVEL - 1 :ANGLE :STEP
  LT :ANGLE
  FD :STEP
  HILBERT :LEVEL - 1 (- :ANGLE) :STEP
  RT :ANGLE
END

TO SETUP :LEVEL
  CLEARSCREEN
  PENUP
  SETPOS [-100 100]
  PENDOWN
END

TO DRAWHILBERT :LEVEL
  SETUP :LEVEL
  HILBERT :LEVEL 90 200 / (POWER 2 :LEVEL)
END

Here’s how this code works:

  1. The recursive structure: The HILBERT procedure calls itself four times at each level, with three FD :STEP commands between them to connect the four sub-curves.

  2. Angle flipping: Notice how the first and fourth recursive calls use (- :ANGLE) while the second and third use :ANGLE. This alternation creates the characteristic rotations of the Hilbert curve—each sub-curve is oriented correctly to connect with its neighbors.

  3. The turn pattern: RT :ANGLE at the start and end, with LT :ANGLE between the sub-curves. Combined with the angle negation in the recursive calls, this creates the maze-like structure.

  4. Scaling: The step size is calculated as 200 / (POWER 2 :LEVEL). Each level doubles the number of segments, so we halve the step size to keep the curve fitting in our drawing area.

  5. Base case: When :LEVEL reaches 0, we stop recursing. The curve is traced by the FD commands at the deepest level of recursion.

The elegance here is that the entire space-filling structure emerges from just these simple rules applied recursively.

Here’s the same algorithm adapted for Berkeley Logo:

to hilbert :level :angle :step
  if :level = 0 [stop]
  right :angle
  hilbert :level - 1 (minus :angle) :step
  forward :step
  left :angle
  hilbert :level - 1 :angle :step
  forward :step
  hilbert :level - 1 :angle :step
  left :angle
  forward :step
  hilbert :level - 1 (minus :angle) :step
  right :angle
end

to setup
  clearscreen
  penup
  setxy -200 200
  pendown
end

to draw_hilbert :level
  setup
  hilbert :level 90 400 / (power 2 :level)
end

; Example usage:
draw_hilbert 6

Berkeley Logo handles deeper recursion well, so you can push this to level 6 or 7 and watch the curve fill the screen with increasingly fine detail.

Python Turtle

And here’s a Python version using the turtle module:

import turtle

def hilbert(t, level, angle, step):
    if level == 0:
        return

    t.right(angle)
    hilbert(t, level - 1, -angle, step)

    t.forward(step)
    t.left(angle)
    hilbert(t, level - 1, angle, step)

    t.forward(step)
    hilbert(t, level - 1, angle, step)

    t.left(angle)
    t.forward(step)
    hilbert(t, level - 1, -angle, step)
    t.right(angle)

# Set up
screen = turtle.Screen()
t = turtle.Turtle()
t.speed(0)
t.penup()
t.goto(-200, 200)
t.pendown()

# Set depth of recursion
level = 5
step = 400 / (2 ** level)

# Draw
hilbert(t, level, 90, step)

# Finish
screen.exitonclick()

Set level to 5 or 6 for a nicely detailed curve. Higher levels work but take longer to draw.

Extra Credit

Hilbert curves demonstrate how simple recursive rules can create structures that fill space in surprisingly efficient ways. A handful of lines of Logo code produces something that mathematicians once thought impossible.

The Hilbert curve is just one of many space-filling curves. Can you modify the code to draw a Peano curve, which Hilbert was responding to?

What happens if you change the angle from 90 degrees to something else? Does the curve still fill space, or does it collapse into something else entirely?

Try drawing two Hilbert curves of different levels on top of each other. What do you notice about how the smaller one fits inside the larger?

Happy coding!