algorithm - 使用空间索引查找彼此范围内的点

Question

我正在尝试找到适合特定问题的空间索引结构:使用联合查找数据结构，我想连接/关联彼此在一定范围内的点。我有很多要点，我正在尝试通过使用更好的空间索引来优化现有解决方案。

现在，我正在使用一个简单的 2D 网格索引我的点图中每个宽度 [阈值距离] 的正方形，并且我通过在网格中的相邻正方形中搜索点来寻找潜在的并集。

然后我计算到相邻单元格组合的平方欧几里得距离，我将其与我的平方阈值进行比较，然后我使用联合查找结构(使用路径压缩等进行优化)来构建点组。

下面是该方法的一些说明。单个黑色点实际上表示属于网格单元格的一组点，向外的彩色箭头表示与外部点的实际距离比较。

(我也在检查属于相同单元格的潜在连接点)。

通过使用这种模式，当我遍历网格单元时，通过使用不与已测试内容重叠的适当“相邻单元格”模式，我确保我不会进行任何距离比较两次。

问题是:这种方法甚至不够快，我正在尝试用可能更快的方法替换“空间网格索引”方法。

我已经研究过四叉树作为这个问题的合适空间索引，但我认为它不适合解决它(我没有看到任何方法对特定单元执行重复的“邻居”检查更多有效地使用四叉树)，但也许我错了。

因此，我正在寻找一种更好的算法\数据结构来有效地索引我的点并查询它们的接近度。

提前致谢。

Answer 1

我有一些意见:

1) 我认为你的问题等同于“空间连接”。空间连接采用两组几何图形，例如一组 R 矩形和一组 P 点，并为每个矩形查找该矩形中的所有点。在您的情况下，R 是每个点周围的矩形(边长 = 2 * 最大距离)，P 是您的点集。搜索 spatial join 可能会给你一些有用的引用。

2) 您可能想看看空间填充曲线。空间填充曲线为一组空间实体(点)创建了一个线性顺序，其属性是线性顺序中的点通常在空间中也很接近(反之亦然)。这在开发算法时可能很有用。

3) 查看OpenVDB . OpenVDB 具有高度优化的空间索引结构，可遍历“体素”单元及其邻居。

4) 查看 PH-Tree (免责声明:这是我自己的项目)。 PH-Tree 有点像四叉树，但使用低级位操作来优化导航。它也是 Z-ordered/Morten-ordered(见上面的空间填充曲线)。您可以为每个点创建一个窗口查询，它返回该矩形内的所有点。据我所知，PH-Tree 是这种操作最快的索引结构，尤其是当矩形中通常只有 9 个点时。如果您对代码感兴趣，V13 实现可能是最快的，但是 V16 应该更容易理解和修改。我在我相当旧的台式机上尝试过，使用大约 1,000,000 个点，我每秒可以进行大约 200,000 个窗口查询，因此找到每个点的所有邻居大约需要 5 秒。

如果您使用的是 Java，我的 spatial index collection也可能有用。