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

发布于 2025-01-08 00:08:39 字数 340 浏览 1 评论 0原文

我在二维平面上有一组点 (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)。最糟糕的是我多次这样做。在每次迭代中，集合都会发生变化，我会再次计算距离。因此，运行时间是一个关键问题。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

沧桑㈠ 2025-01-15 00:08:39

如果您要对许多点进行此检查，您可能需要首先构建一个点间距离表

squareform(pdist([x y]))

if you will do this check for many points you might want to construct a inter-point distance table first

squareform(pdist([x y]))

回复收藏 0 原文

椒妓 2025-01-15 00:08:39

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

回复收藏 0 原文

月下凄凉 2025-01-15 00:08:39

暴力算法将是这样的：

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]

A brute force algorithm would be something like this:

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]

回复收藏 0 原文

还如梦归 2025-01-15 00:08:39

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

回复收藏 0 原文

甜妞爱困 2025-01-15 00:08:39

蛮力方法看起来像这样：

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

The brute force approach looks something like this:

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

回复收藏 0 原文

~没有更多了~