Hilbert curve

From Wikipedia, the free encyclopedia

Jump to: navigation, search
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.
Hn is the nth approximation to the limiting curve. The Euclidean length of Hn is 2^n - {1 \over 2^n} , i.e., it grows exponentially with n, while at the same time always being bounded by a square with a finite area.

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

Contents

[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

Lastly, here is an example of how to produce the curve using NumPy in the Python programming language.

from numpy import array,r_
 
def hilbert(N):
    """
    Produce a Hilbert curve.
 
    @param N:
         the length of side, assumed to be a power of 2 ( >= 2)
 
    @returns: 
          x and y, each as an array of integers. Calling plot(x, y)
          will plot the Hilbert curve.
 
    """
    if N==2:
        return  array((0, 0, 1, 1)), array((0, 1, 1, 0))
    else:
        x, y = hilbert(N/2)
        xl = r_[y, x,     N/2+x, N-1-y  ]
        yl = r_[x, N/2+y, N/2+y, N/2-1-x]
        return xl, yl

[edit] See also

Sister project Wikimedia Commons has media related to: Hilbert curve

[edit] References

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

[edit] External links

Retrieved from "http://en.wikipedia.org/wiki/Hilbert_curve"
Personal tools