预RTree步骤:将一组点分成矩形区域,每个区域包含一个点

Question

鉴于我当前的位置(lat,long),我想快速找到兴趣点问题中最近的邻居.因此,我打算使用R-Tree数据库,它允许快速查找.但是,首先必须填充数据库 - 当然.因此,我需要确定覆盖该区域的矩形区域,其中每个区域包含一个感兴趣的点.

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

/约翰

Answer 1

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

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

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

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

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

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

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

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