Does anyone know a good and simple to use in production code R-tree
implementation? (actually, any implementations - R*, R+
or PR-tree
would be great)
It doesn't matter if it is a template or library implementation, but some implementations that Google found look very disappointing...
You may also check out the rtree variants provided by the Boost.Geometry library:
http://www.boost.org/doc/libs/release/libs/geometry/doc/html/geometry/spatial_indexes.html
Boost.Geometry rtree implementation allows storing values of arbitrary type in the spatial index and performing complex queries. Parameters like maximum node elements may be passed as compile- or run-time parameters. It supports C++11 move semantics also emulated on pre-C++11 compilers thanks to Boost.Move. It also supports stateful allocators which allows e.g. to store the rtree in a shared memory using Boost.Interprocess. And it's fast.
On the down-side, currently persistent storage isn't yet supported so if you need more than in-memory spatial index you should probably check one of the other mentioned libraries.
Quick example:
Probably the most common use case is when you store some geometric objects in a container and their bounding boxes with some ids in the spatial index. In case of Boost.Geometry rtree this could look like this:
#include <boost/geometry.hpp> #include <boost/geometry/index/rtree.hpp> #include <vector> namespace bg = boost::geometry; namespace bgi = boost::geometry::index; /* The definition of my_object type goes here */ int main() { typedef bg::model::point<float, 2, bg::cs::cartesian> point; typedef bg::model::box<point> box; typedef std::pair<box, size_t> value; std::vector<my_object> objects; /* Fill objects */ // create the R* variant of the rtree bgi::rtree< value, bgi::rstar<16> > rtree; // insert some values to the rtree for ( size_t i = 0 ; i < objects.size() ; ++i ) { // create a box box b = objects[i].calculate_bounding_box(); // insert new value rtree.insert(std::make_pair(b, i)); } // find values intersecting some area defined by a box box query_box(point(0, 0), point(5, 5)); std::vector<value> result_s; rtree.query(bgi::intersects(query_box), std::back_inserter(result_s)); // find 5 nearest values to a point std::vector<value> result_n; rtree.query(bgi::nearest(point(0, 0), 5), std::back_inserter(result_n)); return 0; }
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With