La forma más rápida de encontrar el punto más cercano a un punto dado en 3D, en Python

Question

Digamos que tengo 10.000 puntos en A y 10.000 puntos en B y quiero encontrar el punto más cercano en A para cada punto B.

Actualmente, simplemente recorro cada punto en B y A para encontrar cuál está más cerca en distancia. es decir.

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 

Sin embargo, estoy seguro de que hay una manera más rápida de hacer esto ... alguna idea?

Answer 1

Normalmente uso un kd-tree en tales situaciones.

Hay un C++ implementation wrapped with SWIG and bundled with BioPython que es fácil de usar.

Answer 2

Puede usar alguna estructura de búsqueda espacial. Una opción simple es un octree; los más lujosos incluyen el BSP tree.

Answer 3

Podría usar la difusión numpy. Por ejemplo,

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

imprimirá 2,1,0 que son las filas de una que están más cerca de los 1,2,3 filas de B, respectivamente.

De lo contrario, se puede utilizar la difusión:

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

Espero que ayude.