Crate fast_hilbert

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
# S # => State

 ┌──────────(01) (11)◄──────────┐
 |┌────────►[11] [00]──────────┐|
 ||           # 3 #            ||  
 ||         (00) (10)          ||
 ||         [10] [01]          ||
 ||          |▲   ▲|           ||
 ▼|          └┘   └┘           ▼|
(01) (11)─┐           ┌─(01) (11)
[11] [10]◄┘           └►[01] [00]
  # 1 #                   # 2 #
(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 2.5 times faster as comparable rust hilbert-curve implementations and uses only 512 Bytes of RAM for the lookup tables (one for 2D->1D and another for 1D->2D).

Functions

h2xy	Convert form 1D hilbert space to 2D coordinates
xy2h	Convert form 2D to 1D hilbert space