 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. Image File history File links Hilbert-Curve-1. ...
Image File history File links Hilbert-Curve-1. ...
Image File history File links Hilbert-Curve-2. ...
Image File history File links Hilbert-Curve-2. ...
Image File history File links Hilbert-Curve-3. ...
Image File history File links Hilbert-Curve-3. ...
Geometrical or geometric continuity, was a concept of geometry primarily applied to the conic sections and related shapes by mathematicians such as Leibniz, Kepler, and Poncelet. ...
The boundary of the Mandelbrot set is a famous example of a fractal. ...
Space-filling curves or Peano curves are curves, first described by Giuseppe Peano, whose ranges contain the entire 2-dimensional unit square (or the 3-dimensional unit cube). ...
In mathematics, the concept of a curve tries to capture the intuitive idea of a geometrical one-dimensional and continuous object. ...
David Hilbert (January 23, 1862, Wehlau, East Prussia – February 14, 1943, Göttingen, Germany) was a German mathematician, recognized as one of the most influential mathematicians of the 19th and early 20th centuries. ...
1891 (MDCCCXCI) was a common year starting on Thursday (see link for calendar). ...
Because it is space-filling, its Hausdorff dimension (in the limit  ) is 2.
The Euclidean length of Hn is  , i.e. it grows exponentially with n.
In mathematics, the Hausdorff dimension is an extended non-negative real number (that is a number in the closed infinite interval [0, ∞]) associated to any metric space . ...
In mathematics, the Euclidean distance or Euclidean metric is the ordinary distance between the two points that one would measure with a ruler, which can be proven by repeated application of the Pythagorean theorem. ...
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] This article needs to be cleaned up to conform to a higher standard of quality. ...
Representation as Lindenmayer System The Hilbert Curve can be expressed by a rewrite system (Lindenmayer System). Rewriting in mathematics, computer science and logic covers a wide range of methods of transforming strings, written in some fixed alphabet, that are not deterministic but are governed by explicit rules. ...
An L-system or Lindenmayer system is a formal grammar (a set of rules and symbols) most famously used to model the growth processes of plant development, though able to model the morphology of a variety of organisms. ...
- 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). The Logo programming language is an adaptation by Wally Feurzeig and Seymour Papert of the Lisp programming language that is easier to read. ...
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. To execute, download Tuga Turtle[1], extract out tugaturtle.jar and execute java -jar tugaturtle.jar (double-clicking on tugaturtle.jar might work too), 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. JRuby is a pure Java implementation of the Ruby interpreter, being developed by the JRuby team. ...
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.
See also |
Feeds |
Contact