# 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