[−][src]Module hilbert::transform::fast_hilbert

Conversions from N-dimensional points (called axes, following Skilling's usage) to Hilbert curve indices and back again.

  • Converting from an N-dimensional point to a 1-Dimensional Hilbert Index will be called the Hilbert Transform.
  • Converting from the Hilbert Index back to the N-Dimensional point will be called the Inverse Hilbert Transform.

The intermediate form of the Hilbert index is an array of transposed bits.

Example: 5 bits for each of n=3 coordinates.

15-bit Hilbert integer (where A is the high-order bit and O is the low-order bit) called the transposed form:

A B C D E F G H I J K L M N O

ⓘThis example is not tested
 
 //                                           ↑
 //   X[0] = A D G J M                    X[2]|  7
 //   X[1] = B E H K N        «–––––––»       | /X[1]
 //   X[2] = C F I L O                   axes |/
 //          high low                         0––––––––→ X[0]

NOTE: This algorithm is derived from work done by John Skilling and published in "Programming the Hilbert curve". (c) 2004 American Institute of Physics.

NOTE: These are the most important methods:

  1. pub fn hilbert_axes(hilbert_index : &BigUint, bits : usize, dimensions : usize) -> Vec Converts Hilbert Index to N-Space.

  2. pub fn hilbert_index(hilbert_axes : &u32, bits usize, interleaver_option : Option<&Interleaver>) -> BigUint Converts N-Space to Hilbert Index.

NOTE: There are four transformations in all:

  1. N-dimensional coordinates(&u32) to transposed form (Vec)
  2. Transposed form to Hilbert index (BigUint)
  3. Hilbert index to Transposed form
  4. Transposed form to N-dimensional coordinates

NOTE: The confusing lamination, delamination, transposed form and the like are abstracted out into a more convenient API via the point and point_list modules. Use the Point struct for simplicity.

Functions

hilbert_axes

Convert a Hilbert index (the distance from the origin along the Hilbert curve represented as a BigUint) into normal N-space coordinates.

hilbert_index

Given the axes (coordinates) of a point in N-Dimensional space, find the 1-dimensional distance to that point along the Hilbert curve as a BigUint.

hilbert_index_transposed

Given the axes (coordinates) of a point in N-Dimensional space, find the distance to that point along the Hilbert curve. That distance will be transposed; broken into pieces and distributed into an array. This performs the most important half of the **forward Hilbert Transform**.

hilbert_inverse_transform

Convert the Hilbert index (in its transposed form) into an N-dimensional point expressed as a vector of unsigned coordinate values.

interleave_be

Interleave the bits of an unsigned vector and generate a byte array in big-endian order, acceptable for the BigUint constructor (BigUint::from_bytes_be).

transpose

Convert a Hilbert distance (index) stored in a BigUint into a transposed matrix, where the bits are distributed among many integers in an array.

uninterleave

Spread the bits of the BigUint among coordinates for the given number of dimensions in a round-robin fashion, delaminating the big integer.

unpack_big_integer

Convert a BigUint into an array of bits (from low-order bit to high-order bit) within a framework that expects a certain number of bits.

untranspose

Convert a transposed Hilbert index back into a Big Integer (BigUint) index.