我有两个随机排序的2d点的大的numpy数组，假设它们是A和B。我需要做的是找到两个数组之间的“匹配数”，其中match是A中的点（称其为A'）在给定的半径R内，且在B中有一个点（称其为B'）。这意味着A中的每个点都必须与B中的1个点匹配，或者不匹配。在两个数组之间返回匹配项的列表索引也很好，但是这不是必需的。由于此半径R中可以有许多点，因此最好在B中找到最靠近A'的点，然后检查它是否在半径R之内。这可以通过距离公式dx^2 + dy^2进行简单测试。显然，存在遍历两个数组的蛮力O（n ^ 2）解决方案，但是我需要更快的东西，希望是O（n log n）。
我已经看到，Voronoi图可以用于这样的问题，但是我不确定如何实现。我不熟悉Voronoi图，所以我用scipy.spatial.Voronoi生成了它。使用这些图表是否有针对此问题的快速算法，或者还有其他算法？
您可能想要的是KDTrees（在高维中速度很慢，但对于您的问题应该非常快。Python实现甚至实现了半径限制：https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.KDTree.html#scipy.spatial.KDTree