Hilbert-Index

D-dimensional Hilbert curve for Rust.

Requirements

This crate requires Rust 1.51 or later, due to const-generics. Const-generics enables us to use [usize; D] instead of Vec<usize>.

Features

This crate gives conversion between usize (Hilbert indices) and [usize; D] (grid points), based on the D-dimensional Hilbert curve. A Hilbert curve fills all grid points in a D-dimensional cube, and can be used for D-dimensional data structures, such as Hilbert R-tree.

A D-dimensional Hilbert curve with level (order) l is a map from indices 0..2.pow(D*l) to grid points [usize; D], whose component x satisfy 0 <= x < 2.pow(l). Adjacent indices give adjacent grid points. Input outside the range is not supported and may cause unexpected results.

The implemented algorithm is based on Butz's algorithm in Chris Hamilton's report, "Compact Hilbert Indices". See also Compact Hilbert indices: Space-filling curves for domains with unequal side lengths.

Usage

This crate provides 2 traits, FromHilbertIndex and ToHilbertIndex. Additionally, indices function provides an iterator that generates all Hilbert indices.

Convert a index to a grid point.

use hilbert_index::FromHilbertIndex;
const D: usize = 3;

let level = 2;
for hindex in hilbert_index::indices::<D>(level) {
    let position: [usize; D] = hindex.from_hilbert_index(level);
    println!("p[{:02}] = {:?}", hindex, position);
}

You can also use from_hindex instead of from_hilbert_index.

Convert a grid point to a Hilbert index.

use hilbert_index::ToHilbertIndex;

let level = 1;
assert_eq!( 0, [ 0, 0, 0 ].to_hilbert_index(level));
assert_eq!( 1, [ 0, 1, 0 ].to_hilbert_index(level));
assert_eq!( 2, [ 0, 1, 1 ].to_hilbert_index(level));
assert_eq!( 3, [ 0, 0, 1 ].to_hilbert_index(level));
assert_eq!( 4, [ 1, 0, 1 ].to_hilbert_index(level));
assert_eq!( 5, [ 1, 1, 1 ].to_hilbert_index(level));
assert_eq!( 6, [ 1, 1, 0 ].to_hilbert_index(level));
assert_eq!( 7, [ 1, 0, 0 ].to_hilbert_index(level));

You can also use to_hindex instead of to_hilbert_index.

Similar crates

• hilbert
• hilbert_2d (only for 2D)
• hilbert_curve (only for 2D)
• fast_hilbert (only for 2D)