Le moyen le plus rapide de trouver le point le plus proche d'un point donné en 3D, en Python

Question

Disons que j'ai 10 000 points dans A et 10 000 points dans B et que je veux trouver le point le plus proche de A pour chaque point B. Actuellement, je parcours simplement chaque point de B et A pour trouver lequel est le plus proche en distance. c'est à 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 

Cependant, je suis sûr qu'il ya un moyen plus rapide de le faire ... des idées?

Answer 1

J'utilise généralement un kd-tree dans de telles situations. Il y a un C++ implementation wrapped with SWIG and bundled with BioPython facile à utiliser.

Answer 2

Vous pouvez utiliser une structure de recherche spatiale. Une option simple est un octree; Les colombophiles incluent le BSP tree.

Answer 3

Vous pouvez utiliser la diffusion numérique. Par exemple,

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

imprimera 2,1,0 qui sont les lignes d'une qui sont les plus proches des lignes de 1,2,3 B, respectivement.

Sinon, vous pouvez utiliser la diffusion:

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

J'espère que cela aide.