问题标签 [r-tree]

让这个坐标类与欧几里得距离，

并让坐标网格，例如

然后对于任何给定的坐标

最近的点x是

所以前三个最接近的是nearest.take(3)。

有没有办法让这些计算更省时，特别是对于有一百万点的网格的情况？

我在 Windows 7 64 位中使用 Python 的 Canopy 安装。Rtree 似乎安装正确。

但是，当我尝试导入 rtree 时，出现以下错误：

我在 Ubuntu 中遇到了类似的问题，如果不一样的话。我通过软件管理器直接安装 libspatialindex 解决了这个问题。这在 Windows 中是不可能的，我找不到明确的安装方法。

我下载并安装了完整的 OSGeo4W 套件，并在 Canopy 中重新安装了 Rtree，希望 libspatialindex 包含在捆绑包中。那没有用。

有没有办法解决这个问题？

我正在寻找一种空间索引的实现，它允许我快速计算和总结指定区域中包含的值。

更长的版本：我有很多对象要存储在空间索引中。它们每个都有它们在 n 维空间中的坐标以及一个额外的值。给定一个范围，我需要快速回答以下问题：（1）该范围内有多少对象以及（2）它们所有值的总和是多少。

我知道空间索引通常是使用 R-trees 实现的。当然，我可以简单地检索一个范围内的所有对象并每次总结它们。

但是，通过将包含在该节点下的所有元素的总和和计数存储在该节点内，似乎存在显着的加速机会。因此，一旦有问题的节点完全在查询范围内，就没有必要进一步下降树。

有谁知道支持这种“缓存”操作的 C++ 实现？

我目前正在参加“数据建模”课程。对于我的最后一个项目，我需要对“用于空间搜索的 R-tree 索引”进行研究。但是，我对与主题相关的许多概念（空间数据、多维数据……）完全不熟悉。所以，我阅读了wiki，当我遇到新概念时，我尝试在方法。
但是，我不认为这种自上而下的方法是解决此问题的一种非常有效的方法。因此，如果有人能提出一种我需要提前阅读的方法/清单，以便理解 R-tree，并希望从中做出某种实现，我将不胜感激。

我似乎找不到一种有效的方法来迭代boost R-tree ( boost::geometry::index::rtree)。到目前为止，我想出的唯一方法是使用非常大的边界框执行查询，以便在向量中返回所有元素的副本，但这显然既不节省空间也不节省时间。理想情况下，我只想使用 STL 样式的迭代器以通常的方式迭代树，但这似乎不可能？

我目前正在开发一个项目，该项目需要一个线程来构建一个队列，该队列包含 30 个（ish）最近的进程，其中最接近 3D 环境中的玩家。

所有这些进程都可以在环境中移动，也可以保留它们所在的起始节点。我曾考虑使用 R 树，但由于其插入时间高得离谱，它似乎不太可行。

KD-Trees 不起作用，因为它们往往只适用于静态环境。

另请注意，这将与主更新线程异步运行，因此原子方法效果最好。

有人可以建议一种方法吗？

关于树搜索算法，特别是四叉树和 r-tree，它们在寻找最近邻居时如何解决边缘错误。我不擅长用文字来解释，所以我做了一些图片。

对于图片，查找最近邻居的输入坐标为绿色，我假设最终成为“找到的”最近邻居的是红色。实际最近的邻居是蓝色的。

在这个四叉树中，蓝色的右下象限将仅使用一个红色点进行搜索，而实际上，输入坐标（绿色）非常靠近边缘，实际上更靠近蓝色点。

如果坐标在一个矩形内但非常靠近边缘，则与 R-tree 类似，它更靠近另一个矩形中的点，如下所示，其中白点被赋予坐标：

它完全在红色框中，但更接近洋红色框中的一个点。

我知道一些范围搜索数据结构，例如 kd-tree、范围树和四叉树。但是所有的实现都在内存中，我怎样才能在二级内存上以高性能的 I/O 效率实现它们呢？

这是条件：

1)：二维上的一组静态点。

2）：仅用于查询，没有插入或删除。

3）：适应二级内存。

谢谢。

我正在尝试将 2D 点存储在 rtree（版本 0.8.2）中，然后使用 Python 删除它们。我知道 rtree 适用于矩形（或 3D 框），但我猜点是矩形的子集。

从 rtree 中删除项目时出现奇怪的行为。下面的脚本显示了这种行为：

输出是：

从文档（http://toblerity.org/rtree/class.html）：

delete (id, coordinates) 从索引中删除指定坐标内具有给定 'id' 的项目。

参数：

id – 长整数 一个长整数，它是该索引条目的标识符。ID 不需要是唯一的才能插入到索引中，如果需要，用户可以确保它们是唯一的。

坐标- 序列或数组 Dimension * 2 坐标对，表示要从索引中删除的项目的每个维度中的最小和最大坐标。它们的顺序将取决于索引的交错数据成员。这些不是包含项目的空间的坐标，而是项目本身的坐标。它们与 id 参数一起确定将删除哪个项目。这可能是一个满足 numpy 数组协议的对象。

但可以看出，id在输出的第 4 行中删除了给定坐标但不在给定坐标内的点。

该文档还明确指定ids 在插入或删除中都不需要唯一。（0 == id示例中的重复是故意的，因为我的应用程序需要重复id的 s。同一“事物”的多个点。）

还确认可以使用xmin == xmax和来索引点ymin == ymax。

我是否使用了错误的库，或者 libspatialindex（Python rtree 背后的二进制库）的行为与 rtree 文档状态不同？

我需要创建一个 3D R*-tree，也许是为了长时间存储，但性能也是一个问题。为了创建树，我决定使用 Boost 的 spacialindex 并且基本上找到了两种可能的方法。

或者我直接使用对象创建它，因为它在这里：存储在向量中的多边形索引，但是这不允许我在不再次创建 R*-tree 的情况下存储和加载它。

或者我可以使用此处解释的映射文件：使用 Boost.Interprocess 存储在映射文件中的索引，但是，我不确定在这种情况下查询的性能是否足够好。

我的 r-tree 将包含数千个条目，但很可能少于 100,000 个。现在我的问题是，与使用标准对象相比，使用映射文件是否存在任何强大的性能问题？此外，如果创建大约 100,000 个值的 R*-tree 不需要花费大量时间（我可以将所有边界框和相应的键/数据存储在一个文件中），那么跳过映射文件并在每次运行程序时创建树？

希望有人可以在这里帮助我，因为文档并没有真正提供太多信息（尽管它仍然比 libspacialindex 的文档更好）。