The Hilbert Curve
The Hilbert curve is a space-filling curve that visits every point in a square grid with a size of 2x2, 4x4, 8x8, 16x16, or any other power of two.
It was described by David Hilbert in 1891. I have heard that Niklaus Wirth published a recursive algorithm to produce Hilbert curves in Algorithms + Data Structures = Programs, Second Edition (Prentice Hall, 1976). I am unable to confirm this because the book is now out of print. I developed the algorithm presented here independently; however, if Wirth's book does indeed contain an implementation of the algorithm, I suspect that my approach is quite similar to his.
The Hilbert curve has applications in image processing, especially image compression and dithering. It has advantages in those operations where the coherence between neighboring pixels is important [3]. The Hilbert curve is also a special version of a quadtree; any image-processing function that benefits from the use of quadtrees may also use a Hilbert curve.
Constructing a Hilbert Curve
The basic elements of a Hilbert curve are what I call "cups" (a square with one open side) and "joins" (a vector that joins two cups). The "open" side of a cup can be top, bottom, left, or right. In addition, every cup has two endpoints, and each of these can be the "entry" point or the "exit" point. So, there are eight possible varieties of cups. In practice, a Hilbert curve uses only four types of cups. In a similar vein, a join has a direction: up, down, left, or right.
A first-order Hilbert curve is just a single cup:
It fills a 2x2 space. The second-order Hilbert curve replaces that cup by four (smaller) cups, which are linked together by three joins
The link between a cup and a join has been marked with a fat dot in the figure.
Figure 2 shows how to produce a second-order curve from any of the four possible cups. Read this figure from left to right. For example, to produce a second-order Hilbert curve from an upward pointing ("up") cup (top row of figure), first produce a left cup; attach a vertical join to its lower endpoint; attach the bottom end of the vertical join to the left endpoint of an up cup; attach a horizontal join to the right endpoint of the up cup; attach the right end of the horizontal join to the left endpoint of another up cup; attach a vertical join to the right endpoint of this up cup; and attach the top of this vertical join to the bottom endpoint of a right cup. Using this method, you can produce a Hilbert curve of the next-highest order from any existing Hilbert curve. Simply replace every cup in the first curve with four cups as outline by Figure 2.
A Hilbert Curve Function
Listing 2 presents a function that computes the Hilbert curve. Note that the curve is symmetrical around the vertical axis. If you were drawing Hilbert curves, it would therefore be sufficient to draw half of the Hilbert curve and flip it on its axis of symmetry.
The Hilbert curve is easy to generate. When applied over a digitized photograph or a ray-traced image, it makes better use of the coherence of neighboring pixels than the traditional scan-line based approach.
For those interested in a three-dimensional variant of the Hilbert curve (a curve that fills a cube), see http://math.uwaterloo.ca/~wgilbert/Research/HilbertCurve/HilbertCurve.html.
