27

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...

River
  • 8,585
  • 14
  • 54
  • 67
M. Williams
  • 4,945
  • 2
  • 26
  • 27

4 Answers4

29

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;
}
Adam Wulkiewicz
  • 2,068
  • 18
  • 24
  • 6
    +1 for giving an example with the Boost library – djondal Nov 01 '13 at 16:42
  • Do you still need persistent storage ? My master thesis will be on R-Trees and I plan to work on implementations as well. Could I be of any help? – Nikos Athanasiou Jul 02 '15 at 10:30
  • @NikosAthanasiou Yes, it's still planned but I don't have enough free time to work on it. There are also a few more things besides the persistent storage support which I planned to. Of course any help is appreciated. Please contact us on the Boost.Geometry mailing list. – Adam Wulkiewicz Jul 02 '15 at 13:28
  • Sorry to ask on an old answer, but is it possible to adapt this to more than 2 dimensions ? If so, could you give me some pointers as to how should I go about changing the data types ? – NILobachevsky Nov 18 '16 at 12:32
  • 1
    Second template parameter of `bg::model::point` is the dimension. – Adam Wulkiewicz Nov 18 '16 at 23:12
17

Check R-Trees code on http://www.superliminal.com/sources/sources.htm

also check

http://www.virtualroadside.com/blog/index.php/2008/10/04/r-tree-implementation-for-cpp/

Lior Kogan
  • 19,919
  • 6
  • 53
  • 85
  • I still think these versions lack in versatibility, but, well, looks like ok to use – M. Williams Apr 25 '10 at 18:47
  • Bother versions need a compile-time choice of the data dimensionality which makes them useless (to me). – Michael Nett Dec 24 '12 at 12:50
  • 5
    @MichaelNett: So you're downvoting because the open-source implementations that I referred to are useless to you? – Lior Kogan Dec 24 '12 at 13:56
  • @LiorKogan That is true, but mainly because I see this as a major drawback in the implementation. – Michael Nett Dec 25 '12 at 07:44
  • 1
    @MichaelNett Use the templated C++ version of the first one (http://www.superliminal.com/sources/sources.htm) which takes a dimension argument in addition to storage data type. – Melinda Green Jul 02 '15 at 08:45
10

I updated the implementation found in http://www.superliminal.com/sources/sources.htm to support a broader range of data types.

You can find my version on github: https://github.com/nushoin/RTree

The original version is public domain, as is mine.

Yariv
  • 486
  • 6
  • 12
5

spatialindex provides a nice interface to different types of spatial (and spatio-temporal) index structures including R, R*, TPR trees at http://libspatialindex.github.com/

arthur
  • 1,034
  • 2
  • 17
  • 31