如何找到一组点中第k个点的最近邻点

我在2d平面上有一组点（x，y）。给定一个点（x0，y0）和数k，如何找到点集中（x0，x0）的第k个最近邻点。详细地说，点集由两个数组表示：x和y。点（x0，y0）由索引i0给出。它意味着x0 = x（i0）和y0 = y（i0）。如何找到一组点中第k个点的最近邻点

是否有任何功能或Matlab的东西可以帮助我解决这个问题。如果Matlab没有这样的功能，你能否提出其他有效的方法。

编辑：我必须为集合中的每个点（x0，y0）计算这种距离。该集合的大小约为1000. k的值应大约为sqrt（1500）。最糟糕的是我做了很多次。在每次迭代中，设置发生变化，然后再次计算距离。所以，运行时间是一个关键问题。

来源

2012-02-22 James Do

，如果你会做这种检查对于很多点，你可能要构建一个点间距离表第一

squareform(pdist([x y]))

来源

2012-02-23 01:47:43 zamazalotta

是的。我会为这组中的每一点做到这一点。所以，某种距离表有助于节省运行时间。我将发现squareform函数在我的问题中如何工作。非常感谢你。 – 2012-02-23 03:34:39

其实函数是pdist，squareform只是使pdist的向量输出 – zamazalotta 2012-02-23 06:51:19

出一个方阵，谢谢zamazalotta。我知道了。 – 2012-02-23 07:24:55

如果您有统计工具箱，则可以使用功能knnsearch。

来源

2012-02-22 21:57:39 3lectrologos

knnsearch似乎是一个解决办法，但我不知道如何knnsearch应用到我的问题确切。我会找到它。无论如何，你能给我更多关于使用knnsearch的方式的细节。非常感谢你。 – 2012-02-23 03:30:37

你看过Matlab的帮助（添加到我的答案上面的链接）？ – 3lectrologos 2012-02-23 16:58:21

我阅读了关于knnsearch的在线文档，但对我来说有点复杂，而且我没有太多时间来理解和使用它。我尝试了更简单的方法。它需要更多时间跑步，但我会先尝试这种方法。感谢您的帮助。 – 2012-02-23 17:37:59

蛮力算法是这样的：

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-22 21:59:32 ardnew

感谢您的帮助！ – 2012-02-23 03:27:03

蛮力方法看起来是这样的：

%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-22 22:00:28 Pursuit

不应该删除元素本身？考虑一下案例k = 1 – 2012-02-22 22:26:19

好点。我通常不喜欢像这样改变匹配向量的大小。也许给最终索引添加一个'+1'。编辑：虽然如果有一个点与初始点相同，那么会留下一个空白。如果你想保证答案是一个不同的观点，即使有些观点可能是平等的，那么也需要做更多的工作。 – Pursuit 2012-02-23 00:50:49

@追求它也没有意义也删除相同的点。如果你有5个相同的点，你搜索的点，第3个最远的距离应该是0 – ardnew 2012-02-23 02:20:49

自由和开源VLFeat工具箱包含一个kd树实现，以及其他有用的东西。

来源

2012-02-22 22:34:56 Maurits

非常感谢。我会找到它是否可以帮助。 – 2012-02-23 03:37:14

如何找到一组点中第k个点的最近邻点

回答

相关问题