Skip to content

actondev/aod-rtree

Repository files navigation

aod-rtree

An rtree implementation, with a focus of minimizing template (thus compile time) arguments.

Motivation

All the other implementations (superliminal, mdds, boost) that I’m aware of use compile-time template arguments for the dimensionality (& other options). This means that the N-dimension rectangles are stored like double coordinates[N]. This poses a problem when one wants to set up the dimensionality on runtime. (Note: for the superliminal version, the nushoin fork is used, which contains some additions - ie usage of std::functions)

Another motivation was to check out the idea of using handles instead of pointers (as inspired by this article). The tree’s data are stored in plain std::vector, thus making a copy of the tree is as easy as copying those vectors: no tree-traversal is needed. Extending on that, I want to create an immutable version of this library in the future.

Finally, an advantage with this library is that almost all of the implementation resides in src/aod/rtree_base.cpp, which can just be compiled & linked to. This can lead in reduced compile times & binary size (compared to using the other afforementioned libraries), depending on your rtree usage on your codebase.

Usage

#include <aod/rtree.hpp>

aod::Rtree<std::string> tree(2); // dimensionality: 2
tree.insert({0,0}, {1,1}, "0,0->1,1");
tree.insert({1,1}, {2,2}, "1,1->2,2");
tree.insert({3,3}, {4,4}, "3,3->4,4");
auto found = tree.search({0,0}, {2, 2});
// found will be a vector: { "0,0->1,1", "1,1->2,2" }

for more, just see the tests

Benchmarks

For the benchmarks, a NxN grid is constructed with points, which is shuffled in a deterministic way. Each point of the grid is then inserted to the tree (no bulk loading). The results are when compiling with -O2.

doc/benchmark-init-O2.png

doc/benchmark-search-O2.png

doc/benchmark-copy-O2.png

TODOs

  • create immutable version
    • first naive version
    • then, consider immer for structural sharing?
  • reuse node/entry/data/rect ids when removing entries
  • compile-time/template argument for type of rectangles (double, float etc). Currently double is used
  • create some scripting language bindings (NodeJs, python)

Credits