NAME

hilbert_i2c, hilbert_c2i - Compute points on a Hilbert curve.

SYNOPSIS

void hilbert_i2c( dim, bits, idx, coords )
int dim, bits;
long int idx;
int coords[];

void hilbert_c2i( dim, bits, coords, idx )
int dim, bits;
int coords[];
long int *idx;

DESCRIPTION

These procedures map the real line onto a Hilbert curve and vice versa. (A Hilbert curve is a space filling curve similar to the Peano curve, except it is not closed.) The procedure hilbert_i2c returns the coordinates of a point on the Hilbert curve, given an index value representing its sequential position on the curve. The procedure hilbert_c2i reverses the process. The arguments are:

dim: The dimensionality of the Hilbert curve. For the usual planar curve case, this would be 2.
bits: The resolution to which the Hilbert curve will be computed. The space is quantized to 2^bits values on each axis, so there are 2^(3*bits) points on the curve. The product of dim*bits should be less than or equal to the number of bits in a long integer (typically 32), and bits should be less than or equal to the number of bits in an integer.
idx: The sequential position of the point along the curve (starting from 0). This is a 3*bits bit integer.
coords: The spatial coordinates of the point on the curve. The array should hold dim values. Each is a bits bit integer.

REFERENCE

A. R. Butz, "Alternative algorithm for Hilbert's space-filling curve," IEEE Trans. Comput., vol C-20, pp. 424-426, Apr. 1971.

AUTHOR

Spencer W. Thomas