快速算法查找平面上距离给定点最近的 x 个点

发布于 2025-01-01 08:28:38 字数 275 浏览 2 评论 0原文

我想找到一种快速算法来找到距离平面上给定点最近的 x 个点。

我们实际上处理的点并不多（1,000 到 100,000 之间），但我需要每个点的 x 个最接近的点。（其中 x 通常在 5 到 20 之间。）

我需要用 C# 编写它。

有关用例的更多背景信息：这些点是地图上的坐标。（我知道，这意味着我们并不完全在谈论平面，但我希望避免处理投影问题。）最后，有许多其他点靠近它们的点应显示为红色，没有太多点的点应显示为红色。靠近它们的点应显示为绿色。在这两个极端之间，点处于颜色渐变上。

原文

分享到QQ

分享到微博

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

发布评论

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

橘亓 2025-01-08 08:28:38

您需要的是适合组织平面上的点的数据结构。 KD树经常在这种情况下使用。请参阅 Wikipedia 上的 kd 树。

在这里，我找到了几何算法的一般描述

更新

我移植了一个KD 树到 C# 的 Java 实现。请参阅 RoboWiki 上的 User:Ojd/KD-Tree。您可以在那里下载代码，也可以下载CySoft.Collections.zip< /em> 直接从我的主页（仅下载，无文档）。

回复收藏 0 原文

梦途 2025-01-08 08:28:38

对于给定点（不是全部）并且由于点的数量不是极端，您可以计算距每个点的距离：（

var points = new List<Point>();
Point source = ...
....
var closestPoints = points.Where(point => point != source).
                           OrderBy(point => NotReallyDistanceButShouldDo(source, point)).
                           Take(20);

private double NotReallyDistanceButShouldDo(Point source, Point target)
{
   return Math.Pow(target.X - source.X, 2) + Math.Pow(target.Y - source.Y, 2);
}

我使用了 x = 20）

计算基于双精度，因此 fpu 应该能够在这里做一份体面的工作。
请注意，如果 Point 是类而不是结构，您可能会获得更好的性能。

For a given point (not all of them) and as the number of points is not extreme, you could calculate the distance from each point:

var points = new List<Point>();
Point source = ...
....
var closestPoints = points.Where(point => point != source).
                           OrderBy(point => NotReallyDistanceButShouldDo(source, point)).
                           Take(20);

private double NotReallyDistanceButShouldDo(Point source, Point target)
{
   return Math.Pow(target.X - source.X, 2) + Math.Pow(target.Y - source.Y, 2);
}

(I've used x = 20)

The calculation are based on doubles so the fpu should be able to do a decent job here.
Note that you might get better performance if Point is a class rather than a struct.

回复收藏 0 原文

溺ぐ爱和你が 2025-01-08 08:28:38

为了使这更加有效。假设距离为 k。获取 x 坐标在 xk 和 x+k 之间的所有点。类似地取yk 和y+k。所以你已经删除了所有多余的坐标。现在将距离设为 (x-x1)^2 + (y-y1)^2。在它们上创建一个包含 k 个元素的最小堆，如果 new point <<，则将它们添加到堆中。分钟（堆）。现在堆中已有 k 个最小元素。

回复收藏 0 原文