c# - 快速算法找到 x 最接近平面上给定点的点

Question

我想找到一种快速算法，以便找到与平面上给定点最近的 x 个点。

我们实际上处理的点并不多(在 1,000 到 100,000 之间)，但我需要这些点中的每一个点的 x 个最近点。 (其中 x 通常介于 5 和 20 之间。)

我需要用 C# 编写它。

关于用例的更多上下文:这些点是 map 上的坐标。 (我知道，这意味着我们并不是在谈论一个平面，但我希望避免处理投影问题。)在端点附近有很多其他点应该显示为红色，没有太多的点靠近它们的点应显示为绿色。在这两个极端之间，点在颜色渐变上。

Answer 1

您需要的是适合组织平面中点的数据结构。 K-D-Tree 经常用于这种情况。参见 k-d tree在维基百科上。

在这里，我找到了 Geometric Algorithms 的一般描述

---

更新

我将 KD 树的 Java 实现移植到 C#。请看User:Ojd/KD-Tree在 RoboWiki 上。您可以在那里下载代码，也可以下载 CySoft.Collections.zip 直接来 self 的 homepage (仅下载，无文档)。