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

Question

Допустим, у меня есть 10000 точек в точке A и 10000 точек в точке 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-дерево в таких ситуациях.

Существует реализация C ++, обернутая SWIG и связанная с BioPython , которую легко использовать.

Answer 2

Вы можете использовать цифровую трансляцию.Например,

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

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

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

Надеюсь, это поможет.

Answer 3

Вы можете использовать некоторую пространственную структуру поиска. Простая опция - октри ; Из более интересных - BSP tree .