3

我试图了解如何实现一个 R-Tree，它将用于“选择”包含在边界矩形中的一组几何对象。我查看了 Wikipedia 上的文章，其中显示了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());
    }
};

a 会std::set<Shape *, OrderShapes>表现得像一个有效的 R-Tree 吗？如果没有，我怎样才能在不重新发明轮子的情况下解决这个问题？

4

3 回答 3

11

您还可以使用 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。当值存储在索引或容器中时，您不应修改用作键的数据。

如果您不想将 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 */
于 2013-08-22T21:16:33.363 回答
3

R-Trees不是 B-Trees。它们确实有一些共同点，但可能不会比任何其他面向块（=磁盘优化）的树数据结构更多。

恕我直言，首先实现 B-Tree 有两个好处：A) 经验，以及 B) 获得用于快速块 I/O 的稳定 API。

R-Trees 的主要困难不是查询。他们几乎可以直接查询。挑战在于如何有效地修改树，即删除元素和添加元素，同时保持树的平衡。在 1 维数据集中 - 即在 B+-树中 - 这相当容易，因为您确实有一个可以用于平衡的唯一邻居。这不再适用于高维数据。

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

PS对于查询R-tree，你需要overlaps，而不是contains。

于 2013-01-08T07:38:41.993 回答
2

std::set 表现得像一个有效的 R-Tree？

绝对没有。STL 甚至不包含 B-tree 实现。std::set 只是一个红黑树，而不是 B 树。

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

你看到这个答案了吗？

于 2013-01-07T11:46:27.463 回答