database - Pre RTree step：将一组点划分为矩形区域，每个区域包含一个点

Question

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

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

/约翰

score 2 · Accepted Answer

Oracle Spatial Cartridge文档描述了可以满足您需求的细分算法。简而言之：

score 2 · Accepted Answer

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

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

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

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

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

分割成左右（或上下）分割点的矩形。

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

与另一张海报提供的分割成正方形方法相比，它的优势在于它可以更好地适应偏斜的点分布。

score 0 · Accepted Answer

我认为你在问题陈述中遗漏了一些东西。假设您有 N 个点 (x, y)，这样每个点都具有唯一的 x 和 y 坐标。您可以将您的区域划分为 N 个矩形，然后将其划分为 N 个垂直列。但这并不能帮助您轻松解决最近的 POI 问题，不是吗？所以我认为您正在考虑您尚未阐明的矩形结构。

插图：

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

数字是 POI，垂直线显示细分为 7 个矩形区域。但显然，细分中没有太多“有趣”的信息。您没有提到的细分是否有一些额外的标准？

3 回答 3