10

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

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

我需要用 C# 编写它。

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

4

4 回答 4

14

你需要的是一个适合在平面上组织点的数据结构。KD-Tree 通常用于这种情况。参见Wikipedia 上的kd 树。

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

更新

我将 KD-tree 的 Java 实现移植到 C#。请参阅RoboWiki 上的用户：Ojd/KD-Tree。您可以在那里下载代码，也可以直接从我的主页下载CySoft.Collections.zip（仅下载，无文档）。

于 2012-02-02T14:42:38.367 回答
11

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

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 是类而不是结构，您可能会获得更好的性能。

于 2012-02-02T14:20:53.703 回答
1

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

于 2012-02-02T14:29:05.840 回答
1

您需要创建一个距离函数，然后计算每个点的距离并对结果进行排序，然后取第一个 x。

如果结果必须 100% 准确，那么您可以使用标准距离函数：

d = SQRT((x2 - x1)^2 + (y2 - y1)^2)

于 2012-02-02T14:21:53.830 回答