Crate fast_hilbert
source · [−]Expand description
Memory efficient and fast implementation of the Hilbert space-filling curve computation.
The conversion from 2D coordinates to the hilbert-curve can be described as a state diagram:
(xy) => Discrete input coordinates in 2D space
[hh] => Hilbert output for the given Input
┌──────────(01) (11)◄──────────┐
|┌────────►[11] [00]──────────┐|
|| # 3 # ||
|| (00) (10) ||
|| [10] [01] ||
|| |▲ ▲| ||
▼| └┘ └┘ ▼|
(01) (11)─┐ ┌─(01) (11)
[11] [10]◄┘ └►[01] [00]
(00) (10)◄┐ ┌─(00) (10)
[00] [01]─┘ └►[10] [11]
|▲ ┌┐ ┌┐ ▲
|| |▼ ▼| ||
|| (01) (11) ||
|| [01] [10] ||
|| # 0 # ||
|└─────────(00) (10)◄────────┘|
└─────────►[00] [11]──────────┘Instead of only processing one state-transition at a time, a pre-computed transition LUT from one state with three input values to the next state is pre-computed and stored in a lookup table. The whole LUT can be packed in a 256 Byte long data-structure which fits easily in modern CPU caches and allow very fast lookups without any cache misses.
Compared to other implementations, fast_hilbert is about 12 times faster compared to other rust hilbert-curve implementations and uses only
512 Bytes of RAM for the lookup tables (one for 2D->1D and another for 1D->2D).
Traits
Unsigned integer input type which has a double value type as key