我想找到一个快速算法，以便找到在x最接近的点在一个平面上指定的点。

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

我们实际上有没有太多分处理（1000和10万之间），但我需要的X最近的点，每这些点。 （其中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＃写吧。

有关用例多一点背景：这点是地图上的坐标。 （我知道，这意味着我们不正是在谈论一个平面上，但我希望避免处理投影的问题。）在终点有接近他们的其他许多点应显示为红色，有没有太多分接近他们点应显示为绿色。这两个extremees之间的点上的颜色渐变。

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树。

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.

在这里，我发现几何算法的一般描述

我移植的Java实现一个KD树的C＃。请参阅用户：Ojd / KD-树的上RoboWiki。您也可以下载code有或者你可以下载的 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).