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

Question

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

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

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

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

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

通过使用这种模式，我确保我没有通过使用适当的“相邻单元”模式进行两次距离比较，当我迭代网格单元时，该模式不会与已经测试过的东西重叠。

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

我已将四叉树视为解决此问题的合适空间索引，但我认为它不适合解决它（我看不到任何方法可以更有效地使用四叉树），但也许我错了。

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

提前致谢。

标签： algorithmperformanceoptimizationgraph-algorithmkdtree

Answer 1

我有一些意见：

1）我认为您的问题相当于“空间连接”。空间连接采用两组几何图形，例如一组R矩形和一组P点，并为每个矩形找到该矩形中的所有点。在您的情况下，R将是每个点周围的矩形（边长 = 2 * 最大距离），P是您的点集。搜索空间连接可能会给您一些有用的参考。

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，我的空间索引集合也可能有用。