在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

在这种情况下我通常使用kd 树。

有一个用 SWIG 包装并与 BioPython 捆绑在一起的 C++ 实现，易于使用。