Il modo più veloce per trovare il punto più vicino a un punto specifico in 3D, in Python

Question

Quindi diciamo 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.

Attualmente, faccio semplicemente un giro di ogni punto in B e A per trovare quale è il più vicino in 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

In genere utilizzo uno kd-tree in tali situazioni.

C'è un C++ implementation wrapped with SWIG and bundled with BioPython che è facile da usare.

Answer 2

È possibile utilizzare una struttura di ricerca spaziale. Un'opzione semplice è una octree; quelli più fantasiosi includono lo BSP tree.

Answer 3

È possibile 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 che sono le righe di una più vicine 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.