hilbert_curve


hilbert_curve, a Python code 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 information on this web page is distributed under the MIT license.

Languages:

hilbert_curve is available in a C version and a C++ version and a Fortran90 version and a MATLAB version and an Octave version and a Python version.

Related Data and Programs:

python_plots, a Python code which uses plotting to illustrate a mathematical structure, such as an iterative map, a fractal, a curve or surface.

Reference:

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

Source Code:


Last revised on 03 January 2016.