3

最も近い点のペアの問題は、計算幾何学でよく知られています。点のリスト（x、y）が与えられた場合、ユークリッド距離が最小の点のペアを見つけます。ここで、この問題のバリエーションを尋ねます。n個の点（xi、yi）（n + 1> i> 0）のリストを指定し、各点（xi、yi）に最も近いユークリッド距離を見つけて、すべてのポイントの平均最も近いユークリッド距離。私は力ずくの方法を知っています：

all_distance = [];
for i= 1 to n
    p = (xi,yi);
    dis = [];
    for j= 1 to n
      if j==i
          continue;
      else
          q = (xj,yj);
          pt_dis = distance(p,q);
      end 
      dis = [dis; pt_dis];
    end
    all_distance = [all_distance; nearest(dis)]

end
mean_distance = all_distance/n;

この方法は簡単ですが、計算に時間がかかります。この問題を解決するための簡単なアルゴリズムがあるかどうか疑問に思いました。ありがとう！

4

2 に答える 2

2

Delaunay 三角形分割は O( n log n ) 時間で計算でき、頂点ごとに、最も近い点は三角形分割の隣接する点の 1 つになります。O( n ) 個の合計エッジを調べることになるため、O( n log n ) の三角測量コストが支配的になります。

于 2012-07-17T16:32:42.367 に答える
2

この問題は通常、kd-treeまたはquadtreeによって最もよく解決されますが、手早く汚れたものが必要な場合は、何らかの方法でポイントをバケット化してみてください。つまり、ポイントがすべて (0,0) から (10,10) の範囲でほぼ均等に分布しているとします。この場合、100 個のバケットに対して、1 単位の正方形のバケットを作成できます。ここで、バケット内の最も近いポイントと、隣接する 8 つのバケットすべてを検索して、ポイントを処理します。1 単位以下のポイントが見つかった場合、それが最も近いポイントであることがわかります。より近いポイントは、隣接するバケットのいずれかにある必要はなく、1 単位以上離れている必要があることを意味します。この近くにポイントが見つからない場合は、すべてのポイントを確認するか、バケットの次のリングに展開する必要があります。

于 2012-07-17T16:20:00.937 に答える