Tutorial: Hilbert Curve Coloring

Text and Images © 2001 Kerry Mitchell

Hilbert's Space-filling Curve

German mathematician David Hilbert discovered the curve that bears his name in the early 1900's. It is an example of a "space-filling" curve: it literally covers every point in a square. Like all good fractals, it is generated in iterations. The first few are shown below:
 
Hilbert curve, iteration 0

iteration 0

Hilbert curve, iteration 1

iteration 1

Hilbert curve, iteration 2

iteration 2

The beginning state is on the left. Hilbert designed his curve as connecting the centers of 4 sub-squares, which made up a larger square. To begin, 3 segments connect the 4 centers in an upside-down U shape.

In the middle is iteration 1. Each of the 4 squares has been divided into 4 more squares. The U shape from before is shrunk to half its original size and copied into each sector of 4 squares. In the top left, it's simply copied. In the top right, it's flipped horizontally. In the bottom left, it's rotated 90 degrees clockwise, and in the bottom right, it's rotated 90 degrees counter-clockwise. The 4 pieces are connected with 3 segments, each of which is the same size as the shrunken pieces of the U shape. They are shown in red.

The right panel shows iteration 2. Each of the 16 squares from iteration 1 has been divided into 4 more squares, and the shape from iteration 1 is shrunk and copied. Again, 3 connecting segments (shown in red) are added to complete the curve. The iteration proceeds in this fashion. At each stage, the previous curve is reduced to half its size and copied 4 times. In the upper left, it's just copied, flipped in the upper right, rotated one way in the bottom left, and rotated the other way in the bottom right. At each stage, the curve starts in the lower left corner and ends in the lower right corner, never touching or crossing itself.

My Version

Here, we see the first 3 iterations from the Hilbert curve coloring formula (click on the images to see the uprs):
 
Hilbert curve coloring, iteration 0

iteration 0

Hilbert curve coloring, iteration 1

iteration 1

Hilbert curve coloring, iteration 3

iteration 2

The colored backgrounds have been added to visualize the construction. In each 2x2 block of squares, the curve starts in the lower left (red), moves to the upper left (green), upper right (blue), and exits from the lower right (white). In the cases for iteration 1 and 2, grid lines have been added to break up the 2x2 blocks. You can see how the basic shape is just copied, flipped, and rotated many times. The formula adds the connecting lines, so that the curve always starts in the lower left corner and ends in the lower right.

Center Coordinates

The curve is just a series of lines connecting the centers of each of the squares. There's no reason why the point in the square has to be the exact center, and choosing other points can lead to interesting results. Each "center" point can be specified within its own sub-square. The normal curve has the points right in the center of each sub-square, with coordinates of (0.5, 0.5). The coordinates can vary from 0 to 1 in both dimensions.
 
normal
points moved in
points moved out
iteration 0
iteration 3
center coordinates
lower left/red (0.5, 0.5)
upper left/green (0.5, 0.5)
upper right/blue (0.5, 0.5)
lower right/white (0.5, 0.5)
(0.75, 0.75)
(0.75, 0.25)
(0.25, 0.25)
(0.25, 0.75)
(0.25, 0.25)
(0.25, 0.75)
(0.75, 0.75)
(0.75, 0.25)

Enter/Exit Point

Instead of drawing connecting lines between the last point of one 2x2 block and the first point of the next 2x2 block, the formula draws a line from the last center to the edge of its sub-square, and another line from the edge of the first sub-square to its center. By design the 2 stubs connect, because the point on the edge of the last sub-square always matches up with the point on the edge of the next first sub-square. Exactly where along the sides of the sub-squares is up to you. The default is halfway along the side (enter/exit parameter value of 0.5), but it can be anything from 0 (outside corner) to 1 (boundary between lower left and lower right sub-squares). The figures below illustrate the effect of changing the enter/exit point while leaving all the centers in their default positions of (0.5, 0.5).
 
normal (0.5)
0.25
0.75
iteration 0
iteration 3

4 Corners Point

