Hilbert curve

A Hilbert curve (also known as a Hilbert space-filling curve) is a continuous fractal space-filling curve first described by the German mathematician David Hilbert in 1891. [D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. Math. Ann. 38 (1891), 459–460.]

Because it is space-filling, its Hausdorff dimension (in the limit $n\; ightarrow\; infty$) is $2$.
The Euclidean length of $H\_n$ is $2^n\; -\; \{1\; over\; 2^n\}$, i.e., it grows exponentially with $n$.

For multidimensional databases, Hilbert order has been proposed to be used instead of Z order because it has better locality-preserving behavior.

Representation as Lindenmayer system

The Hilbert Curve can be expressed by a rewrite system (L-system).

:Alphabet : L, R:Constants : F, +, −:Axiom : L :Production rules: : L → +RF−LFL−FR+ : R → −LF+RFR+FL−

Here, "F" means "draw forward", "+" means "turn left 90°", and "−" means "turn right 90°" (see turtle graphics).

Computer program

Butz [A.R. Butz: Alternative algorithm for Hilbert’s space filling curve. IEEE Trans. On Computers, 20:424-42, April 1971.] provided an algorithm for calculating the Hilbert curve in multidimensions.

The following Java applet draws a Hilbert curve by means of four methods that recursively call one another:import java.awt.*;import java.applet.*;

public class HilbertCurve extends Applet { private SimpleGraphics sg=null; private int dist0=512, dist=dist0;

public void init( ) { dist0 = 512; resize ( dist0, dist0 ); sg = new SimpleGraphics(getGraphics()); }

public void paint(Graphics g) { int level = 4; dist = dist0; for (int i=level; i>0; i--) dist /= 2; sg.goToXY ( dist/2, dist/2 ); HilbertU(level); // start recursion }

// Make U-shaped curve at this scale: private void HilbertU(int level) { if (level > 0) { HilbertD(level-1); sg.lineRel(0, dist); HilbertU(level-1); sg.lineRel(dist, 0); HilbertU(level-1); sg.lineRel(0, -dist); HilbertC(level-1); } }

// Make D-shaped (really "] " shaped) curve at this scale: private void HilbertD(int level) { if (level > 0) { HilbertU(level-1); sg.lineRel(dist, 0); HilbertD(level-1); sg.lineRel(0, dist); HilbertD(level-1); sg.lineRel(-dist, 0); HilbertA(level-1); } }

// Make C-shaped (really " [" shaped) curve at this scale: private void HilbertC(int level) { if (level > 0) { HilbertA(level-1); sg.lineRel(-dist, 0); HilbertC(level-1); sg.lineRel(0, -dist); HilbertC(level-1); sg.lineRel(dist, 0); HilbertU(level-1); } }

// Make A-shaped (really "⊓" shaped) curve at this scale: private void HilbertA(int level) { if (level > 0) { HilbertC(level-1); sg.lineRel(0, -dist); HilbertA(level-1); sg.lineRel(-dist, 0); HilbertA(level-1); sg.lineRel(0, dist); HilbertD(level-1); }

class SimpleGraphics { private Graphics g = null; private int x = 0, y = 0;

public SimpleGraphics(Graphics g) { this.g = g; } public void goToXY(int x, int y) { this.x = x; this.y = y; }

public void lineRel(int deltaX, int deltaY) { g.drawLine ( x, y, x+deltaX, y+deltaY ); x += deltaX; y += deltaY;

And here is another version that directly implements the representation as a Lindenmayer system:
def f walk 10 end def p turn 90 end def m turn -90 end def l(n) return if n=0 p; r(n-1); f; m; l(n-1); f; l(n-1); m; f; r(n-1); p end def r(n) return if n=0 m; l(n-1); f; p; r(n-1); f; r(n-1); p; f; l(n-1); m end l(6)This is written using the [http://bagotricks.com/projects/tugaturtle/ Tuga Turtle] programming system, which is built on JRuby. It requires Java 5 or higher. To execute, run Tuga Turtle [http://bagotricks.com/projects/tugaturtle/tugaturtle.jnlp] by accepting the self-signed certificate, copy-paste the above code to replace the code in the left-hand pane, and press "Go". You will see a sixth-order Hilbert curve being drawn by the turtle on the screen.

What follows is an example of how to draw the Hilbert curve in the Logo programming language. The code involves a parity variable to indicate whether the curve being drawn is a right-hand Hilbert curve or a left-hand Hilbert curve. The parity is a multiplication of the drawing direction by −1 (negative one). This leads to the realization that the right-hand curve is symmetrical to the left-hand curve.

to hilbert :size :level lhilbert (:size / power 2 (:level - 1)) :level 1end

to lhilbert :size :level :parity if :level = 0 [stop] right 90 * :parity lhilbert :size (:level - 1) (:parity * -1) forward :size right -90 * :parity lhilbert :size (:level - 1) :parity forward :size lhilbert :size (:level - 1) :parity right -90 * :parity forward :size lhilbert :size (:level - 1) (:parity * -1) right 90 * :parityend

An example of invoking the curve is:hilbert 200 5

References

See also

* [http://tog.acm.org/GraphicsGems/gemsii/Hilbert.c Hilbert Curve generation code from Graphics Gems 2]
* Sierpiński curve
* z-order (curve)
* Moore curve
* List of fractals by Hausdorff dimension