[解決済み] x座標とy座標のnumpy配列から最近接点のインデックスを見つける

質問

x_arrayはx方向の位置情報、y_arrayはy方向の位置情報を含んでいます。

私はx,y点の長いリストを持っています。

リスト内の各点について、私はその点に最も近い場所（配列で指定された）の配列インデックスを見つける必要があります。

私はこの質問に基づいて、動作するいくつかのコードを素朴に作成しました。 numpyの配列で最も近い値を見つける

すなわち

import time
import numpy

def find_index_of_nearest_xy(y_array, x_array, y_point, x_point):
    distance = (y_array-y_point)**2 + (x_array-x_point)**2
    idy,idx = numpy.where(distance==distance.min())
    return idy[0],idx[0]

def do_all(y_array, x_array, points):
    store = []
    for i in xrange(points.shape[1]):
        store.append(find_index_of_nearest_xy(y_array,x_array,points[0,i],points[1,i]))
    return store


# Create some dummy data
y_array = numpy.random.random(10000).reshape(100,100)
x_array = numpy.random.random(10000).reshape(100,100)

points = numpy.random.random(10000).reshape(2,5000)

# Time how long it takes to run
start = time.time()
results = do_all(y_array, x_array, points)
end = time.time()
print 'Completed in: ',end-start

私はこれを大きなデータセットに対して行っており、本当にそれを少しスピードアップしたいと思います。 誰かこれを最適化できますか？

ありがとうございます。

UPDATE: @silvado および @justin の提案に従った解決策 (以下)

# Shoe-horn existing data for entry into KDTree routines
combined_x_y_arrays = numpy.dstack([y_array.ravel(),x_array.ravel()])[0]
points_list = list(points.transpose())


def do_kdtree(combined_x_y_arrays,points):
    mytree = scipy.spatial.cKDTree(combined_x_y_arrays)
    dist, indexes = mytree.query(points)
    return indexes

start = time.time()
results2 = do_kdtree(combined_x_y_arrays,points_list)
end = time.time()
print 'Completed in: ',end-start

このコードにより、私のコード（100x100の行列から5000点を探す）は100倍高速化されました。興味深いことに scipy.spatial.KDTree (の代わりに scipy.spatial.cKDTree。 の代わりに）私の素朴な解決策と同等の時間を与えたので、cKDTreeバージョンを使用することは間違いなく価値があります...。

どのように解決するのか？

scipy.spatial には、k-d tree の実装もあります。 scipy.spatial.KDTree .

アプローチとしては、まず点データを使ってk-d木を構築するのが一般的です。その計算量はN log Nのオーダーで、Nはデータポイントの数です。レンジクエリーと最近傍探索はlog Nの複雑さで実行される。これは、単にすべてのポイントを循環させる (計算量 N) よりもはるかに効率的です。

したがって、範囲検索や最近傍検索を繰り返す場合は、k-dツリーを使用することを強く推奨します。