我有两个随机排序的 2d 点的大型 numpy 数组，假设它们是 A 和 B。我需要做的是找到两个数组之间“匹配”的数量，其中匹配是 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。是否有使用这些图来解决此问题的快速算法，或者还有其他算法吗？