我正在尝试找到一个适合特定问题的空间索引结构：使用union-find数据结构，我希望连接彼此特定范围内的\关联点。我有很多要点，我正在尝试通过使用更好的空间索引来优化现有解决方案。
现在，我正在使用一个简单的2D网格索引我的点图的宽度[阈值距离]的每个方格，我通过搜索网格中相邻方块中的点来寻找潜在的联合。
然后我计算到相邻单元组合的平方欧几里德距离，我将其与平方阈值进行比较，并使用union-find结构（使用路径压缩等优化）来构建点组。
以下是该方法的一些说明。单个黑点实际上表示属于网格单元格的点集合，而出局彩色箭头表示与外部点的实际距离比较。
（我也在检查属于同一个小区的潜在连接点）。
通过使用这种模式，我确保在迭代网格单元格时，通过使用与已经测试过的东西不重叠的适当“相邻单元格”模式，我没有做两次任何距离比较。
问题是：这种方法甚至还不够快，我试图用可能更快的东西替换“空间网格索引”方法。
我已经研究过四叉树作为这个问题的合适空间索引，但我认为它不适合解决它（我没有看到任何方法对一个特定的单元格执行重复的“邻居”检查更有效地使用四叉树），但也许我错了。
因此，我正在寻找一种更好的算法\数据结构来有效地索引我的点并查询它们的接近程度。
提前致谢。
我有一些意见：
1）我认为你的问题等同于“空间连接”。空间连接采用两组几何，例如一组矩形和一组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，我的spatial index collection也可能有用。
标准方法是“sweep and prune”算法。按X坐标对所有点进行排序，然后迭代它们。正如您所做的那样，保持在当前点的阈值距离（以X为单位）内的点的最低索引。该范围内的点是合并的候选者。然后，您按Y进行相同的排序。然后，您只需检查在X和Y扫描中出现的那些对的欧几里德距离。
请注意，使用您当前的union-find方法，如果有一堆附近的点“桥接”它们，您可以最终联合彼此相距很远的点。所以你的基本方法 - 基于接近度的联合点组合 - 可以引起任意数量的距离误差，而不仅仅是阈值距离。