8

我需要使用给定的数据点构造一棵R 树。我已经搜索了 R 树的实现。当给定矩形坐标作为输入时，我找到的所有实现都构造 r 树。我需要在给定数据点本身时构造 r 树（它可以是一维的）。代码应该注意创建包围这些数据点的矩形并构造 r 树。

4

3 回答 3

6

使用具有 min = max = 坐标的MBR（最小边界矩形）。他们都是这样做的。然而，好的实现将存储点数据，叶子中的容量大约是目录节点的两倍。

于 2011-12-22T21:18:51.703 回答
2

如果您正在寻找 C++ 实现，目前（Boost.1.57）中包含的Boost.Geometry能够存储点、框和段。明显的优点是树的叶子中的数据不重复，这意味着使用的内存更少，缓存更好等。用法如下所示：

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/geometries.hpp>
#include <boost/geometry/index/rtree.hpp>

#include <vector>

namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;

int main()
{
    typedef bg::model::point<float, 2, bg::cs::cartesian> point;
    typedef bg::model::box<point> box;

    // a container of points
    std::vector<point> points;

    // create the rtree
    bgi::rtree< point, bgi::linear<16> > rtree(points.begin(), points.end());

    // insert some additional points
    rtree.insert(point(/*...*/));
    rtree.insert(point(/*...*/));

    // find points intersecting a box
    std::vector<point> query_result;
    rtree.query(bgi::intersects(box(/*...*/)), std::back_inserter(query_result));

    // do something with the result
}
于 2015-01-09T01:30:42.437 回答
0

我想使用 Rtree 来存储点似乎是一种误用。虽然这种结构用于存储空间数据，但经过一些研究，我发现它最适合存储非零区域区域（因为名称中的 R 表示区域或矩形）。创建具有良好索引的简单表应该为更新和搜索数据提供更好的性能。考虑下面我的例子：

CREATE TABLE locations (id, latitude, longitude);
CREATE INDEX idx_locations ON locations (latitude, longitude);

优于

CREATE VIRTUAL TABLE locations USING rtree( id, minLatitude, maxLatitude, minLongitude, maxLongitude);

如果您只是打算在 maxLatitude 上重复 minLatitude 和在 maxLongitude 上重复 minLongitude 以表示点而不是矩形。尽管后一种方法可以按预期工作，但 Rtrees 适合索引矩形区域，并且使用它们来存储点是一种性能最差的误用。更喜欢上面的复合索引。

进一步阅读：http ://www.deepdyve.com/lp/acm/r-trees-a-dynamic-index-structure-for-spatial-searching-ZH0iLI4kb0?key=acm

于 2012-12-26T03:51:43.027 回答