使用空间索引查找彼此范围内的点
Using a spatial index to find points within range of each other
我正在尝试找到适合特定问题的空间索引结构：使用联合查找数据结构，我想要 connect\associate 彼此在一定范围内的点。
我有很多要点，我正在尝试通过使用更好的空间索引来优化现有解决方案。
现在，我正在使用一个简单的 2D 网格索引我的点图中每个宽度 [阈值距离] 的正方形，并且我通过在网格中的相邻正方形中搜索点来寻找潜在的并集。
然后我计算到相邻单元格组合的平方欧几里得距离，我将其与我的平方阈值进行比较，然后我使用联合查找结构（使用路径压缩等进行优化）来构建点组。
这是该方法的一些说明。单个黑色点实际上表示属于网格单元格的一组点，向外的彩色箭头表示与外部点的实际距离比较。
（我也在检查属于相同单元格的潜在连接点）。
通过使用此模式，我确保在遍历网格单元时使用不与已测试内容重叠的适当 "neighbor cell" 模式，我不会进行两次距离比较。
问题是：这种方法甚至不够快，我正在尝试用可能更快的方法替换 "spatial grid index" 方法。
我已经研究过四叉树作为这个问题的合适空间索引，但我认为它不适合解决它（我没有看到任何执行重复 "neighbours" 检查的方法一个特定的单元格更有效地使用四叉树），但也许我错了。
因此，我正在寻找更好的 algorithm\data 结构来有效地索引我的点并查询它们的接近度。
提前致谢。
对此的标准方法是 "sweep and prune" 算法。按 X 坐标对所有点进行排序，然后遍历它们。正如您所做的那样，保持当前点的阈值距离（以 X 为单位）内的点的最低索引。该范围内的点是合并的候选点。然后你做同样的事情按 Y 排序。然后你只需要检查在 X 和 Y 扫描中出现的那些对的欧几里得距离。
请注意，使用当前的联合查找方法，如果附近有一堆 "bridging" 点，您最终可能会合并彼此相距很远的点。因此，您的基本方法——基于接近度合并点组——可能会导致任意数量的距离误差，而不仅仅是阈值距离。
我有一些意见：
1) 我认为你的问题相当于一个"spatial join"。空间连接采用两组几何图形，例如一组 R 矩形和一组 P 点，并为每个矩形查找所有点那个矩形。在您的情况下，R 将是每个点周围的矩形（边长 = 2 * 最大距离），而 P 是您的点集。搜索空间连接可能会给你一些有用的参考。
2) 您可能想看看 space 填充曲线。 Space 填充曲线为一组空间实体（点）创建线性顺序，其中 属性 表示线性顺序中的收盘价通常也收于 space 中（反之亦然） ).这在开发算法时可能会有用。
3) 看过OpenVDB。 OpenVDB 具有高度优化的空间索引结构，可遍历 'voxel'-cells 及其邻居。
4) 查看 PH-Tree（免责声明：这是我自己的项目）。 PH-Tree 有点像四叉树，但使用低级位操作来优化导航。它也是 Z-ordered/Morten-ordered（参见上面的 space 填充曲线）。您可以为每个点创建一个 window 查询，其中 returns 该矩形内的所有点。据我所知，PH-Tree 是这种操作最快的索引结构，尤其是当矩形中通常只有 9 个点时。如果您对代码感兴趣，V13 实现可能是最快的，但是 V16 应该更容易理解和修改。
我在我相当旧的台式机上尝试过，使用大约 1,000,000 个点，我每秒可以进行大约 200,000 window 次查询，因此找到每个点的所有邻居大约需要 5 秒。
如果您正在使用 Java，我的 spatial index collection 可能也有用。
我正在尝试找到适合特定问题的空间索引结构：使用联合查找数据结构，我想要 connect\associate 彼此在一定范围内的点。 我有很多要点，我正在尝试通过使用更好的空间索引来优化现有解决方案。
现在，我正在使用一个简单的 2D 网格索引我的点图中每个宽度 [阈值距离] 的正方形，并且我通过在网格中的相邻正方形中搜索点来寻找潜在的并集。
然后我计算到相邻单元格组合的平方欧几里得距离，我将其与我的平方阈值进行比较，然后我使用联合查找结构（使用路径压缩等进行优化）来构建点组。
这是该方法的一些说明。单个黑色点实际上表示属于网格单元格的一组点，向外的彩色箭头表示与外部点的实际距离比较。
（我也在检查属于相同单元格的潜在连接点）。
通过使用此模式，我确保在遍历网格单元时使用不与已测试内容重叠的适当 "neighbor cell" 模式，我不会进行两次距离比较。
问题是：这种方法甚至不够快，我正在尝试用可能更快的方法替换 "spatial grid index" 方法。
我已经研究过四叉树作为这个问题的合适空间索引，但我认为它不适合解决它（我没有看到任何执行重复 "neighbours" 检查的方法一个特定的单元格更有效地使用四叉树），但也许我错了。
因此，我正在寻找更好的 algorithm\data 结构来有效地索引我的点并查询它们的接近度。
提前致谢。
对此的标准方法是 "sweep and prune" 算法。按 X 坐标对所有点进行排序，然后遍历它们。正如您所做的那样，保持当前点的阈值距离（以 X 为单位）内的点的最低索引。该范围内的点是合并的候选点。然后你做同样的事情按 Y 排序。然后你只需要检查在 X 和 Y 扫描中出现的那些对的欧几里得距离。
请注意，使用当前的联合查找方法，如果附近有一堆 "bridging" 点，您最终可能会合并彼此相距很远的点。因此，您的基本方法——基于接近度合并点组——可能会导致任意数量的距离误差，而不仅仅是阈值距离。
我有一些意见：
1) 我认为你的问题相当于一个"spatial join"。空间连接采用两组几何图形，例如一组 R 矩形和一组 P 点，并为每个矩形查找所有点那个矩形。在您的情况下，R 将是每个点周围的矩形（边长 = 2 * 最大距离），而 P 是您的点集。搜索空间连接可能会给你一些有用的参考。
2) 您可能想看看 space 填充曲线。 Space 填充曲线为一组空间实体（点）创建线性顺序，其中 属性 表示线性顺序中的收盘价通常也收于 space 中（反之亦然） ).这在开发算法时可能会有用。
3) 看过OpenVDB。 OpenVDB 具有高度优化的空间索引结构，可遍历 'voxel'-cells 及其邻居。
4) 查看 PH-Tree（免责声明：这是我自己的项目）。 PH-Tree 有点像四叉树，但使用低级位操作来优化导航。它也是 Z-ordered/Morten-ordered（参见上面的 space 填充曲线）。您可以为每个点创建一个 window 查询，其中 returns 该矩形内的所有点。据我所知，PH-Tree 是这种操作最快的索引结构，尤其是当矩形中通常只有 9 个点时。如果您对代码感兴趣，V13 实现可能是最快的，但是 V16 应该更容易理解和修改。 我在我相当旧的台式机上尝试过，使用大约 1,000,000 个点，我每秒可以进行大约 200,000 window 次查询，因此找到每个点的所有邻居大约需要 5 秒。
如果您正在使用 Java，我的 spatial index collection 可能也有用。