7

2次元平面上に点 (x,y) のセットがあります。点 (x0,y0) と数値 k が与えられた場合、点セット内の (x0,x0) の k 番目の最近傍点を見つける方法。詳細には、点集合は x と y の 2 つの配列で表されます。点 (x0,y0) はインデックス i0 によって与えられます。x0=x(i0) と y0=y(i0) という意味です。

Matlab には、この問題に役立つ関数や何かがありますか。Matlab にそのような機能がない場合、他に有効な方法を教えてください。

編集: セット内のすべてのポイント (x0、y0) について、この種の距離を計算する必要があります。セットのサイズは約 1000 です。k の値は約 sqrt(1500) である必要があります。最悪のことは、これを何度も行うことです。反復ごとにセットが変更され、距離が再度計算されます。したがって、実行時間は重大な問題です。

4

5 に答える 5

6

多くのポイントに対してこのチェックを行う場合は、最初にポイント間距離テーブルを作成することをお勧めします

squareform(pdist([x y]))
于 2012-02-23T01:47:43.283 に答える
4

統計ツールボックスがある場合は、関数knnsearchを使用できます。

于 2012-02-22T21:57:39.687 に答える
2

フリーでオープンソースのVLFeatツールボックスには、kd-tree 実装などの便利なものが含まれています。

于 2012-02-22T22:34:56.227 に答える
2

ブルート フォース アルゴリズムは次のようになります。

array x[n] = ()
array y[n] = () 
array d[n] = ()

... populate x and y arrays with your n points ...

/* step over each point and calculate its distance from (x0, y0) */
for i = 1 to n
do
  d[i] = distance((x0, y0), (x[i], y[i])
end 

/* sort the distances in increasing order */
sort(d)

/* the k'th element of d, is the k'th nearest point to (x0, y0) */
return d[k]
于 2012-02-22T21:59:32.893 に答える
2

ブルート フォース アプローチは次のようになります。

%Create some points
n = 10;
x = randn(n,1);
y = randn(n,1);

%Choose x0
ix0 = randi(n);

%Get distances
d = sqrt(...
    (x - x(ix0) ).^2 + ...
    (y - y(ix0) ).^2 );

%Sort distances
[sorted_Dstances, ixSort] = sort(d);

%Get kth point
k = 3;
kth = [x(ixSort(k+1)); y(ixSort(k+1))]; %+1 since the first element will always be the x0 element.
于 2012-02-22T22:00:28.463 に答える