The Hilbert Space Filling Curve

The Hilbert screen saver.

HILBER.SCR is a Windows screen saver which draws successive approximations to the Hilbert curve on your inactive PC.

How to draw the Hilbert Curve

The Hilbert space filling curve is a one dimensional curve which visits every point within a two dimensional space. It may be thought of as the limit of a sequence of curves which are traced through the space. Curve H1 has four vertices at the center of each quarter of the unit square. Curve H2 has 16 vertices each at the centre of a sixteenth of the unit square.

The next member of the family comes from treating each quarter as the whole and repeating the operation. The actual Hilbert Curve is not a member of this family, it is the limit that the sequence approaches.

The basic pattern is a curve which starts near the bottom left corner of a box and terminates near the bottom right corner. It has a kink in it, the kink takes it into the top left and top right of the box.

The next curve in the sequence is a refinement of this, we consider each of the quarters to be a box with the appropriate orientation, so that the curve is entering and leaving from the bottom left and leaving in the bottom right.

procedure hilbert(x0, y0, xis, xjs, yis, yjs, n)
/* x0 and y0 are the coordinates of the bottom left corner */
/* xis & xjs are the i & j components of the unit x vector this frame */
/* similarly yis and yjs */
if (n<= 0) then
   LineTo(x0+(xis+yis)/2, y0+(xjs+yjs)/2);
else
  {hilbert(x0, y0, yis/2, yjs/2, xis/2, xjs/2, n-1)
   hilbert(x0+xis/2, y0+xjs/2 ,xis/2, xjs/2, yis/2, yjs/2, n-1)
   hilbert(x0+xis/2+yis/2, y0+xjs/2+yjs/2, xis/2, xjs/2, yis/2, yjs/2,n-1)
   hilbert(x0+xis/2+yis, y0+xjs/2+yjs, -yis/2,-yjs/2, -xis/2, -xjs/2,n-1)}
end procedure;

/* Sample call */
hilbert(0, 0, 300, 0, 0, 300, 4);

Visual Basic version

At each recursive call the new box positioned with the bottom left corner in a possibly different place and the vectors representing right and up are different.

The Hilbert Curve vs the Jordan Curve Theorem

The Jordon curve theorem is a seemingly obvious, but suprisingly difficult to prove result. Roughly, it states that a closed curve which does not cross itself will divide the plane into two regions, the inside and the outside. The Hilbert curve may be closed fairly easily and appears not to cross itself, neverthless it has no inside.

This apparent riddle is solved as although none of the family of curves leading to the Hilbert curve crosses itself the final curve does cross itself all over the place. Consider a point on the boundary between two quarters. It will be included in the section of the curve which fills each of the quarters and is therefore a crossing point.

Treasure Trove reference