Hilbert curve 3611120 225413965 2008-07-13T15:39:42Z Qef 72915 Switch some example images to equivalent SVG versions (with thicker lines which show up better in these small versions) [[Image:Hilbert_curve.gif|right|thumb|First 8 steps toward building the Hilbert curve]] [[Image:Hilbert_curve_1.svg|right|thumb|Hilbert curve, first order]] [[Image:Hilbert_curve_2.svg|right|thumb|Hilbert curves, first and second orders]] [[Image:Hilbert_curve_3.svg|right|thumb|Hilbert curves, first to third orders]] [[Image:Hilbert512.gif|right|thumb|Hilbert curve in three dimensions]] [[Image:Hilbert3d-step3.png|right|thumb|3-D Hilbert curve with color showing progression]] A '''Hilbert curve''' (also known as a '''Hilbert space-filling curve''') is a [[Geometric continuity|continuous]] [[fractal]] [[space-filling curve|space-filling]] [[curve]] first described by the German mathematician [[David Hilbert]] in [[1891]].<ref>D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. [[Mathematische Annalen|Math. Ann.]] 38 ([[1891]]), 459&ndash;460.</ref> Because it is space-filling, its [[Hausdorff dimension]] (in the limit <math>n \rightarrow \infty</math>) is <math>2</math>. <br> The [[euclidean distance|Euclidean length]] of <math> H_n </math> is <math> 2^n - {1 \over 2^n} </math>, i.e., it grows exponentially with <math>n</math>. <br="clearall"> For multidimensional databases, Hilbert order has been proposed to be used instead of [[z-order (curve)|Z order]] because it has better locality-preserving behavior. ==Representation as Lindenmayer system== The Hilbert Curve can be expressed by a [[rewriting|rewrite system]] ([[L-system]]). :'''Alphabet''' : L, R :'''Constants''' : F, +, &minus; :'''Axiom''' : L :'''Production rules''': : L &rarr; +RF&minus;LFL&minus;FR+ : R &rarr; &minus;LF+RFR+FL&minus; Here, ''F'' means "draw forward", ''+'' means "turn left 90°", and ''&minus;'' means "turn right 90°" (see [[turtle graphics]]). == Computer program == Butz<ref>A.R. Butz: Alternative algorithm for Hilbert’s space filling curve. IEEE Trans. On Computers, 20:424-42, April 1971.</ref> provided an algorithm for calculating the Hilbert curve in multidimensions. The following [[Java (programming language)|Java]] [[applet]] draws a Hilbert curve by means of four methods that [[recursion|recursively]] call one another: <source lang="java"> 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; } } </source> And here is another version that directly implements the representation as a [[Lindenmayer system]]: <code><br> 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) </code> This is written using the [http://bagotricks.com/projects/tugaturtle/ Tuga Turtle] programming system, which is built on [[JRuby]]. It requires Java 5 or higher. To execute, run Tuga Turtle[http://bagotricks.com/projects/tugaturtle/tugaturtle.jnlp] 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 &minus;1 (negative one). This leads to the realization that the right-hand curve is symmetrical to the left-hand curve. <source lang="text"> 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 </source> An example of invoking the curve is: hilbert 200 5 == References == <references/> == See also == {{Commons|Hilbert curve}} * [[Sierpiński curve]] * [[z-order (curve)]] * [[Moore curve]] * [[List of fractals by Hausdorff dimension]] [[Category:Fractal curves]] [[bn:হিলবার্ট কার্ভ]] [[de:Hilbert-Kurve]] [[fr:Courbe de Hilbert]] [[hr:Hilbertova krivulja]] [[lv:Hilberta līkne]] [[ja:ヒルベルト曲線]] [[pl:Krzywa Hilberta]] [[sl:Hilbertova krivulja]] [[zh:希爾伯特曲線]]