快速算法,找到平面上给定点的x个最近点

Question

我想找到一个快速算法,以便找到平面上给定点的x个最近点.

我们实际上处理的点数并不多(1000到100,000之间),但我需要每个点的x最近点.(其中x通常在5到20之间.)

我需要用C#编写它.

关于用例的更多上下文:这些点是地图上的坐标.(我知道,这意味着我们并不是在谈论一架飞机,但我希望避免处理投影问题.)最后有许多其他点靠近它们的点应该用红色显示,这些点没有太多靠近它们的点应显示为绿色.在这两个极端之间,点是颜色梯度.

Answer 1

您需要的是适合于在平面中组织点的数据结构.KD-Tree经常用于这种情况.请参阅维基百科上的kd树.

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

UPDATE

我将KD树的Java实现移植到C#.请在RoboWiki上查看用户:Ojd/KD-Tree.您可以在那里下载代码,也可以直接从我的主页下载CySoft.Collections.zip(只下载,没有文档).

Answer 2

对于给定点(并非所有点)并且由于点数不是极端,您可以计算每个点的距离:

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是类而不是结构,则可能会获得更好的性能.