R-Tree：我应该重复造轮子吗？

Question

R-Tree：我应该重复造轮子吗？

3

我正在尝试理解如何实现R-Tree，它将用于在包围矩形中选择一组几何对象。我查看了维基百科上的文章，其中展示了数据布局的示例作为B-Tree。

我可以编写B-Tree并使用它来编写R-Tree，但这是两个复杂的数据结构，我必须进行调试、测试等操作。我宁愿重用现有的树实现（std::set/multiset）并提供排序操作。

假设我有以下接口用于我的形状：

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-Tree 吗？如果不能，我该如何解决这个问题而不必重新发明轮子？

- Jean-Marie Comets

3个回答

3

R-Trees不是B-Trees。它们有一些共同点，但可能与任何其他块导向（=磁盘优化）树数据结构一样多。

在我看来，首先实现B-Tree有两个好处：A）经验和B）获得快速块I/O的稳定API。

R-Trees的关键难点不在于查询。它们的查询几乎是直截了当的。挑战在于如何有效地修改树，即删除元素和添加元素，同时保持树的平衡。在一维数据集中 - 即在B+-tree中 - 这相当容易，因为您有一个可用于平衡的唯一邻居。在更高维度的数据中，这种方法不再适用。

但是，您当然可以寻找现有的R-tree库，例如libspatialindex

P.S. 对于查询R-tree，您需要使用overlaps而不是contains。

- Has QUIT--Anony-Mousse

2

std::set能够作为一个有效的R-Tree吗？

绝对不行。STL甚至不包含B树实现。std::set只是红黑树，而不是B树。

我如何在不重复发明轮子的情况下解决这个问题？

你看过这个答案了吗？

- Soonts

是的，我看过那个答案了，但我希望通过调整一个STL容器来实现它。 - Jean-Marie Comets

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Adam Wulkiewicz · Accepted Answer

你也可以使用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是形状的属性，而我们存储的是指针，所以有可能从rtree空间索引的外部修改AABB。当值存储在索引或容器中时，不应修改用作键的数据。

如果您不想将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 */