как найти k-го ближайшего соседа точки в наборе точек

Question

У меня есть набор точек (x, y) на 2d плоскости.Учитывая точку (x0, y0) и число k, как найти k-го ближайшего соседа (x0, x0) в наборе точек.Подробно, набор точек представлен двумя массивами: x и y.Точка (x0, y0) задается индексом i0.Это означает, что x0 = x (i0) и y0 = y (i0).

Есть ли какая-либо функция или что-то в Matlab, помогает мне решить эту проблему.Если у Matlab нет такой функции, можете ли вы предложить какие-либо другие эффективные способы.

РЕДАКТИРОВАТЬ : Я должен рассчитать расстояние такого типа для каждой точки (x0, y0) внабор.Размер набора составляет около 1000. Значение k должно быть около sqrt (1500).Хуже всего то, что я делаю это много раз.На каждой итерации набор меняется, и я снова вычисляю расстояния.Таким образом, время работы является критической проблемой.

Answer 1

если вы выполните эту проверку для многих точек, вы можете сначала построить таблицу расстояний между точками

squareform(pdist([x y]))

Answer 2

Если у вас есть набор инструментов статистики, вы можете использовать функцию knnsearch .

Answer 3

Свободный и открытый исходный код VLFeat набор инструментов содержит реализацию дерева kd, среди других полезных вещей.

Answer 4

Метод грубой силы выглядит примерно так:

%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

Алгоритм грубой силы будет выглядеть примерно так:

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]