Reason for sorting in descending order of Hilbert number?

[vcschapp]

I have a somewhat esoteric question!

I'm trying to write an implementation of the spec, and my brain is hung up on the reason why the index is sorted in descending order of Hilbert number instead of ascending order. Since I can't figure it out, I thought I would ask!

An example is the C++ implementation of hilbertSort (here) where it says:

std::sort(items.begin(), items.end(), [minX, minY, width, height] (const NodeItem &a, const NodeItem &b) {
    uint32_t ha = hilbert(a, HILBERT_MAX, minX, minY, width, height);
    uint32_t hb = hilbert(b, HILBERT_MAX, minX, minY, width, height);
    return ha > hb;
});

I'm curious if there's a geometric/efficiency/correctness reason for this or if it's more just an aesthetic choice.

Thanks for your time!

[bjornharrtell]

I don't recall I made a conscious choice here so I think it's purely accidental from when I ported this logic from https://github.com/mourner/flatbush. Maybe it's actually the other way there? I wonder if this detail matters in any meaningful way?

[vcschapp]

I think it might technically be reversed from flatbush (assuming this is the spot).

My intuition is that it doesn't matter, they both work equally well. The key is to arrange by the Hilbert index so that you get the desired spatial characteristics, but whether that's "front to back" or "back to front" probably makes no difference.

A key thing I wanted to verify with you is that I wouldn't be "breaking the spec" if I sorted ascending, although on balance I'd prefer to match your code to reduce variance.

[bjornharrtell]

Agreed that it probably doesn't matter. Thanks for the in depth interest!

I'm curious why/where you are doing your own implementation?

[vcschapp]

Thanks Bjorn!

• Why = I have a use for native GoLang, and I like coding libraries.
• Where = https://github.com/gogama/flatgeobuf

Most of the code is there now but the "appearance" and "structure" of the package will change as I work through the unit tests and documentation. It kind of feels like a jungle....