问题标签 [r-tree]

我通过以下方式在空间索引库的帮助下创建了一个主内存 R* 索引（DBStream 实现了 bulkLoading 的接口）

我的数据是只读的，也就是说，我只想构建树一次，保存它，并在每次使用我的程序时从持久存储重新加载。显然，我可以自己保存和加载 memStorage，但是如何从中重新创建 RTree？

我正在使用空间索引（http://libspatialindex.github.com/）库批量加载 R 树：

以下是有关已构建树的信息的输出：

现在我正在尝试加载我保存在磁盘中的内容：

并且树只有一个节点（树的输出是：）

我做错了什么？为什么我不从磁盘加载整个树？

如何将 R* 树实现为持久（基于磁盘）的树？保存 R* 树索引或保存叶值的文件架构是什么？

注释：此外，如何在这样的持久性 R* 树中执行插入、更新和删除操作？

注释 II：我已经实现了一个具有批量加载功能的内存 R-Tree。但我认为当我们谈论基于磁盘的磁盘时，这完全无关紧要。

R* Tree的插入算法的步骤是什么？

注意：我希望能够通过插入来构造树。无论我选择什么条件来选择最佳叶子，它总是给我具有最大重叠和最大面积覆盖的垃圾树（在树的每一级添加后测试最小重叠区域，在树的每一级的最小扩展率等） .

现在这个 R* 树是如何通过如此精美的插入构建的（来自Wikipedia）：

我尝试从 PyPI 安装Rtree 0.7.0ImportError: No module named index ，但是当我尝试使用它时，我不断得到它。我从下载页面下载并运行了 Rtree-0.7.0.win32.exe ，一切似乎都已正确安装。

这是我得到的完整错误消息（来自 Python 3.2.2 shell）：

错误消息表明没有名为“index”的模块，但是当我查看我的C:\Python32\lib\site-packages\rtree\目录时，我看到它在那里。

什么可能导致我仍然收到ImportError: No module named index错误消息，我该如何修复它以便我可以使用 RTree 模块？

我试图了解如何实现一个 R-Tree，它将用于“选择”包含在边界矩形中的一组几何对象。我查看了 Wikipedia 上的文章，其中显示了B-Tree的数据布局示例。

我可以编写一个 B-Tree 并用它来编写一个 R-Tree，但这是两个复杂的数据结构，我必须调试、测试等。我宁愿重用现有的树实现（std::set/ multiset) 并提供排序操作。

假设我的形状有以下界面：

并提供这个函子来订购形状：

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

我有一个存储为点的矩形列表。目前，数据如下所示：

我还有一个基本函数可以测试一个矩形是否包含在另一个矩形中：

我想以一组矩形和它们的孩子结束，但我不确定我应该如何存储它们。我在想这样的事情：

上下文是这些框表示网页上的元素。数据结构是用来生成基本标记的，所以上面的结构最终会是这样的：

1. 源/目标数据结构是否适合这种情况？如果不是，那是什么？
2. 我怎样才能从源头到达目标？
3. 一位朋友建议使用 r-trees。这有意义吗？

我正在研究基于本文的 R* 树的实现。关于选择分割轴算法，我有几个问题。

R*-tree 使用 followmg 方法来寻找好的分裂。沿每个轴，条目首先按较低值排序，然后按其矩形的较高值排序。

矩形的下限值/上限值是什么意思？

对于每个分布，确定好的值。根据这些优良值确定条目的最终分布。实验测试了三种不同的优值以及在不同组合中使用它们的不同方法。

（一）面积-值area[bb(第一组)] + area[bb(第二组)]

（二）margin-valuemargin[bb(第一组)]+margin[bb(第二组)]

(三)重叠值区域[bb(第一组)+bb(第二组)]

这里 bb 表示一组矩形的边界框

这是什么意思margin-value？我将如何计算这个值？

我正在阅读R* Tree 的这个实现，我注意到它们计算重叠的方式与论文定义的方式不同。

在论文中，重叠定义如下：

对于给定的节点/矩形k ，计算k和k的每个兄弟（不包括k）之间的交集面积总和。

重叠放大是这个值的增量，如果将项目r添加到k ，节点k的重叠是多少。

像这样的东西：

在另一种实现中，它们按给定节点与要插入的项目的交集区域进行排序。像这样的东西：

显然，它们的实现在计算上比论文的定义要少。但是，我找不到任何明显的逻辑为什么这两个计算应该相等。

所以我的问题是：

1. 这两个计算是否总是最终选择相同的子树？为什么？
2. 如果它们确实导致选择不同的子树，结果是更好还是接近论文的定义？还是选择错误？

编辑：重新阅读他们的实现，我意识到他们不是在比较两个兄弟姐妹的交集，而是每个潜在叶子的交集和被插入的项目。奇怪的是，他们选择了与插入项目重叠最少的兄弟姐妹。您不想插入与所插入项目重叠最多的节点吗？

我正在使用 opencv2.1.0，我想通过 opencv 使用 r-tree 结构。我的想法是使用 r-tree 为给定的线段（都在 2d 中）找到附近的线段。我真的不知道如何使用这个 r-tree 函数，我有每个线段的终点坐标。如果有人知道如何在 opencv2.1.0 中将 r-tree 用于 2D 线段，请告诉我方法并举一些例子。为了清楚起见，我也在插入一张图片。黑线是给定的线，虚线是其他线。所以我想要所有靠近暗线的虚线。我有很多这样的场合。所以我想要有效的方式，这就是我正在寻找 r-tree 的原因。