Hilbert curve

The Hilbert curve (also known as the Hilbert space-filling curve) is a continuous fractal space-filling curve first described by the German mathematician David Hilbert in 1891, as a variant of the space-filling Peano curves discovered by Giuseppe Peano in 1890.

Because it is space-filling, its Hausdorff dimension is 2 (precisely, its image is the unit square, whose dimension is 2 in any definition of dimension; its graph is a compact set homeomorphic to the closed unit interval, with Hausdorff dimension 2).

The Hilbert curve is constructed as a limit of piecewise linear curves. The length of the $n$th curve is $\textstyle 2^n -$, i.e., the length grows exponentially with $n$, even though each curve is contained in a square with area $1$.

Images

File:Hilbert curve 1.svg, Hilbert curve, first order
File:Hilbert curve 2.svg, Hilbert curves, first and second orders
File:Hilbert curve 3.svg, Hilbert curves, first to third orders
File:Hilbert curve production rules!.svg, Production rules
File:Hilbert.png, Hilbert curve, construction color-coded
File:Hilbert3d-step3.png, A 3-D Hilbert curve with color showing progression
File:Courbe de Hilbert.jpg, Variant, first three iterations

Applications and mapping algorithms

Both the true Hilbert curve and its discrete approximations are useful because they give a mapping between 1D and 2D space that preserves locality fairly well. This means that two data points which are close to each other in one-dimensional space are also close to each other after folding. The converse cannot always be true.

Because of this locality property, the Hilbert curve is widely used in computer science. For example, the range of IP addresses used by computers can be mapped into a picture using the Hilbert curve. Code to generate the image would map from 2D to 1D to find the color of each pixel, and the Hilbert curve is sometimes used because it keeps nearby IP addresses close to each other in the picture.

In an algorithm called Riemersma dithering, grayscale photograph can be converted to a dithered black-and-white image using thresholding, with the leftover amount from each pixel added to the next pixel along the Hilbert curve. Code to do this would map from 1D to 2D, and the Hilbert curve is sometimes used because it does not create the distracting patterns that would be visible to the eye if the order were simply left to right across each row of pixels. Hilbert curves in higher dimensions are an instance of a generalization of Gray codes, and are sometimes used for similar purposes, for similar reasons. For multidimensional databases, Hilbert order has been proposed to be used instead of Z order because it has better locality-preserving behavior. For example, Hilbert curves have been used to compress and accelerate R-tree indexes (see Hilbert R-tree). They have also been used to help compress data warehouses.

Given the variety of applications, it is useful to have algorithms to map in both directions. In many languages, these are better if implemented with iteration rather than recursion. The following C code performs the mappings in both directions, using iteration and bit operations rather than recursion. It assumes a square divided into ''n'' by ''n'' cells, for ''n'' a power of 2, with integer coordinates, with (0,0) in the lower left corner, (''n'' − 1, ''n'' − 1) in the upper right corner, and a distance ''d'' that starts at 0 in the lower left corner and goes to $n^2-1$ in the lower-right corner. This is different from the animation shown above where the curve starts from upper left corner and terminates at upper right corner.

//convert (x,y) to d
int xy2d (int n, int x, int y)

//convert d to (x,y)
void d2xy(int n, int d, int *x, int *y)

//rotate/flip a quadrant appropriately
void rot(int n, int *x, int *y, int rx, int ry)

These use the C conventions: the & symbol is a bitwise AND, the ^ symbol is a bitwise XOR, += is the addition/assignment operator (x += y is equivalent to x = x + y), and /= is the division/assignment operator. The handling of booleans in C means that in xy2d, the variable ''rx'' is set to 0 or 1 to match bit ''s'' of ''x'', and similarly for ''ry''.

The xy2d function works top down, starting with the most significant bits of ''x'' and ''y'', and building up the most significant bits of ''d'' first. The d2xy function works in the opposite order, starting with the least significant bits of ''d'', and building up ''x'' and ''y'' starting with the least significant bits. Both functions use the rotation function to rotate and flip the (''x'',''y'') coordinate system appropriately.

The two mapping algorithms work in similar ways. The entire square is viewed as composed of 4 regions, arranged 2 by 2. Each region is composed of 4 smaller regions, and so on, for a number of levels. At level ''s'', each region is ''s'' by ''s'' cells. There is a single FOR loop that iterates through levels. On each iteration, an amount is added to ''d'' or to ''x'' and ''y'', determined by which of the 4 regions it is in at the current level. The current region out of the 4 is (''rx'',''ry''), where ''rx'' and ''ry'' are each 0 or 1. So it consumes 2 input bits, (either 2 from ''d'' or 1 each from ''x'' and ''y''), and generates two output bits. It also calls the rotation function so that (''x'',''y'') will be appropriate for the next level, on the next iteration. For xy2d, it starts at the top level of the entire square, and works its way down to the lowest level of individual cells. For d2xy, it starts at the bottom with cells, and works up to include the entire square.

It is possible to implement Hilbert curves efficiently even when the data space does not form a square. Moreover, there are several possible generalizations of Hilbert curves to higher dimensions.

Representation as Lindenmayer system

The Hilbert Curve can be expressed by a rewrite system (L-system).

:Alphabet : A, B
:Constants : F + −
:Axiom : A
:Production rules:
:: A → +BF−AFA−FB+
:: B → −AF+BFB+FA−

Here, "F" means "draw forward", "+" means "turn left 90°", "-" means "turn right 90°" (see turtle graphics), and "A" and "B" are ignored during drawing.

Other implementations

Graphics Gems IIVoorhies, Douglas: Space-Filling Curves and a Measure of Coherence, pp. 26–30, Graphics Gems II. discusses Hilbert curve coherency, and provides implementation.

The Hilbert Curve is commonly used among rendering images or videos. Common programs such as Blender and Cinema 4D use the Hilbert Curve to trace the objects, and render the scene.

See also

* Hilbert curve scheduling
* Hilbert R-tree
* Locality of reference
* Locality-sensitive hashing
* Moore curve
* Murray polygon
* Sierpiński curve
* List of fractals by Hausdorff dimension

Notes

Further reading

*
*

External links

Dynamic Hilbert curve with JSXGraph



XKCD cartoon using the locality properties of the Hilbert curve to create a "map of the internet"

Gcode generator for Hilbert curve

Iterative algorithm for drawing Hilbert curve in JavaScript

Algorithm 781: generating Hilbert's space-filling curve by recursion (ACM Digital Library)

{{Fractals

Fractal curves
Articles containing video clips
Articles with example C code