So a few weeks ago I finished preliminary work on an R* Tree implementation in C++. My goal for this implementation is as follows:
- Simple API – Most existing implementations I’ve seen are far from simple
- Generic enough to use with most types, with low overhead
- N dimensions for bounding boxes
- Easy to integrate and use for Roadnav
- Take advantage of modern C++ features to get decent performance
This is a header-only implementation of an R tree with an R* index, and makes heavy use of templates, STL, and STL-style functors; but it should work in any relatively modern C++ compiler. To do searching for nodes, this implementation uses the Visitor pattern via functors — there are examples and documentation in RStarVisitor.h.
If you use this, *please* let me know, I’m very interested to see what bugs may come up, and possible performance problems. Unfortunately, I haven’t gotten around to writing any comprehensive tests for it (but given the tests I’ve run so far, I’m reasonably sure the implementation is mostly correct), but I expect that once I get it integrated into Roadnav that this will follow shortly after. Also, integration of the R* tree into Roadnav will make a lot of potential errors pop out. Look for this in the near future.
Additionally, I am thinking about some of the following ideas too:
- Adding the ability to work with extra-large datasets by saving/loading to/from disk (after all, that is the point of R trees…)
- Adding a bulk insert function — there is pseudocode already for this, but I haven’t actually written an implementation for this yet. Also, a more efficient bulk delete function
- Trying to implement it as a Boost intrusive container. I’ve been playing with some Boost stuff lately at work, and theres a lot of neat things there.
I’ll also use this opportunity to put in a plug for Roadnav — if you’re looking to work on an open source project, theres a bunch of (mostly) interesting stuff that I’m working on/planning for Roadnav. What I’m working on right now is totally removing US-specific stuff from Roadnav, and moving to an OpenStreetMap-only implementation. Theres a number of features that are getting thrown away, but I think that the dynamic community that OSM opens up to Roadnav will be well worth it.
Note: I’ve updated this quite a bit (though, remove functionality has been removed and it no longer uses the visitor pattern for data access), and its currently a part of libsdbx. Libsdbx can be found in Roadnav SVN at https://roadnav.svn.sourceforge.net/svnroot/roadnav/libsdbx/trunk/. I’ll write about this soon.. but its pretty neat. It supports R* and modified B+ trees, in memory or on disk. Check it out.
Note II: I’ve pushed the source code to github at https://github.com/virtuald/r-star-tree
Download the sourcecode here