Schnellster Weg, um den nächsten Punkt zu einem bestimmten Punkt in 3D, in Python zu finden

Question

So kann sagen, ich habe 10.000 Punkte in A und 10.000 Punkte in B und will für jeden Punkt B den nächsten Punkt in A erfahren.

Zur Zeit habe ich einfach Schleife durch jeden Punkt in B und A zu finden, die man im nächsten Abstand ist. dh.

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

Ich bin jedoch sicher, dass es einen schnelleren Weg, dies zu tun ... irgendwelche Ideen?

Answer 1

ich normalerweise verwenden kd-Baum in solchen Situationen.

Es gibt eine C ++ Implementierung gewickelt mit SWIG und mit biopython gebündelt, die leicht zu bedienen ist.

Answer 2

Sie könnten einige räumliche Suchstruktur verwenden. Eine einfache Möglichkeit ist ein Octree ; schicker gehören der BSP Baum .

Answer 3

Sie könnten numpy Rundfunk verwenden. Zum Beispiel:

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

wird 2,1,0 drucken, die die Zeilen in einem sind, die am nächsten zu den 1,2,3 Reihen von B sind jeweils.

Sie können aber verwenden Rundfunk:

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

Ich hoffe, das hilft.