Hilbert curve

From Wikipedia, the free encyclopedia

First 8 steps toward building the Hilbert curve

Hilbert curve, first order

Hilbert curves, first and second orders

Hilbert curves, first to third orders

Hilbert curve in three dimensions

3-D Hilbert curve with color showing progression

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.^[1]

Because it is space-filling, its Hausdorff dimension (in the limit $n \rightarrow \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.

1 Representation as Lindenmayer system
2 Computer program
3 References
4 See also

[edit] 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).

[edit] Computer program

Butz^[2] 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 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.

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 1
end
 
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 * :parity
end

An example of invoking the curve is: hilbert 200 5

[edit] References

^ D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. Math. Ann. 38 (1891), 459–460.
^ A.R. Butz: Alternative algorithm for Hilbert’s space filling curve. IEEE Trans. On Computers, 20:424-42, April 1971.