R-Trees:我应该重新发明轮子吗？

Question

我试图了解如何实现一个R树,它将用于"选择"包含在边界矩形中的一组几何对象.我查看了维基百科上的文章,其中显示了数据布局作为B树的示例.

我可以写一个B-Tree并用它来编写一个R-Tree,但这些是两个复杂的数据结构,我必须调试,测试等等.我宁愿重用一个现有的树实现(std :: set/multiset)并提供排序操作.

假设我的Shapes有以下界面:

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

并提供此仿函数来订购形状:

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

一个std::set<Shape *, OrderShapes>表现为有效的R树吗？如果没有,如何在不重新发明轮子的情况下解决这个问题呢？

Answer 1

您还可以使用Boost.Geometry库:

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

如果您想使用自己的Point和AABB类型,则应将它们调整为Point和Box概念,以告知Boost.Geometry库如何处理这些类型.例如,请参阅以下页面:

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

否则你可以使用预定义的.

假设您想在rtree中存储指针(我将使用boost :: shared_ptr),代码可能如下所示:

#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;
}

请记住,因为AABB是Shape的属性,并且我们存储指针,所以可以从rtree空间索引的外部修改AABB.当Value存储在索引或容器中时,不应修改用作Key的数据.

如果您不想将AABB存储在Shape中或/并提高rtree安全性,则可以存储例如std :: pair <AABB,boost :: shared_ptr>.您将无法从索引外部修改用于索引的AABB.在这种情况下,你不会专门化bgi :: indexable <>因为rtree默认知道如何处理std :: pair <Box,...>类型.这看起来像这样:

// 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 */