一个 Swift 框架，使用 Fortune 算法计算 Voronoi 图。
使用 VoronoiDiagram 类来计算 Voronoi 图的单元格。Voronoi 图是平分给定点之间连线的边。单元格内的每个点都比任何其他 Voronoi 点更接近该单元格的 Voronoi 点。位于两个单元格边缘上的点与两个 Voronoi 点等距。
Fortune 算法是一种在 O(n log(n)) 时间内解决 Voronoi 图的方法。 它只需要在每个 Voronoi 点和三个 Voronoi 点可能形成的圆上处理一个事件（这发生在 O(n) 时间内），并且还需要在每个站点事件中搜索二叉树（这发生在 O(log(n)) 时间内）。
Fortune 算法使用沙滩线（一条由给定 x 坐标处抛物线的最小值形成的 piecewise 曲线）和扫描线（一条对应于抛物线准线的水平线）。 每个 Voronoi 点对应于抛物线的焦点，扫描线对应于准线。
抛物线可以定义为焦点（一个点）和准线（一条线）。 抛物线上任何点与其焦点之间的距离等于同一点与其准线之间的距离（假设准线是一条水平线，这只是 y 坐标的差值）。 例如，假设我们的抛物线的焦点为 (x, y) = (0, 1)，准线为 y = -1。 (1, 0.25) 位于抛物线上。 焦点与该点之间的距离为 sqrt((0 - 1)^2 + (1 - 0.25)^2) = sqrt(1 + 0.5625) = sqrt(1.5625) = 1.25，该点与准线之间的距离为 0.25 - (-1) = 1.25，这是相同的。
由于点与焦点之间的距离和同一点与准线之间的距离相同，因此具有相同准线（扫描线）的两个抛物线的交点形成这两个点之间的平分线。 通过在每个新的 Voronoi 点处向沙滩线添加新的抛物线（并分割先前的抛物线），Fortune 算法跟踪 Voronoi 图的边缘。
最后的考虑是圆事件。 当三个焦点都位于同一个圆上时，这意味着当扫描线到达圆的顶部时，所有三个抛物线都将相交，这意味着中间的抛物线被“挤出”沙滩线。 因此，当我们从沙滩线添加或删除抛物线时，我们会检查它们是否形成圆事件。 圆事件也是两条边相遇并开始一条新边的地方。
一旦所有事件都被处理（并且不完整的边被扩展到边界），Voronoi 图就完成了。
在某些情况下，您想了解的不仅仅是 Voronoi 图的边缘。 在 Voronoi 图完成后，您可以计算与每个单独的 Voronoi 点关联的顶点。 例如，如果您尝试渲染填充的 Voronoi 图，并且需要知道单元格的顶点以形成三角形，这将非常有用。 VoronoiResult 类公开了一个 VoronoiCell 对象数组，这些对象本身允许您计算给定单元格的顶点（因为顶点直到您显式调用该方法才会被计算，如果您不需要访问它们，则不会产生性能损失）。