Fast Hilbert 2D curve computation using an efficient Lookup Table (LUT) and a more efficient "orientation-stable encoding". The curve is slightly than the original hilbert curve. Every odd iteration is oriented by 90 degrees compared to the original hilbert implementation.
- Orientation-stable encoding (all credits to DoubleHyphen see this PR for more information)
- Convert from discrete 2D space to 1D hilbert space and reverse
- No
orderoriterationinput required - Very fast using an efficient 512 Byte LUT
- No additional dependencies except for rust std lib.
Benchmarking the conversion from full 256x256 discrete 2D space to the 1D hilbert space, shows that fast_hilbert is almost 5 times faster compared to the fastest 2D hilbert transformation libs written in rust. Benchmarked on a Intel i5-6400 CPU @ 2.70 GHz, 4 Cores with 8 GB RAM:
| Library | Time | Description |
|---|---|---|
| fast_hilbert | 0.6 ms | Optimized for fast computation in 2D discrete space using an efficient LUT |
| hilbert_2d | 2.5 ms | Also allows other variants such as Moore and LIU |
| hilbert_curve | 2.0 ms | Implements algorithm described on Wikipedia |
| hilbert | 32.1 ms | Allows computation of higher dimensional Hilbert curves |