modo più veloce per trovare il punto più vicino ad un dato punto in 3D, in Python

Question

Quindi, consente di dire che ho 10.000 punti in A e 10.000 punti in B e voglio scoprire il punto più vicino in A per ogni punto B.

Al momento, ho semplicemente scorrere ogni punto B e A per trovare che uno è più vicino della distanza. vale a dire.

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

Tuttavia, sono sicuro che ci sia un modo più veloce per fare questo ... tutte le idee?

Answer 1

Io di solito uso un kd-tree in tali situazioni.

C'è un C ++ implementazione avvolto con SWIG e in bundle con Biopython che è facile da utilizzare.

Answer 2

Si potrebbe usare un po 'di struttura di ricerca spaziale. Un'opzione semplice è un octree ; quelli più elaborati sono il albero BSP .

Answer 3

Si potrebbe utilizzare la trasmissione NumPy. Ad esempio,

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()

stamperà 2,1,0 quali sono le righe di una che più si avvicinano alle 1,2,3 righe di B, rispettivamente.

In caso contrario, è possibile utilizzare la trasmissione:

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

Mi auguro che aiuta.