C# 实现 Fortune's Voronoi 算法
使用 C# 实现 Fortune 算法来计算二维 Voronoi 图。
注意：代码已迁移至 Google Code！
介绍
给定一组二维向量（或数据点），Voronoi 图是将这些点划分为若干区域，其中一个区域内的所有点都比任何其他数据点更接近该区域内包含的数据点。我在这里不进行任何演示，但如果您想了解更多关于 Voronoi 图的信息，请查看 这里。
Voronoi 图的应用非常广泛。对于许多优化问题非常有用（在大多数情况下，可以从 Voronoi 图轻松推导出的 Delaunay 三角剖分在那里使用），甚至可以用于从位图中计算拓扑地图。
[这篇文章是为极客准备的。在编写这个东西之后，我希望它能帮助所有正在寻找这种算法的人，并且使用一种文明的语言（或者只是不想使用 Fortune 最初的 C 实现）。]
1987 年，Steve Fortune 描述了一种使用扫描线结合二叉树来计算此类图的算法。关于该算法的 PowerPoint 解释（我用来实现它的那个）可以在 这里找到。请注意，我没有使用链接的数据结构来表示图 - 我认为在 ArrayList 和 HashSet 时代，这是一种不必要的困难。
实现
数据点由我自己的 Vector 类表示。它比这里需要的能做更多（但没有理由在引入它之前将其剥离），但我不会在这里解释它。最重要的是，虽然使用 double 类型，Vector 类会自动将值四舍五入到 10 位数字（或 Vector.Precision 字段中设置的任何位数）。是的，不幸的是，如果您想比较 double 类型，这非常重要。
VoronoiGraph 是一个类，它只包含一个 HashSet 的顶点（作为二维向量）和一个 HashSet 的 VoronoiEdge - 每个顶点都引用左侧和右侧的数据点以及（当然）限定该边的两个顶点。如果边是（部分或完全）无界的，则使用向量 Fortune.VVUnknown。
BinaryPriorityQueue 用于扫描线事件队列。
用法
该算法本身（Fortune.ComputeVoronoiGraph(IEnumerable)）接受任何仅包含二维向量的 IEnumerable。它将返回一个 VoronoiGraph。该算法的复杂度为 O(n ld(n))，在我的机器（2GHz）上大约有 10 微秒的因子。