2
$\begingroup$

I am working on a project which needs to traverse a 2d spatial grid, and would like to use a space-filling curve indexing scheme. Unfortunately, I have no guarantee that the input grid will be a power of two along either dimension. In fact, it may be just barely over a power of two in some cases. Virtually extending the grid to be a power of two in size may use too much memory (it is a very large grid). Is it still possible to use a space-filling curve, such as a Morton curve, to index this grid?

$\endgroup$
2
$\begingroup$

What kind of indexing do you need? If it is just a lookup, your can interleave the bits of you coordinates to get a z-ordered Morton value. These could be stored in binary trie (critbit-tree) that uses prefix sharing. Traversing the tree gives you Morton-order, and the possible prefix sharing should reduce memory consumption. I implemented one in Java: critbit

If you also need geometric queries (kNN, window queries, range queries), you could try the PH-Tree, it's like a bit like quadtree, but uses prefix sharing like a trie and some other things to be much more efficient (memory and speed) than a quadtree. The tree uses internally a Morton ordering so a full traversal or Window queries will always return Morton-ordered results.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.