Hilbert Curve

IntroductionThe web notes by Andrew Cumming of Napier University Edinburgh provide a very good introduction to the Hilbert curve. His pseudo code, slightly modified, is shown in listing 1. Listing 1 (from Andrew Cumming)
To fully understand how Andrews recursive function operates is not easy and in order to do so it is necessary to breakdown his Hilbert procedure so that the role that each "part" plays in the construction of the curve can be more readily understood. We will begin by looking at the inputs of the Hilbert function. Inputs
In addition to the counter (n) that tracks the level from which the function begins to
recursively call itself, there are six other inputs to Andrew's procedure. The first two
define the x and y coordinates
of an input point that will be used in the calculation of a point on the Hilbert curve.
The next 4 values define two vectors. Before we see how they are used we must understand
what is meant by the inputs labelled xi, xj, yi and yj. Hopefully, figure 1 will make them
clearer.

Although these vectors represent the x and y coordinates of P, like any vector, they have their own coordinates. For example, the coordinates of the xvector (in two dimensions) might be [1,0] while the coordinates of the yvector might be [0,0.5]. To prevent the confusion of labelling the coordinates of these vectors as "x" and "y" they are instead labelled "i" and "j". For example, xvector yvector xi = 1.0 yi = 0.0 xj = 0.0 yj = 0.5 We can make use of these vectors to move (ie. translate) a copy of point P. For example, in Andrew's procedure we see this statement. LineTo(x + (xi + yi)/2, y + (xj + yj)/2); Rewritten for point P we have, Px = Px + (xi + yi)/2 = 1.0 + (1.0 + 0)/2 = 1.5 Py = Py + (xj + yj)/2 = 0.5 + (0 + 0.5)/2 = 0.75 The effect of using the i's and j's on point P can be seen in figure 2.
Point P could also have been translated by directly changing its x and y values. However, using the "i" and "j" coordinates (xvector and yvectors) moves the point in a structured and proportional fashion. In the context of their use in Andrew's procedure, the "i" and "j" components provide, what are in effect, additional "handles" to control the placement of points along the Hilbert curve. 
Modifying the InputsLooking at the hilited code shown in listing 2 we see the Hilbert procedure calls itself four times. On each call it passes slightly modified versions of its original input values to itself. 
Listing 2 (pseudo code)

// x y xi xj yi yj n hilbert(0, 0, 1, 0, 0, 1, 1);
Tracking the results of the recursions will show what happens to original x,y
coordinates  shown in above in blue. The i and the j vectors will be ignored.
The four recursive calls will be labelled
A hilbert(...); B hilbert(...); C hilbert(...); D hilbert(...);
Performing the arithmetic on the x and y's for the first level of recursion for
x y A hilbert(0.0 0.0, ...); B hilbert(0.5 0.0, ...); C hilbert(0.5 0.5, ...); D hilbert(0.5 1.0, ...);
The value of x and y can be plotted using the Listing 3 (pseudo code)
Figures 3 to 6 show the development of a Hilbert curve from 1 to 4 iterations. The colored dots correspond to the four recursions ie. A hilbert(...); red dot B hilbert(...); green dot C hilbert(...); blue dot D hilbert(...); purple dot Figure 3 shows the basic building block of the Hilbert curve is a open square formed by three connected lines. A complex pattern (figure 4) is made by the Hilbert procedure recursively converting each line to a smaller version of the original open square. The lines of each of the small squares are then converted to even smaller squares, and so on, and so on. After one iteration we have four smaller separate squares. Because of the way the vertices of each square are drawn the final pattern is formed by a single continuous line. In figure 4 the connections that join the small (separate) open squares are shown as dotted lines. 




Basic Code
Listings 4 and 5 provide code for a RenderMan procedural primitive. One is
written in Python, the other in Tcl. For information about procedural primitives,
or helper apps as they are often called, refer to the tutorial,
Listing 4 (hilbert.py)

Listing 5 (hilbert.tcl)
The inputs (arguments) to the helper apps are,

Listing 6 (hilbert.rib)

Mistakes can be InterestingWhen entering the code for the Python and Tcl scripts I made a couple of mistakes that produced some interesting results. The first error occured in a python script. hilbert(x0, y0, yi/2, yj/2, xi/2, xj/2, n  1) hilbert(x0 + xi/2, y0 + xj/2, xi/2, xj/2, yi/2, xj/2, n  1) hilbert(x0 + xi/2 + yi/2, y0 + xj/2 + yj/2, xi/2, xj/2, yi/2, xj/2, n  1) hilbert(x0 + xi/2 + yi, y0 + xj/2 + yj, yi/2,yj/2,xi/2,xj/2, n  1)
The second error occured a tcl script. hilbert $x0 $y0 $YI $YJ $XI $XJ [expr $n  1] hilbert [expr $x0 + $XI] [expr $y0 + $XJ] $XI $XJ $YI $YJ [expr $n  1] hilbert [expr $x0 + $XI + $YI] [expr $y0 + $XJ + $YJ] $XI $XJ $YI $YJ [expr $n  1] hilbert [expr $x0 + $XI + $YI] [expr $y0 + $XJ + $yj] $YI $YJ $XI $XJ [expr $n  1]

© 2002 Malcolm Kesson. All rights reserved.