#hilbert #lookup-tables #mapping #space-filling-curve #algorithm #peano-curves

fast_hilbert

Fast Hilbert 2D curve computation using an efficient Lookup Table (LUT)

4 releases (stable)

2.0.0 Oct 31, 2022
1.0.1 Oct 16, 2022
1.0.0 Mar 31, 2021
0.1.0 Feb 11, 2021

#2 in #hilbert

Download history 15/week @ 2023-11-25 70/week @ 2023-12-02 148/week @ 2023-12-09 6/week @ 2023-12-16 1/week @ 2023-12-23 186/week @ 2024-01-13 103/week @ 2024-01-20 119/week @ 2024-01-27 29/week @ 2024-02-03 81/week @ 2024-02-10 60/week @ 2024-02-17 131/week @ 2024-02-24 26/week @ 2024-03-02 30/week @ 2024-03-09

252 downloads per month
Used in 3 crates

MIT license

23KB
330 lines

Fast Hilbert

Build Status doc crates.io usage license

Fast Hilbert 2D curve computation using an efficient Lookup Table (LUT) and only considering the lowest order for a given input.

h1 h2 h3 h4 h5 h6

  • Convert from discrete 2D space to 1D hilbert space and reverse
  • Generalized for different unsigned integer input types (thanks DoubleHyphen PR#3)
  • Speedup via lowest order computation (thanks DoubleHyphen PR#2)
  • Very fast using an efficient 512 Byte LUT
  • Only one additional dependency

Benchmarking the conversion from full 256x256 discrete 2D space to the 1D hilbert space, shows that fast_hilbert is about 12 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.2 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

Especially for higher orders fast_hilbert outperforms other libraries by using only the next lowest relevant order instead of computing the hilbert curve bit per bit for the given input. See PR #2 and #9 for more details.

For example the computation of xy2h(1, 2, 64) is very fast to compute using fast_hilbert compared to a higher x,y pair such as xy2h(u32::MAX-1, u32::MAX-2, 64):

Library x=1, y=2, order=64 x=u32::MAX-1, y=u32::MAX-2, order=64
fast_hilbert 4 ns 29 ns
hilbert_2d 73 ns 72 ns
hilbert_curve 67 ns 49 ns
hilbert 690 ns 680 ns

Dependencies

~155KB