Pythonで、3Dで与えられた点に最も近い点を見つけるための最速の方法

Question

だから私はBにAで10,000ポイント10,000ポイントを持っているし、すべてのBポイントのAにおける最も近い点を知りたいと言うことができます。

BとA内のすべてのポイントを介して

現在、私は単にループ1の距離で最も近いである見つけます。すなわちます。

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

あなたは、いくつかの空間的なルックアップ構造を使用することができます。簡単なオプションは、オクのです。手の込んだものは BSPツリーを含めます。

Answer 3

あなたは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()

は、それぞれ、Bの1,2,3行に最も近いの行である2,1,0を表示します。

そうしないと、放送を使用することができます

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

私はそれが役に立てば幸います。