num-traits v0.2.0, which fast-hilbert depends on, doesn't support impl PrimInt for u128 but fast-hilbert requires it.

This caused a compilation error:

| error[E0277]: the trait bound `u128: PrimInt` is not satisfied
|   --> /root/.cargo/registry/src/github.com-1ecc6299db9ec823/fast_hilbert-1.0.0/src/lib.rs:59:16
|    |
| 59 |     type Key = u128;
|    |                ^^^^ the trait `PrimInt` is not implemented for `u128`
|    |
|    = help: the following other types implement trait `PrimInt`:
|              i16
|              i32
|              i64
|              i8
|              isize
|              u16
|              u32
|              u64
|            and 2 others
| note: required by a bound in `Unsigned::Key`

I'll send a PR to fix this! 🚀

How hard would it be to get the performance gains of fast_hilbert, but also be able to create Xian Liu's variants?

https://www.sciencedirect.com/science/article/abs/pii/S0096300302008081?via%3Dihub

Looks like hilbert_2d does this.

https://crates.io/crates/hilbert_2d

I wonder if the variants provide significant performance differences regarding the use of the curve as a spatial index?

I've been using this (awesome) library for generating Hilbert locations in building a map tiling engine. As the README states, for every zoom, the Hilbert curve rotates. A core property of the Hilbert curve is that relative position of items in the curve is maintained as the zoom changes. For example, this property should hold:

lower_zoom_hilbert = hilbert / (4^n) * (4^n-1)

Or more nicely:

lower_zoom_hilbert = hilbert >> 2

Because the rotation happens, these nice properties do not apply. I instead have to calculate a Hilbert location at a higher zoom and shift down for a lower zoom tile.

Is it possible to tweak the LUT so that this rotation does not happen?

z3 x4 y3 h31
z2 x2 y1 h13
z1 x1 y0 h1

Here we are with a tile at zoom 1. The hilbert location resolves to 1.

At zoom 2, the hilbert location resolves to 13 due to the rotation.

If I were to sort geographic data by their Hilbert location at one zoom, the locality will change for another, negating the static quadtree.

And then one more zoom in, and the direction of the preceding tile comes from the north.

1. Could you also include the lindel crate in the benchmarks you produce? Mr Chernoch's code has some… inefficiencies, let's say, which I took upon myself to correct. I don't think it'll come anywhere remotely close to your own speed, but I also suspect it'll at least fall within the same ball-park as the other crates.
2. One of the parametres to your functions is the so-called “order” of the Hilbert curve. Correct me if I'm wrong: I think that in your specific case all that matters is whether the order is an even or odd number. Is this indeed what's happening?
3. Do you have any idea if the tricks you used here can be generalised for arbitrary dimensions? I suspect that generalising them to eg u8s or u16s would be trivial, but the part about the arbitrary dimensions will take a bit more thought methinks.

Thanks in advance!

I thought I'd try to figure out a way to get rid of the state parametre in both the LUT's index and the results it outputs. I succeeded in achieving that, but to my astonishment it ended up consistently ~50% slower! I tried optimising things further here and there, but no consistent result came up. Here is the main.rs file that explains how I did all those things; in the lib.rs file you'll see the actual methods I used.

That said…

You said in your benchmarks that fast_hilbert is around 2-2.5 times faster than other comparable methods. My own benchmarks show the improvement to be on the order of 8-10 times faster! I strongly suspect that our benchmarks lead to different results. Thus, if this seems interesting to you, feel free to experiment as well and see; otherwise, just close the issue.

PS: The main reason I ultimately decided to show you the work I did is because I think that this will help illuminate the way to generalise to other dimensions.