FortuneSwift

FortuneSwift 是一个 Swift 框架，它使用 Fortune 算法从 2D 平面上的一组点生成 Voronoi 图和 Delaunay 三角剖分。 Fortune 算法的时间复杂度为 O(n log n)，空间复杂度为 O(n)。 此框架兼容 iOS 8+、macOS 10.13+。

可以使用 Swift Package Manager 安装 FortuneSwift 框架。 在 Xcode 中：File > Swift Packages > Add Package Dependency..，URL：https://github.com/TateLiang/FortuneSwift.git

或者

• 将 .package(url: "https://github.com/TateLiang/FortuneSwift.git", from: "1.1.6") 添加到 Package.swift 文件的 dependencies 中。
• 使用 $ swift package update 更新您的软件包。

1. 添加软件包依赖
2. 导入 import FortuneSwift
3. 创建一个 Voronoi 对象，指定一个 Coordinate 数组和矩形区域。

let points: [Coordinate] = [ ... ]
let rect = (x: 25, y: 25, width: 500, height: 500)

let voronoi = Voronoi(sites: points, numPoints: points.count, rect: rect)

或者，如果未给出数组，则在矩形区域内生成 numPoints 个随机点。

let voronoi = Voronoi(numPoints: 150, rect: rect)

FortuneSwift 输出一个双向连接边列表 (DCEL)，存储为站点、Voronoi 顶点和半边的数组。 此框架提供四个类来访问该图：Coordinate、Site、Vertex 和 HalfEdge。 此信息可用于绘制 Voronoi 图或 Delaunay 三角剖分。

创建 voronoi 对象后，可以通过属性获得结果数组

var voronoiVertices: [Vertex]
var voronoiEdges: [HalfEdge]
var voronoiSites: [Site]

每个类的主要属性详述如下。

var x: Double
var y: Double
var firstEdge: HalfEdge?
var surroundingEdges: [HalfEdge]?

var x: Double
var y: Double
var incidentEdges: [HalfEdge]

var origin: Vertex?
var destination: Vertex?

var twin: HalfEdge?
var next: HalfEdge?
var prev: HalfEdge?

var incidentSite: Site?

func walk() -> [HalfEdge]? 

• firstEdge 是定义站点 Voronoi 单元格的任意边。 surroundingEdges 可用于获取定义该单元格的所有边的列表。
• HalfEdge 按照逆时针方向追踪 Voronoi 单元格，假设坐标系中 y 向上增加，x 向右增加，incidentSite 位于其左侧。
• 如果 incidentSite 是边界矩形的外部边界上的边，则为 nil。
• walk() 输出定义单元格的 HalfEdges 环，如果边不形成环，则输出 nil（不应该发生）

Voronoi 图是平面上单元格的镶嵌，表示最接近特定点的点。 对于每个 Voronoi“站点”，其区域定义为比任何其他站点更接近它的点。 Voronoi 图也是 Delaunay 三角剖分的对偶图，其中 Voronoi 图的每条边都对应于两个入射点之间 Delaunay 三角剖分中的相邻边。 Voronoi 图具有多种应用，包括天文学、艺术、生物学、机器人技术和物理学。

Fortune 算法是一种计算几何中的扫描线算法。 类似于凸包或线段相交等问题，通过优先级队列数据结构维护事件队列。 Fortune 算法还使用二叉搜索树来维护“海滩线”，表示基于扫描线位置的当前已知单元格。 在算法结束时，可以通过多边形（在本例中为矩形）来限制无限边。

• 位于边界框之外的点仍会影响 Voronoi 图，因为该框只是限制了所有无限边。
• 该算法不适用于所有点共线的情况。
• 该算法不适用于同一位置有多个站点的情况。