RTree 前步骤：将一组点划分为每个包含一个点的矩形区域

题

给定我当前的位置（纬度，经度），我想快速找到兴趣点问题中的最近邻居。因此我打算使用 R-Tree 数据库，它可以快速查找。然而，当然，首先必须填充数据库。因此，我需要确定覆盖该区域的矩形区域，其中每个区域包含一个兴趣点。

我的问题是如何预处理数据，即如何将区域细分为这些矩形子区域？（我想要矩形区域，因为它们很容易添加到 RTree - 与更一般的 Voronoi 区域相比）。

/约翰

解决方案

编辑： 下面的方法有效，但忽略了 R 树的关键特征——R 树节点的分裂行为被明确定义，并维护平衡树（通过类似 B 树的属性）。所以事实上，你所要做的就是：

选择每页的最大矩形数
创建种子矩形（使用彼此距离最远的点、质心等）。
对于每个点，选择一个矩形将其放入
1. 如果它已经落入一个矩形中，请将其放入其中
2. 如果没有，则扩展需要扩展最少的矩形（测量“最少”出口的不同方法 - 面积有效）
3. 如果应用多个矩形 - 根据其填充程度或其他一些启发式选择一个
如果发生溢出——使用二次分割来移动东西......
等等，直接使用教科书上的 R 树算法。

我认为下面的方法可以找到你的初始种子矩形；但您不想以这种方式填充整个 R 树。一直进行分割和重新平衡可能会有点昂贵，因此您可能需要使用下面的 KD 方法来完成大部分工作；只是不是所有的工作。

KD方法：将所有内容都包含在一个矩形中。

如果矩形中的点数>阈值，则沿D方向扫描，直到覆盖一半点。

将分割点左右（或上方和下方）分成矩形。

在新矩形上递归调用相同的过程，并使用下一个方向（如果您从左到右，现在将从上到下，反之亦然）。

与另一张海报提供的划分为正方形的方法相比，这种方法的优点是它可以更好地适应倾斜的点分布。

其他提示

Oracle 空间盒文档描述了可以执行您想要的操作的曲面细分算法。简而言之：

我觉得你的问题陈述缺少的东西。假设你有N个点（X，Y），使得每一个点都具有独特的X和Y坐标。你可以只把它分成N立柱将您的区域划分为N个矩形即可。但是，这并不能帮助你轻松解决最近的POI问题，不是吗？所以我认为你正在考虑一些事情你还没有阐明的矩形结构。

插图：

| | | | |5| | |
|1| | | | |6| |
| | |3| | | | |
| | | | | | | |
| |2| | | | | |
| | | | | | |7|
| | | |4| | | |

的数字是POI和垂直线示出了一个划分成7个的矩形区域。但显然没有在细分很多“有趣”的信息。是否有一个你没有提到的细分一些附加标准？

许可以下： CC-BY-SA 和归因