28

私は2次元配列を持っています:

MyArray = array([6588252.24, 1933573.3, 212.79, 0, 0],
                [6588253.79, 1933602.89, 212.66, 0, 0],
                 etc...)

最初の 2 つの要素MyArray[0]とMyArray[1]は、点のX座標とY座標です。

配列内のすべての要素について、半径X単位で最も近い 1 つの要素を返す最も簡単な方法を見つけたいと思います。これは 2D 空間にあると仮定しています。

この例で言いましょうX = 6。

すべての要素を他のすべての要素と比較することで問題を解決しましたが、リストが 22k ポイントの長さの場合、これには 15 分ほどかかります。最終的には、約 3000 万ポイントのリストでこれを実行したいと考えています。

Kd ツリーについて読んで、基本的な概念は理解しましたが、それらをスクリプト化する方法を理解するのに苦労しました。

4

1 に答える 1

35

scipy を提案してくれた John Vinyard に感謝します。いくつかの適切な調査とテストの後、この質問に対する解決策は次のとおりです。

前提条件: Numpy と SciPy をインストールする

  1. SciPy および Numpy モジュールをインポートする

  2. X 値と Y 値だけを含む 5 次元配列のコピーを作成します。

  3. のインスタンスをそのまま作成しますcKDTree。

    YourTreeName = scipy.spatial.cKDTree(YourArray, leafsize=100)
#Play with the leafsize to get the fastest result for your dataset

  4. cKDTree次のように、6 単位以内の最近傍を照会します。

    for item in YourArray:
    TheResult = YourTreeName.query(item, k=1, distance_upper_bound=6)

    の各項目についてYourArray、TheResultは 2 点間の距離のタプル、および の点の位置のインデックスになりますYourArray。

于 2012-10-26T00:07:55.420 に答える