Maneira mais rápida de encontrar o ponto mais próximo de um determinado ponto em 3D, em Python

Question

Então, digamos que eu tenho 10.000 pontos em A e 10.000 pontos em B e queira descobrir o ponto mais próximo de A para cada ponto B.

Atualmente, eu simplesmente percorro todos os pontos em B e A para descobrir qual é o mais próximo a distância. ou seja.

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

No entanto, tenho certeza de que há uma maneira mais rápida de fazer isso ... alguma idéia?

Answer 1

Eu normalmente uso um KD-Tree em tais situações.

Existe um Implementação de C ++ enrolada com SWIG e empacotada com Biopython Isso é fácil de usar.

Answer 2

Você pode usar alguma estrutura de pesquisa espacial. Uma opção simples é um Octree; os mais sofisticados incluem o Árvore BSP.

Answer 3

Você pode usar a transmissão Numpy. Por exemplo,

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 são as linhas em A que estão mais próximas das 1,2,3 linhas de B, respectivamente.

Caso contrário, você pode usar a transmissão:

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

Espero que isso ajude.