# Hilbert-Index
[![crates.io](https://img.shields.io/crates/v/hilbert_index?label=latest)](https://crates.io/crates/hilbert_index)
[![Documentation](https://docs.rs/hilbert_index/badge.svg)](https://docs.rs/hilbert_index/)
D-dimensional Hilbert curve for Rust.
## Requirements
This crate requires Rust 1.51 or later, due to [const-generics](https://rust-lang.github.io/rfcs/2000-const-generics.html).
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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.7490&rep=rep1&type=pdf)".
See also [Compact Hilbert indices: Space-filling curves for domains with unequal side lengths](https://doi.org/10.1016/j.ipl.2007.08.034).
## 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.
```rust
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.
```rust
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](https://crates.io/crates/hilbert)
* [hilbert_2d](https://crates.io/crates/hilbert_2d) (only for 2D)
* [hilbert_curve](https://crates.io/crates/hilbert_curve) (only for 2D)
* [fast_hilbert](https://crates.io/crates/fast_hilbert) (only for 2D)