Repository files navigation

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

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 likedouble coordinates[N]. This poses a problem when one wants to set up the dimensionality on runtime. (Note: for the superliminal version, thenushoin fork is used, which contains some additions - ie usage of std::functions)

Another motivation was to check out the idea of usinghandles instead of pointers (as inspired bythis article). The tree’s data are stored in plainstd::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 insrc/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.

#include<aod/rtree.hpp>aod::Rtree<std::string>tree(2);// dimensionality: 2tree.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 thetests

For the benchmarks, aNxN 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.

• 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)

• https://github.com/lakshayg/google_benchmark_plot used for the benchmarks plots as seen in this readme
• superliminal’s RTree. The code used in this repo for splitting nodes (pick_seeds, distribute_entries - ie PickNext in the guttman original paper lingo) is based on the superliminal code
• https://github.com/hebaishi/easy-cpp-print was useful for debugging: printing out std::vectors etc