快速算法找到一个飞机上给定点的最近点 [英] Fast algorithm to find the x closest points to a given point on a plane

问题描述

我想找到一个快速算法，以便找到一个飞机上给定点的最近点。

I would like to find a fast algorithm in order to find the x closest points to a given point on a plane.

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

We are actually dealing with not too many points (between 1,000 and 100,000), but I need the x closest points for every of these points. (where x usually will be between 5 and 20.)

我需要在C＃中写。

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

A bit more context about the use case: These points are coordinates on a map. (I know, this means we are not exactly talking about a plane, but I hope to avoid dealing with projection issues.) In the end points that have many other points close to them should be displayed in red, points that have not too many points close to them should be displayed green. Between these two extremees the points are on a color gradient.

推荐答案

你需要的是一个适合于组织点的数据结构平面。在这种情况下常常使用K-D树。请参阅维基百科上的 kd tree 。

What you need is a data structure appropriate for organizing points in a plane. The K-D-Tree is often used in such situations. See k-d tree on Wikipedia.

在这里，我找到了几何算法

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

I ported a Java implementation of a KD-tree to C#. Please see User:Ojd/KD-Tree on RoboWiki. You can download the code there or you can download CySoft.Collections.zip directly from my homepage (only download, no docu).

这篇关于快速算法找到一个飞机上给定点的最近点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！