R-Trees : should I reinvent the wheel?

Question

I'm trying to understand how to implement an R-Tree which will be used for "selecting" a set of geometrical objects contained in a bounding rectangle. I checked out the article on Wikipedia, which shows an example of data layout as a B-Tree.

I could write a B-Tree and use it to write an R-Tree, but these are two complicated data structures which I'd have to debug, test, etc. I would rather reuse an existing tree implementation (std::set/multiset) and provide the sorting operation.

Assuming I have the following interface for my Shapes:

class Shape
{
    public:
        Shape();
        virtual ~Shape();
        const AABB & bounding_box() const = 0;
};

And providing this functor for ordering Shapes:

struct OrderShapes
{
    bool operator()(Shape * const & left, Shape * const & right) const
    {
        return right->bounding_box().contains(left->bounding_box());
    }
};

Would a std::set<Shape *, OrderShapes> behave as a valid R-Tree ? If not, how can I solve this problem without reinventing the wheel ?

Answer 1

You could also use Boost.Geometry library:

http://www.boost.org/doc/libs/release/libs/geometry/doc/html/index.html

If you'd like to use your own Point and AABB types, you should adapt them to the Point and Box concepts in order to tell Boost.Geometry library how to handle those types. E.g. see the following page:

http://www.boost.org/doc/libs/release/libs/geometry/doc/html/geometry/reference/adapted/register/boost_geometry_register_box.html

otherwise you may use predefined ones.

Assuming that you'd like to store pointers (I'll use boost::shared_ptr) in the rtree, the code could look like this:

#include <boost/geometry.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <boost/foreach.hpp>
#include <vector>

namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
namespace bgm = boost::geometry::model;

/* The registration of your Point and Box types goes here */

// OR use predefined ones
typedef bgm::point<float, 2, bg::cs::cartesian> Point;
typedef bgm::box<Point> AABB;

class Shape
{
public:
    Shape() {}
    virtual ~Shape() {}
    const AABB & bounding_box() const { return m_aabb; }
private:
    AABB m_aabb;
};

// Tell the rtree how to extract the AABB from the Shape
namespace boost { namespace geometry { namespace index {

template <>
struct indexable< boost::shared_ptr<Shape> >
{
    typedef boost::shared_ptr<Shape> V;
    typedef AABB const& result_type;
    result_type operator()(V const& v) const { return v->bounding_box(); }
};

}}} // namespace boost::geometry::index

int main()
{
    // The rtree
    bgi::rtree< boost::shared_ptr<Shape>, bgi::rstar<32> > rt;

    // Store some shapes
    rt.insert(boost::shared_ptr<Shape>(new Shape()));
    rt.insert(boost::shared_ptr<Shape>(new Shape()));
    rt.insert(boost::shared_ptr<Shape>(new Shape()));
    /*...*/

    // Search for some shapes
    std::vector<boost::shared_ptr<Shape> > query_result;
    rt.query(bgi::intersects(AABB(/*...*/)), std::back_inserter(query_result));

    BOOST_FOREACH(boost::shared_ptr<Shape> & s, query_result)
    {
        /* Do something with each shape */
        /* but don't modify the AABB if the Shape is stored in the rtree! */
    }

    // Remove them from the rtree
    BOOST_FOREACH(boost::shared_ptr<Shape> & s, query_result)
    {
        rt.remove(s);
    }

    return 0;
}

Keep in mind that because the AABB is Shape's attribute and we're storing pointers, it's possible to modify AABB from the outside of the rtree spatial index. You shouldn't modify data used as a Key when the Value is stored in the index or container.

If you don't want to store AABB inside the Shape or/and improve the rtree safety you may store e.g. std::pair< AABB, boost::shared_ptr >. You won't be able to modify AABB used for indexing from the outside of the index. In this case you musn't specialize bgi::indexable<> because the rtree by default knows how to handle std::pair< Box, ... > type. This could look like this:

// The value type
typedef std::pair<AABB, boost::shared_ptr<Shape> > MyVal;

// The rtree
bgi::rtree<MyVal, bgi::rstar<32> > rt;

// Store a shape
boost::shared_ptr<Shape> s(new Shape());
rt.insert(std::make_pair(s->calculate_aabb(), s));

/* The rest of the code */

Answer 2

R-Trees are not B-Trees. They do have some things in common, but probably not more than any other block oriented (= disk optimized) tree data structure.

IMHO, implementing a B-Tree first is good for two things: A) experience, and B) get a stable API for fast block I/O.

The key difficulty with R-Trees is not the query. They are pretty much straight forward to query. The challenge is how to efficiently modify the tree, i.e. remove elements and add elements, while keeping the tree balanced. In a 1 dimensional data set - i.e. in a B+-tree - this is fairly easy, as you do have a unique neighbor that you can use for balancing. This no longer works in higher dimensional data.

But you could of course look for exising R-tree libraries such as libspatialindex

P.S. For querying the R-tree, you need overlaps, not contains.

Answer 3

std::set behave as a valid R-Tree?

Definitely no. The STL doesn't even contain a B-tree implementation. std::set is merely a red-black tree, not a B-tree.

how can I solve this problem without reinventing the wheel?

Did you see this answer?