### 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 |

#**630** in Algorithms

**445** downloads per month

Used in **4** crates

**MIT**license

23KB

330 lines

# Fast Hilbert

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

- 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

is very fast to compute using `xy2h``(``1``,` `2``,` `64``)`

compared to a higher x,y pair such as `fast_hilbert`

:`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

~150KB