2

2 つのリストがあります。最初のリストは座標ペアリストです

[[x1, y1]
 [x2, y2]
 ...
 [xn, yn]]

2 番目のリストは、各ペアに関連付けられた値を含む座標ペア リストです。

[[x1',y1',v1']
 [x2',y2',v2']
 ...
 [xn',yn',vn']]

最初のリストの各ペア (x,y) に対して 2 番目のリストで最も近い (x',y') を見つけ、値 v' を (x,y) にマップします。

私の現在の解決策は、両方のリストをループして、可能なすべての座標ペア間のユークリッド距離を計算し、最小距離にマップすることです。しかし、元の 2 番目のリストには 300 万のエントリがあります。これを達成するためのより効率的な方法はありますか？ありがとう。

4

2 に答える 2

1

2 番目のリストの座標を丸めてみます。座標の場合、これにより多くの小さなクラスターが得られます。丸められた座標を dict のキーとして使用し、座標 + 値のリストを値として使用します。

for x,y in first_list:
    x_,y_ = round(x,y)
    l = d[(x_,y_)]
    ... find closest point in l...

このアルゴリズムでは、いくつかの点を確認するだけで済みます。

リストが空の場合は、より緩やかな丸めを使用して再試行できます。

于 2013-10-09T08:30:42.463 に答える
1

このエリアにある 2 番目のリストのポイントに「エリア」をマッピングして、空間マップを作成できます。たとえば、x-min、x-max、y-min、y-max の 4 タプルをポイントにマッピングできます。このような：

{(0, 10, 0, 10): [(2, 4, 5), (5, 1, 12), ...], (0, 10, 10, 20): [(4, 14, -1), ...] }

これで、最初のリストからポイントに対応するエリアを選択できます。たとえば、ポイントが の場合、(24, 13)エリア に対応するリストを選択します(20, 30, 10, 20)。もちろん、これらの領域のサイズは、ポイントの分布によって異なります。

この領域にポイントがある場合は、元のポイントまでの距離が最も小さいポイントを選択します。それ以外の場合は、そのエリアの周囲の 8 つのエリアの次の「レイヤー」を調べます。ポイントが見つかったら、元のポイントにより近いレイヤーにポイントがまだ存在する可能性があるため、もう 1 つのレイヤーを展開する必要があります。(図を参照)

ここに画像の説明を入力

ここで、赤い点は最初のリストのポイントであり、青い点は 2 番目のリストのポイントです。ボックスは、マップ内のエリアに対応しています。元の点に直接対応する領域には 2 つのドットがありますが、次の「レイヤー」にはより近い点がありますが、それ以上検索する必要はありません。

于 2013-10-09T08:34:43.797 に答える