7

我在二维平面上有一组点 (x,y)。给定一个点 (x0,y0) 和数字 k，如何在点集中找到 (x0,x0) 的第 k 个最近邻。具体来说，点集由两个数组表示：x 和 y。点 (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

蛮力算法将是这样的：

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 回答
2

免费和开源的VLFeat工具箱包含一个 kd-tree 实现，以及其他有用的东西。

于 2012-02-22T22:34:56.227 回答