Hilbert Curve Algorithm

Rust implentation of the Hilbert Curve algoritm. The library moves from point (x, y) to index (z) and index (z) to point (x, y).

As a Consumer of the Library

Install

cargo add hilbert-curve-rust

Detail on Crate.io

How to use?

The Rust Documentation for the Hilbert Curve Rust library is available online. However, here are two examples to get started.

Index to point

Single dimension integer into a two dimensionals coordinate

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

Point to index

Two dimensionals coordinate into a single dimension integer.

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

As a Developer of the Hibert Curve Rust Library

If you want to contribute to the Hibert Curve Rust code base. Here are few informations that might be useful.

Test and Coverage

Coverage

You must install few components before running coverage:

cargo install grcov
rustup component add llvm-tools-preview

Then, you can run:

./coverage.sh

Further explanation in the Mozilla grcov website

Documentation

cargo doc --open

Benchmark

./benchmark.sh

Publishing

cargo login
cargo publish --dry-run
cargo publish

Performance Compared to other Rust Libraries

Comparing on Order 8

The benchmark finds all index of each position (x,y) has an average time to scan all position

Comparing Each Framework on Multiple Orders

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 fast_hilbert. The plot shows the second group next to the best group, but the reality is that fast_hilbert can be 10x faster than the three next contenders.

Performance Learning Experience

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.