Hilbert curve

From Wikipedia, the free encyclopedia

You have new messages (last change).

Hilbert curve, first order

Hilbert curves, first and second order

Hilbert curves, first to third order

A Hilbert curve is a continuous fractal space-filling curve first described by the German mathematician David Hilbert in 1891.

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 (curve), because it has a better locality preserving behaviour. Database algorithms with the Hilbert order are found in ^[1] and ^[2]

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 (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).

[edit] Computer program

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

[edit] References

^ J. Lawder, P. King: querying multidimensional data indexed using the Hilbert space filling curve. SIGMOD Record, 30(1); 19-24, 2001.
^ 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.
^ A.R. Butz: Alternative algorithm for Hilbert’s space filling curve. IEEE Trans. On Computers, 20:424-42, April 1971.