c++ - R-树 : should I reinvent the wheel?

Question

我正在尝试了解如何实现 R 树，它将用于“选择”边界矩形中包含的一组几何对象。我检查了 article在维基百科上，它以 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 树？如果没有，我如何在不重新发明轮子的情况下解决这个问题？

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

如果您不想将 AABB 存储在 Shape 中或/和提高 rtree 安全性，您可以存储例如std::pair 。您将无法从索引外部修改用于索引的 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 */