在Python中寻找给定点在三维空间中最接近的点的最快方法

Question

假设我有A中的10,000个点和B中的10,000个点，我想找出每个B点最接近的A点。

目前，我的方法是循环遍历A和B中的每个点以找到距离最近的点。例如：

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

然而，我相信有一种更快的方法来做这件事... 有什么想法吗？

- Saebin

Answer 1

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

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

- awesomo

---

我目前使用scipy的kd-tree。 - Saebin

Answer 2

你可以使用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])

希望这能有所帮助。

- reckoner

Answer 3

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

- Thomas