在Python中找到3D中与给定点最近点的最快方法

Question

假设我在A中有10,000个点，在B中也有10,000个点，我想找出B中的每一个点离A中哪个点最近。

现在，我的做法是把B中的每一个点都和A中的每一个点进行比较，看看哪个距离最近。也就是说，我会这样做：

B = [(.5, 1, 1), (1, .1, 1), (1, 1, .2)]
A = [(1, 1, .3), (1, 0, 1), (.4, 1, 1)]
C = {}
for bp in B:
   closestDist = -1
   for ap in A:
      dist = sum(((bp[0]-ap[0])**2, (bp[1]-ap[1])**2, (bp[2]-ap[2])**2))
      if(closestDist > dist or closestDist == -1):
         C[bp] = ap
         closestDist = dist
print C

不过，我相信还有更快的方法可以做到这一点……有没有什么好主意？

Answer 1

你可以使用numpy的广播功能。比如说，

from numpy import *
import numpy as np

a=array(A)
b=array(B)
#using looping
for i in b:
    print sum((a-i)**2,1).argmin()

这段代码会输出2,1,0，这些数字代表在a中与B的1,2,3行最接近的行。

另外，你也可以使用广播：

z = sum((a[:,:, np.newaxis] - b)**2,1)
z.argmin(1) # gives array([2, 1, 0])

希望这些对你有帮助。

Answer 2

你可以使用一些空间查找结构。一个简单的选择是八叉树；更高级的选项包括二叉空间划分树。

Answer 3

在这种情况下，我通常会使用一个叫做 kd-tree 的数据结构。

有一个 用C++写的实现，经过SWIG处理，并和BioPython打包在一起，使用起来非常简单。