In Hilbert's original construction, he used an initial square, broken into 4 sub-squares. The 4 corners of the sub-squares all met at the center of the larger square. There's no reason why the 4 sub-regions need to be square. In this formula, they are all rectangles and their shapes are determined by the point where the 4 corners meet. However, in order to make the enter and exit points align properly, the lower left and upper right regions need to be square. So the 4 corners point can vary along a line from the very lower left corner up to the very top right corner of the 2x2 block. The default setting for the 4 corners parameter is 0.5; it can vary from 0 to 1. The figures below illustrate the effect of changing it while leaving all the centers in their default positions of (0.5, 0.5).
 
normal (0.5)
0.25
0.75
iteration 0
iteration 3

Coloring Options

No coloring formula would be complete without a boatload of coloring options. Here, they're available under the "color by" parameter.

The "distance" method colors the pixel by its distance from the curve. See my article, "Using Ultra Fractal as a Drawing Tool," for more information on how that works. Note that this is the only mode in which the curve will be visible, so it's the only choice where the center coordinates and enter/exit point matter.

The "last = lsb" mode builds the color #index out of the sequence of sub-squares visited. As an example, imagine that you roll a single die 4 times, and get the numbers 1, 6, 2, and 3. When the 1 comes up, you start a tally with 1. Then the 6 comes up. Tack the 6 onto the 1 to get 16. (Or, multiply the 1 by 10 and add 6). The 2 makes 162, and the 3 yields 1623. Since there were 4 numbers, divide by 104 (10000) to get 0.1623. This is how the "last = lsb" mode works. Each sub-square is assigned a number 0 - 3, and when it is used, its value gets tacked on to the end of the string. Then, the final number is divided by 4iterations to get the final #index between 0 and 1. Since each subsequent iteration's value is less and less significant, you won't see much difference with this mode with more than 3 or 4 iterations.
 

2 iterations
4 iterations
6 iterations
last = lsb
last = msb

The "last = msb" methods works in a similar fashion, but the number is prepended (added to the front). So for our die example, the #index would wind up being 0.3261. Using this with many iterations can yield an image that quickly decomposes into visual noise.  Click on either of the "6 iterations" images above to see the uprs.

The last 2 options are reflections of how this formula is implemented. Rather than finding the actual locations of all the lines and comparing those to #z, I followed Samuel Monnier's lead. In his formulas, he iterates #z and compares each iterate with the base curves. Consequently, a stack of new z values is obtained, much like with a normal fractal calculation formula. So the last 2 options color by the how far the final iterate is from #z, or by the angle between the final iterate and #z. Click on either image to see the upr.
 

4 iterations
distance from z
angle from z

 

Tutorial: Hilbert's Ghost

Now that we've gotten all that background out of the way, let's use it to create the image I call, "Hilbert's Ghost."  Click on the thumbnail to see a larger version.

Step 1: the formula

Step 2: the coloring Step 3: Progress check The plan (click for upr):

Here's the plan, shown on the left for 0 iterations and in color. We're going to have 9 layers, each with slightly different center coordinates. The bottom layer is shown in red and the top layer in cyan. Each layer has the same entry/exit point, which is why all the lines come together at the bottom in the middle and on the right side in the middle. Each layer will have the 4 corners point be in the middle, which is why the red and cyan lines cross there. Ready?

Step 4: Set the first layer

Step 5: Add a bunch more
layer
lower left
upper left
upper right
lower right
2
0.125/0.125
0.875/0.125
0.875/0.875
0.125/0.875
3
0.25/0.25
0.75/0.25
0.75/0.75
0.25/0.75
4
0.375/0.375
0.625/0.375
0.625/0.625
0.375/0.625
5
0.5/0.5
0.5/0.5
0.5/0.5
0.5/0.5
6
0.625/0.625
0.375/0.625
0.375/0.375
0.625/0.375
7
0.75/0.75
0.25/0.75
0.25/0.25
0.75/0.25
8
0/875/0.875
0.125/0.875
0.125/0.125
0.875/0.125
9
1/1
0/1
0/0
1/0

Back to Tutorials page
Up to my home page