Самый быстрый способ найти ближайшую точку к заданной точке в 3D, в Python
Итак, допустим, у меня есть 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
Тем не менее, я уверен, что есть более быстрый способ сделать это ... какие-нибудь идеи?
3 ответа
Я обычно использую kd-tree в таких ситуациях.
Существует реализация C ++, заключенная в SWIG и связанная с BioPython , которая проста в использовании.
Вы можете использовать некоторую структуру пространственного поиска. Простым вариантом является октодерево ; к более интересным относятся BSP-дерево .
Вы можете использовать широковещательную рассылку numpy. Например,
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])
Надеюсь, это поможет.