Crate fast_hilbert[−][src]
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 |