HILBERT_CURVE
Convert between 1D and 2D coordinates of Hilbert Curve


HILBERT_CURVE is a C library which can convert between 1D and 2D coordinates of the Hilbert curve.

Mathematically, the Hilbert curve H is a continuous curve that passes through every point in the unit square. Naturally, it is not possible to draw, or even to imagine, such a curve. However, the Hilbert curve can be described as the limit of a sequence of simpler curves Hn, where Hn is drawn by dividing the unit square into an NxN array of cells Cn (where N is a power of 2), and connecting the cell centers. The Hilbert curve Hn will pass through each cell exactly once.

Computationally, the Hilbert curve Hn is very useful. It provides a way of traversing a 2D array that tends to preserve locality. It provides an interesting corresponding between points on the unit line segment [0,1], expressed as base 4 decimal fractions, and cells in the sequence of nested squares Cn. For instance, the point whose base four decimal expansion begins 0.312... can be located by going to the 4th cell of H2, then when that cell gets subdivided, going to the second cell, then when that cell gets subdivided, going to the third cell. (Note that, in order for the Hilbert curve to be connected, each time a cell is subdivided, the ordering of the subcells is rotated or flipped in a regular way.)

Licensing:

The computer code and data files made available on this web page are distributed under the GNU LGPL license.

Languages:

HILBERT_CURVE is available in a C version and a C++ version and a FORTRAN90 version.

Related Data and Programs:

MANDELBROT, a C program which generates an ASCII Portable Pixel Map (PPM) image of the Mandelbrot fractal set;

Reference:

  1. Brian Hayes,
    Crinkly curves,
    American Scientist,
    Volume 101, Number 3, May-June 2013, pages 178-183.

Source Code:

Examples and Tests:

List of Routines:

You can go up one level to the C source codes.


Last revised on 23 December 2015.