Самый быстрый способ найти ближайшую точку к заданной точке в 3D, в Python

Question

Итак, скажем, у меня 10 000 точек в A и 10 000 точек в B и вы хотите узнать ближайшую точку в A для каждой точки B.

В настоящее время я просто просматриваю каждую точку в B и A, чтобы найти, какая из них ближе всего на расстоянии. то есть.

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 

Однако, я уверен, что существует более быстрый способ сделать это ... любые идеи?

Answer 1

Обычно я использую kd-tree в таких ситуациях.

Существует C++ implementation wrapped with SWIG and bundled with BioPython, который прост в использовании.

Answer 2

Вы можете использовать некоторую пространственную структуру поиска. Простой вариант: octree; более привлекательные - BSP tree.

Answer 3

Вы можете использовать бесчисленное вещание. Например,

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, которые являются строки в том, что наиболее близки к 1,2,3 рядами B, соответственно.

В противном случае, вы можете использовать вещание:

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

Я надеюсь, что помогает.