10

したがって、A に 10,000 点、B に 10,000 点があり、B 点ごとに A で最も近い点を見つけたいとします。

現在、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

ただし、これを行うためのより高速な方法があると確信しています...何かアイデアはありますか?

4

3 に答える 3

4

私は通常、このような状況でkd ツリーを使用します。

SWIG でラップされ、使いやすいBioPython にバンドルされたC++ 実装があります。

于 2010-04-14T21:37:49.550 に答える
1

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行にそれぞれ最も近いaの行である2,1,0を出力します。

それ以外の場合は、ブロードキャストを使用できます。

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

それがお役に立てば幸いです。

于 2010-04-15T13:52:25.393 に答える
1

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

于 2010-04-14T21:33:21.240 に答える