Der schnellste Weg, den nächsten Punkt zu einem bestimmten Punkt in 3D zu finden, in Python

Question

Also sagen wir, ich habe 10.000 Punkte in A und 10.000 Punkte in B und möchte den nächsten Punkt in A für jeden B Punkt herausfinden.

Momentan durchsuche ich einfach jeden Punkt in B und A, um herauszufinden, welcher in der Entfernung am nächsten 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 

Aber ich bin sicher, dass es ein schnellerer Weg, dies ... irgendwelche Ideen zu tun?

Answer 1

Ich verwende normalerweise eine kd-tree in solchen Situationen.

Es gibt eine C++ implementation wrapped with SWIG and bundled with BioPython, die einfach zu bedienen ist.

Answer 2

Sie könnten eine räumliche Suchstruktur verwenden. Eine einfache Option ist ein octree; Züchter gehören die BSP tree.

Answer 3

Sie könnten numpy Broadcasting verwenden. Zum Beispiel wird

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

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 Rundfunk verwenden:

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

Ich hoffe, das hilft.