HILBERT CURVE

A 'Hilbert curve' is a continuous fractal space-filling curve first described by the German mathematician David Hilbert in 1891 ^[1].
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 (curve), because it has a better locality preserving behaviour. Database algorithms with the Hilbert order are found in ^[2] and ^[3]

Contents

Representation as Lindenmayer System

Computer program

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

References

See also

Representation as Lindenmayer System

The Hilbert Curve can be expressed by a rewrite system (Lindenmayer 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 ^[4] 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 each other:


import java.awt.
★ ;
import java.applet.
★ ;
public class HilbertCurve extends Applet {
private SimpleGraphics sg=null;
private int dist0=512, dist=dist0;
public void init() {
sg = new SimpleGraphics(getGraphics());
dist0 = 512;
resize ( dist0, dist0 );
}
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 );
HilbertA(level); // start recursion
}
private void HilbertA (int level) {
if (level > 0) {
HilbertB(level-1); sg.lineRel(0,dist);
HilbertA(level-1); sg.lineRel(dist,0);
HilbertA(level-1); sg.lineRel(0,-dist);
HilbertC(level-1);
}
}
private void HilbertB (int level) {
if (level > 0) {
HilbertA(level-1); sg.lineRel(dist,0);
HilbertB(level-1); sg.lineRel(0,dist);
HilbertB(level-1); sg.lineRel(-dist,0);
HilbertD(level-1);
}
}
private void HilbertC (int level) {
if (level > 0) {
HilbertD(level-1); sg.lineRel(-dist,0);
HilbertC(level-1); sg.lineRel(0,-dist);
HilbertC(level-1); sg.lineRel(dist,0);
HilbertA(level-1);
}
}
private void HilbertD (int level) {
if (level > 0) {
HilbertC(level-1); sg.lineRel(0,-dist);
HilbertD(level-1); sg.lineRel(-dist,0);
HilbertD(level-1); sg.lineRel(0,dist);
HilbertB(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 Tuga Turtle programming system which is built on JRuby. It requires Java 5 or higher. To execute, run Tuga Turtle[1] 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.

References

1. D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. Math. Ann. 38 (1891), 459–460.
2. J. Lawder, P. King: querying multidimensional data indexed using the Hilbert space filling curve. SIGMOD Record, 30(1); 19-24, 2001.
3. H. Tropf: US patent application 2004/0177065, an improved description of the European patent EP 03003692.5; it includes also an algorithm for calculating Hilbert values in n dimensions.
4. A.R. Butz: Alternative algorithm for Hilbert’s space filling curve. IEEE Trans. On Computers, 20:424-42, April 1971.

See also

★ Sierpiński curve

★ z-order (curve)

★ List of fractals by Hausdorff dimension