R树：我应该重新发明轮子吗？ [英] R-Trees : should I reinvent the wheel?
问题描述
我想了解如何实现一个R-Tree，它将用于选择一组包含在边界矩形中的几何对象。我查看了维基百科上的文章，其中显示了数据布局示例为 B-Tree 。
I 可以写一个B树，并使用它来写一个R树，但这是两个复杂的数据结构，我必须调试，测试等。我宁愿重用一个现有的树实现std :: set / multiset）并提供排序操作。
假设我有我的形状的以下界面：
class Shape
{
public：
Shape（）;
virtual〜Shape（）;
const AABB& bounding_box（）const = 0;
};
并提供这个函子订购形状：
<预先class =lang-cpp prettyprint-override>
struct OrderShapes
{
bool operator（）（Shape * const& left，Shape * const& right）const
{
return right-> bounding_box（）。contains（left-> bounding_box（））;
}
};
会 std :: set< Shape *，OrderShapes> 表现为一个有效的R树？
也可以使用Boost.Geometry库：
http://www.boost.org/doc/libs/release/libs/geometry/doc/html/index.html
如果您' d喜欢使用你自己的Point和AABB类型，你应该适应他们的Point和Box的概念，以告诉Boost.Geometry库如何处理这些类型。例如。请参阅以下页面：
假设你想存储指针（I'在rtree中使用boost :: shared_ptr），代码可能如下所示：
#include& boost / geometry。 hpp>
#include< boost / geometry / index / rtree.hpp>
#include< boost / foreach.hpp>
#include< vector>
命名空间bg = boost :: geometry;
namespace bgi = boost :: geometry :: index;
namespace bgm = boost :: geometry :: model;
/ *注册你的Point和Box类型到这里* /
//或使用预定义的类型
typedef bgm :: point< float，2， bg :: cs :: cartesian>点;
typedef bgm :: box< Point> AABB;
class Shape
{
public：
Shape（）{}
virtual〜Shape（）{}
const AABB& bounding_box（）const {return m_aabb; }
private：
AABB m_aabb;
};
//告诉rtree如何从Shape中提取AABB
命名空间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（）; }
};
}}} //命名空间boost :: geometry :: index
int main（）
{
// rtree
bgi :: rtree< boost :: shared_ptr< Shape>，bgi :: rstar< 32> > rt;
//存储一些形状
rt.insert（boost :: shared_ptr< Shape>（new Shape（）））;
rt.insert（boost :: shared_ptr< Shape>（new Shape（）））;
rt.Insert（boost :: shared_ptr< Shape>（new Shape（）））;
/*...*/
//搜索一些形状
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）
{
/ *对每个形状执行操作* /
/如果形状存储在rtree中，则修改AABB！ * /
}
//从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<框，...>类型。这可能如下所示：
//值类型
typedef std :: pair< AABB，boost :: shared_ptr< Shape> > MyVal;
// rtree
bgi :: rtree< MyVal，bgi :: rstar< 32> > rt;
//存储形状
boost :: shared_ptr< Shape> s（new Shape（））;
rt.insert（std :: make_pair（s-> calculate_aabb（），s））;
/ *其余代码* /
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 ?
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:
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 */
这篇关于R树：我应该重新发明轮子吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
