一千萬個為什麽

搜索

在Python中找到3D中給定點的最近點的最快方法

因此,假設我在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

但是,我確信有更快的方法來做到這一點...任何想法?

最佳答案

在這種情況下,我通常使用 kd-tree

There is a C++ implementation wrapped with SWIG and bundled with BioPython that's easy to use.

轉載註明原文: 在Python中找到3D中給定點的最近點的最快方法