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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
