如何使用给定的数据点构建RTree

Question

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

- rajsekhar

Answer 1

在编程中，使用最小外接矩形（Minimum bounding rectangle，MBRs），其中min = max = 坐标。所有人都是这样做的。但好的实现将会在叶子节点中存储点数据的容量大约是目录节点的两倍。

- Has QUIT--Anony-Mousse

---

能详细说明一下吗？在大多数R树代码中，您会创建一个矩形（具有右下角和右上角点），并将该矩形添加到R树中。您是说如果我们想要存储单个点，那么两个点（右下角和右上角）应该是同一个点吗？ - stackoverflowuser2010

一个单点的MBR当然是min=max=coordinate。在叶子级别存储点而不是MBR，我们会得到大约两倍数量的对象，并将磁盘空间减少近2倍。 - Has QUIT--Anony-Mousse

谢谢。通过解读您的回答，我认为您的意思是“是的，如果我们想要存储单个点，则两个点（右下角和右上角）应该是同一个单个点”。相比于其他数据结构（如点区域四叉树），R树是否更适合存储点？ - stackoverflowuser2010

根据您的数据、查询和实现情况而定。在我的实验中，R树表现出色，比如k-d树容易因为更好的扇出而胜出。选择正确的页面大小是至关重要的。至于四叉树，R树具有更好的扇出，并且是数据自适应的，因此如果您的数据是聚类的，它们很可能会更好。 - Has QUIT--Anony-Mousse

如果我尝试使用5位浮点精度（例如37.80995，-122.47735）存储GPS点，您的方法是否有效？ - stackoverflowuser2010

嗯，我不知道有一个好的5位浮点二进制编码。 但是，您可以使用整数，32位整数精度应该是GPS数据的合理选择。 - Has QUIT--Anony-Mousse

Answer 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
}

- Adam Wulkiewicz

---

以下是一些带有断言的数值示例：https://github.com/cirosantilli/cpp-cheat/blob/160e96ec04df93c4ad227d63af5e651498bca834/boost/rtree.cpp - Ciro Santilli OurBigBook.com

Answer 3

我认为使用R树来存储点似乎是一种误用。尽管这种结构被指示用于存储空间数据，但经过一些研究，我发现它最适合存储非零面积区域（因为名称中的 R 代表 Region 或 Rectangle）。创建一个简单表格并建立良好索引应该能够提供更好的性能，无论是更新还是搜索数据。请考虑下面的例子：

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);

如果您只是计划在每一行中重复minLatitude和maxLatitude以及minLongitude和maxLongitude，以表示点而不是矩形。尽管后一种方法将按预期工作，但R树适用于索引矩形区域，并且将它们用于存储点是最差性能的误用。建议使用上述复合索引。

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

- Cléssio Mendes

---

不能同意。我需要仅使用点索引，并且R树查询比复合索引（SQLite）更快。空间性不仅是关于数据，还包括查询：如果你想知道一个矩形区域内包含的所有点（数据），试试R树。 - pwes