jak znaleźć k-najbliższego sąsiada punktu w zestawie punktu

Question

Mam zestaw punktu (x, y) na płaszczyźnie 2d. Biorąc pod uwagę punkt (x0, y0) i liczbę k, jak znaleźć k-tego najbliższego sąsiada (x0, x0) w zestawie punktów. Szczegółowo, zestaw punktów jest reprezentowany przez dwie tablice: x i y. Punkt (x0, y0) jest podany przez indeks i0. Oznacza to x0 = x (i0) i y0 = y (i0).

Czy istnieje jakaś funkcja lub coś w Matlab pomaga mi ten problem. Jeśli Matlab nie ma takiej funkcji, możesz zaproponować inne skuteczne sposoby.

EDIT: Muszę obliczyć ten rodzaj odległości dla każdego punktu (x0, y0) w zbiorze. Rozmiar zestawu wynosi około 1000. Wartość k powinna wynosić około sqrt (1500). Najgorsze jest to, że robię to wiele razy. Przy każdej iteracji zestaw ulega zmianie i ponownie obliczam odległości. Tak więc czas pracy jest krytycznym problemem.

Answer 1

jeśli zrobisz to czek na wielu punktach może chcesz zbudować między pierwszym punktem

squareform(pdist([x y])) 

Answer 2

Jeśli masz przybornik statystyk, możesz użyć funkcji knnsearch.

Answer 3

algorytm brute force byłoby coś takiego:

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] 

Answer 4

Podejście brute force wygląda mniej więcej tak:

%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. 

Answer 5

Wolną i opensource VLFeat Toolbox zawiera implementację kd-drzewa, wśród innych przydatnych rzeczy.