Hilbert curve
From Wikipedia, the free encyclopedia
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] as a variant of the space-filling curves discovered by Giuseppe Peano in 1890.[2]
Because it is space-filling, its Hausdorff dimension is 2 (precisely, its image is the unit square, whose dimension is of course 2 in any definition of dimension; its graph is a compact set homeomorphic to the closed unit interval, with Hausdorff dimension 2).
Hn is the nth approximation to the limiting curve. The Euclidean length of Hn is 
, 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).
Butz[3] provided an algorithm for calculating the Hilbert curve in multidimensions.
Graphics Gems II[4] discusses Hilbert Curve coherency, and provides implementation.
[edit] Computer implementations of the drawing algorithms
[edit] Logo
make "s 4
to Hilbert :n :t
if :n = 0 [stop]
right :t
Hilbert :n-1 -:t
forward :s
left :t
Hilbert :n-1 :t
forward :s
Hilbert :n-1 :t
left :t
forward :s
Hilbert :n-1 -:t
right :t
end
Hilbert 5 90
[edit] Python
from turtle import left, right, forward size = 4 def hilbert(level, angle): if level == 0: return right(angle) hilbert(level - 1, -angle) forward(size) left(angle) hilbert(level - 1, angle) forward(size) hilbert(level - 1, angle) left(angle) forward(size) hilbert(level - 1, -angle) right(angle) hilbert(5, 90)
[edit] Tuga Turtle implementation
The code below directly implements the representation of the Hilbert curve 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] Java implementation
This is yet another implementation of the drawing code, using a more popular Java programming language. It might be easier to follow for those more familiar with Java/C-like syntax. 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; } }
[edit] Haskell Implementation
import Graphics.Rendering.Diagrams curve = iterate seg [] where seg xs = concat [rot id xs, [(0,1)], xs, [(1,0)], xs, [(0,-1)], rot negate xs] rot f = map $ \(x, y) -> (f y, f x) main = renderAs PNG "out.png" (Width 200) (pad 1 1 $ curved 0.2 . pathFromVectors $ curve !! 4)
 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 |
[edit] See also
 |
Wikimedia Commons has media related to: Hilbert curve |
[edit] Notes
- ^ D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. Math. Ann. 38 (1891), 459–460.
- ^ G.Peano: Sur une courbe, qui remplit toute une aire plane. Mathematische Annalen 36 (1890), 157–160.
- ^ A.R. Butz: Alternative algorithm for Hilbert’s space filling curve. IEEE Trans. On Computers, 20:424-42, April 1971.
- ^ Voorhies, Douglas: Space-Filling Curves and a Measure of Coherence, p. 26-30, Graphics Gems II.
