2 unstable releases
0.2.0 | Apr 5, 2021 |
---|---|
0.1.0 | Mar 26, 2021 |
#926 in Math
15KB
127 lines
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)