寻找与平面上给定点最近的x个点的快速算法
寻找与平面上给定点最近的x个点的快速算法
提问于 2012-02-02 22:11:54
我想找到一种快速算法，以便找到与平面上给定点最近的x个点。
我们实际上处理的点不是太多(在1,000到100,000之间)，但我需要为这些点中的每个点找到x个最近的点。(其中x通常介于5和20之间。)
我需要用C#编写它。
更多关于用例的上下文:这些点是地图上的坐标。(我知道，这意味着我们并不是在谈论飞机，但我希望避免处理投影问题。)最后，具有许多其他点的端点应显示为红色，靠近点不太多的点应显示为绿色。在这两个极端之间，这些点位于颜色渐变上。
回答 4
Stack Overflow用户
回答已采纳
发布于 2012-02-02 22:42:38
您需要的是一个适合在平面中组织点的数据结构。K-D-Tree通常用在这样的情况下。请参阅维基百科上的k-d tree。
在这里，我找到了对Geometric Algorithms的一般描述
更新
我将KD-tree的Java实现移植到了C#。请参阅RoboWiki上的User:Ojd/KD-Tree。您可以在那里下载代码，也可以直接从我的homepage下载 (只下载，不下载文档)。
Stack Overflow用户
发布于 2012-02-02 22:20:54
对于给定的点(不是所有点)，由于点的数量不是极值，您可以计算到每个点的距离：
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是一个类而不是结构，您可能会获得更好的性能。
Stack Overflow用户
发布于 2012-02-02 22:21:54
您需要创建一个距离函数，然后计算每个点的距离并对结果进行排序，然后取第一个x。
如果结果必须100%准确，则可以使用标准距离函数：
D= SQRT((x2 - x1)^2 + (y2 - y1)^2)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/9113780
复制相关文章
相似问题
腾讯云开发者
