nd-tree data structures and algorithms
BSL-1.0 License
Data-oriented pointer-free edge based n-dimensional region octree and algorithms
DISCLAIMER: this library is a work in progress and woefully incomplete!
This library provides a minimal nd
-dimensional octree implementation
(tree<nd>
) with a relatively low memory usage (1 + 1/2^nd
words per node),
ok complexity guarantees (log(N)
root-to-node and node-to-root traversals),
and configurable node data layout (as long as you can swap two elements), which
allows using a Struct of Arrays data layout for your node data if you want.
Geohashes are implemented externally (but used by some algorithms). You can implement your own for different purposes (e.g. fast neighbor queries, low-memory foot-print, ...).
For a quick start there is an n-dimensional nearest neighbor implementation in the example directory. That shows the main features of the library.
nd
: spatial dimension of the tree.root node
: largest node in the tree.level(n) -> l
: l
is the minimum number of edges between node n
and the root node
.parent(n) -> p
: p
is the smallest node enclosing n
, that is, with level(p) == level(n) - 1
.child(n) -> c
: c
is the smallest node enclosed by n
, that is, with level(c) == level(n) + 1
.sibling_group
is the group of all nodes sharing the same parent node.children_group
is the group of all children of a given node.Memory requirements:
1 + 1 / 2^nd
words of memory per nodeInternal node data layout:
Node data layout:
Thread safety:
Traversal complexities:
node-to-root and root-to-node traversals are O(log(N))
where N
is the
number of nodes in the tree.
traversal to neighbor nodes are also O(log(N))
and require one
root-to-neighbor traversal if the location hash is known (otherwise an extra
node-to-root traversal to compute the location hash)
Sorting:
Location hashes:
1 + nd
words of memory to2
words of memory for nodes at a particular level1
word of memory for leaf nodesAlgorithms: