快速算法，找到平面上给定点的x个最近点
我想找到一个快速算法，以便找到平面上给定点的x个最近点。
我们实际上处理的点数不多（1000到100,000之间），但我需要每个点的x最近点。 （其中x通常在5到20之间。）
我需要用C＃编写它。
关于用例的更多上下文：这些点是地图上的坐标。 （我知道，这意味着我们并不是在谈论一架飞机，但我希望避免处理投影问题。）最后，有许多其他点靠近它们的点应该用红色显示，点数不要太多靠近它们的点应显示为绿色。 在这两个极端之间，点是颜色梯度。
您需要的是适合于在平面中组织点的数据结构。 KD-Tree经常用于这种情况。 请参阅维基百科上的kd树 。
在这里，我找到了几何算法的一般描述
UPDATE
我将KD树的Java实现移植到C＃。 请在RoboWiki上查看用户：Ojd / KD-Tree 。 您可以在那里下载代码，也可以直接从我的主页下载CySoft.Collections.zip （只下载，没有文档）。
对于给定点（不是全部）并且由于点数不是极端，您可以计算每个点的距离：
var points = new List(); 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是类而不是结构，则可能会获得更好的性能。
您需要创建一个距离函数，然后计算每个点的距离并对结果进行排序，并获取第一个x。
如果结果必须100％准确，那么您可以使用标准距离函数：
d = SQRT（（x2-x1）^ 2 +（y2-y1）^ 2）
为了使这更有效。 让我们说距离是k。 获取xk和x + k之间x坐标的所有点。 同样地，取yk和y + k。 所以你已经删除了所有多余的坐标。 现在使距离乘以（x-x1）^ 2 +（y-y1）^ 2。 在它们上创建一小部分k元素，如果新点