Rust implentation of the Hilbert Curve algoritm. The library moves from point (x, y) to index (z) and index (z) to point (x, y).
sh
cargo add hilbert-curve-rust
Detail on Crate.io
The Rust Documentation for the Hilbert Curve Rust library is available online. However, here are two examples to get started.
Single dimension integer into a two dimensionals coordinate
rust
let hilbert_curve = HilbertCurveAlgorithm::new(1); // Set the Hilbert order here
let point = hilbert_curve.index_to_point(0); // Get the point for index 0
Two dimensionals coordinate into a single dimension integer.
rust
let hilbert_curve = HilbertCurveAlgorithm::new(1);// Set the Hilbert order here
let index = hilbert_curve.point_to_index(CoordinateValue { x: 0, y: 0 }); // Get the index for (0,0) point
If you want to contribute to the Hibert Curve Rust code base. Here are few informations that might be useful.
You must install few components before running coverage:
sh
cargo install grcov
rustup component add llvm-tools-preview
Then, you can run:
sh
./coverage.sh
Further explanation in the Mozilla grcov website
sh
cargo doc --open
sh
./benchmark.sh
sh
cargo login
cargo publish --dry-run
cargo publish
The benchmark finds all index of each position (x,y) has an average time to scan all position
| Library | Mean | | ------------------------------------------------------------------------ | --------: | | fasthilbert | 0.3364 ms | | hilbertcurve | 0.7496 ms | | hilbert-curve-rust | 1.0290 ms | | hilbert_2d | 1.3298 ms | | hilbert | 9.9606 ms |
The test loops all x, y coordinates to find the index. Here are the average of each framework.
The plot shows three clear groups. The worse algorithm is the hilbert, which goes exponentially worse after an order of 10.
A second group that contains this library (hilbert-curve-rust) where performance is more stable but starts to get worse around an order 12.
The last group with one algorithm, the fast_hilbert, is the clear fastest algorithm.
From some perspective, a grid of 1024 by 1024 (~1 million points/pixels) is good with any library. However, if you need to start having a grid of 8192 by 8192 (order 13, with 67 million points/pixels), then it might be better to use the fasthilbert. The plot shows the second group next to the best group, but the reality is that fasthilbert can be 10x faster than the three next contenders.
Reduced the benchmark by about 3 seconds by using reference instead of copying value in functions update_rx_from_point, update_ry_from_point, update_point_value_from_number, move_point and rotate_point.
The plot shows the previous benchmark in red and the change of using reference instead of immutable in blue. By removing the copy of objects and passing a reference, the program needs to create less memory and only change the value in specific memory. The gain was significant.