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

Functions

Convert form 1D hilbert space to 2D coordinates
Convert form 2D to 1D hilbert space. Input type T must have half the capacity of the result type. For example (u32, u32) => u64.