用 Swift 实现 Quickhull 凸包算法：swift-algorithm-club 中的计算几何实战

本篇技术指南以 swift-algorithm-club 仓库中 Convex Hull/README.md 为骨架，围绕 Quickhull 凸包算法展开：从凸包的定义与算法背景、复杂度分析，到算法分步流程与伪代码，再结合仓库内完整可运行的 iOS 示例工程（View.swift）进行源码级拆解，并给出单元测试验证。读完后你将掌握 Quickhull 的核心思想（分治 + 叉积定向 + 点到直线距离），能够独立在 Swift 中实现并可视化凸包求解。

什么是凸包（Convex Hull）

给定平面上的一组点，凸包算法计算出一个由这些点本身围成的形状，使其包含全部给定点。直观地说，凸包是"包住"所有点的最小凸多边形——想象在钉满钉子的木板上绷紧一根橡皮筋，橡皮筋最终形成的轮廓就是这些钉子（点）的凸包。

       •        ••          •        
    •     •   •        •  •   •    • 
  •    •    •     •      •     •  •  
     •        •    •    •       •    
  •    •   •        •  •        •    

根据 README 的说明，凸包算法原则上也可以用于其他维度（更高维空间）的点集合，但本仓库中的这份实现专注于平面上的点（二维）。它的本质是：计算出点与点之间的连线，这些连线组合在一起恰好包含所有点。不同算法之间的比较，通常以各自的大 O 时间复杂度作为衡量标准。

在 Convex Hull/README.md 中作者 Jaap Wijnen 明确指出，凸包存在多种算法，而本实现采用的是 Quickhull（快速凸包）。

Quickhull 算法背景与复杂度

Quickhull 这一命名与快速排序（Quicksort）同源——两者都采用"选取枢轴 → 划分 → 递归"的分治策略。根据 README 的记载，该算法分别由 W. Eddy（1977 年） 和 A. Bykat（1978 年） 独立提出。

关于复杂度，README 给出了清晰的结论：

• 期望时间复杂度：O(n log n)
• 最坏情况时间复杂度：O(n²)

在平均条件下，Quickhull 的效率尚可；但在某些特殊分布下性能会显著退化——例如高度对称的点集，或者点分布在圆周上的情形。此时每一层递归都难以剔除足够多的内部点，划分收益下降，时间复杂度会向 O(n²) 甚至更差的方向恶化（README 原文描述为 "more exponential"）。

与基于排序的 Andrew 单调链（O(n log n)）、Graham 扫描等算法相比，Quickhull 的优势在于：在"大多数点靠近凸包内部"的典型分布下，它通过尽早剔除三角形内部的点来大幅缩小问题规模。这一点在下面的分步流程中会看得非常清楚。

Quickhull 算法核心步骤

README 将 Quickhull 的完整流程归纳为以下步骤：

1. 输入：一个点集合，这些点需要先按 x 坐标值排序（这是本实现的一个前置约定）。
2. 确定初始锚点：找出 x 坐标最小的点 A 和 x 坐标最大的点 B。因为它们在水平方向上处于最外侧，必然属于凸包。
3. 按直线划分：用 A、B 两点连成的直线将整个集合一分为二，得到两个子集，后续对它们分别递归处理。
4. 寻找最远点：在直线某一侧，找出距离该直线最远的点。这个点与 A、B 一起构成一个三角形。
5. 剔除内部点：落在该三角形内部的点不可能成为凸包顶点，可以直接忽略。
6. 递归推进：对三角形构成的两条新边（注意不是最初的直线 AB）重复步骤 4、5。
7. 终止条件：不断递归直到某侧不再有点剩余；此时所有被选中的点即构成凸包。

整个算法可以浓缩为两个递归调用，README 给出的伪代码形式如下：

findHull(S1, A, B)
findHull(S2, B, A)

其中 S1 是直线 AB 一侧的点集，S2 是另一侧的点集。注意第二次调用把方向反过来了（B → A），这是因为叉积定向测试是有方向性的，"某条有向线段的右侧"取决于线段的走向。

findHull 函数定义与分步行为

仓库中我们的函数定义（README 原文）：

findHull(points: [CGPoint], p1: CGPoint, p2: CGPoint)

即：给定一个点数组 points 与两个端点 p1、p2，找出该直线（从 p1 指向 p2）右侧的所有凸包顶点。README 详细列出了该函数的 9 个行为步骤：

1. 若 points 为空，直接返回——直线右侧已经没有点可以加入凸包。
2. 画一条从 p1 到 p2 的直线。
3. 在 points 中找出距离这条直线最远的点（记为 maxPoint）。
4. 把 maxPoint 插入到凸包数组中 p1 的紧后面（保持凸包顶点顺序正确）。
5. 画一条从 p1 到 maxPoint 的直线（line1）。
6. 画一条从 maxPoint 到 p2 的直线（line2）。这两条线与最初的直线共同围成一个三角形。
7. 三角形内部的点必然不属于凸包，可以忽略。检查 points 中哪些点位于 line1 的右侧，归入数组 s1。
8. 检查哪些点位于 line2 的右侧，归入数组 s2。注意：不存在同时位于 line1 右侧和 line2 右侧的点——否则 maxPoint 就不会是离初始直线（p1→p2）最远的那个点了（这是算法正确性的关键）。
9. 对两个新的点组再次递归调用 findHull：

findHull(s1, p1, maxPoint)
findHull(s2, maxPoint, p2)

递归层层展开、逐个收集，最终得到一个按顺序排列、完整描述凸包的顶点数组。

源码级实现解读

README 描述的是算法逻辑，而仓库中的 Convex Hull/Convex Hull/View.swift 给出了可直接运行的 Swift 实现。整个工程是一个基于 UIKit 的 iOS 应用：启动后随机生成 100 个点，实时计算凸包，并直接在屏幕上绘制。下面逐段拆解实现细节。

数据准备：随机点生成与按 x 坐标排序

View 类用 MAX_POINTS = 100 控制点的数量（View.swift），generateRandomPoints() 使用 arc4random 在视图范围内生成随机坐标，并在末尾按 x 排序：

let MAX_POINTS = 100
var points = [CGPoint]()
var convexHull = [CGPoint]()

func generateRandomPoints() {
  for _ in 0..<MAX_POINTS {
    let offset: CGFloat = 50
    let xrand = CGFloat(arc4random()) / CGFloat(UInt32.max) * (self.frame.width - offset) + 0.5 * offset
    let yrand = CGFloat(arc4random()) / CGFloat(UInt32.max) * (self.frame.height - offset) + 0.5 * offset
    let point = CGPoint(x: xrand, y: yrand)
    points.append(point)
  }
  points.sort { (a: CGPoint, b: CGPoint) -> Bool in
    return a.x < b.x
  }
}

排序是后续"取最小/最大 x 点"的前提——排序完成后，数组的第一个元素就是 x 最小的点（最左），最后一个元素就是 x 最大的点（最右）。

初始分割：quickHull 入口

quickHull(points:) 是算法入口（View.swift），它对应 README 流程中的步骤 1–3：

func quickHull(points: [CGPoint]) {
  var pts = points
  // 假设 points 至少包含 2 个点
  // 假设列表已按 x 排序

  // 最左点
  let p1 = pts.removeFirst()
  // 最右点
  let p2 = pts.removeLast()

  // p1 和 p2 是最外侧的点，因此属于凸包
  convexHull.append(p1)
  convexHull.append(p2)

  // 位于有向线 p1→p2 右侧的点
  var s1 = [CGPoint]()
  // 位于有向线 p2→p1 右侧的点
  var s2 = [CGPoint]()

  // p1 到 p2 的向量
  let lineVec1 = CGPoint(x: p2.x - p1.x, y: p2.y - p1.y)

  for p in pts { // 逐点判断其在 p1→p2 直线的左侧还是右侧
    let pVec1 = CGPoint(x: p.x - p1.x, y: p.y - p1.y)
    let sign1 = lineVec1.x * pVec1.y - pVec1.x * lineVec1.y // 叉积：判断点 p 在直线的哪一侧

    if sign1 > 0 { // 位于 p1 p2 直线右侧
      s1.append(p)
    } else { // 位于 p2 p1 直线右侧
      s2.append(p)
    }
  }

  // 寻找新的凸包点
  findHull(s1, p1, p2)
  findHull(s2, p2, p1)
}

这里有三个值得注意的实现细节：

• 叉积定向测试：lineVec1.x * pVec1.y - pVec1.x * lineVec1.y 计算的是向量 lineVec1 与 pVec1 的二维叉积（行列式），其符号决定了点 p 在直线（p1→p2）的哪一侧。这是整个算法最核心的几何原语，findHull 内部同样复用它。
• 坐标系方向：代码注释特别说明——在标准 xy 坐标系中，"位于直线右侧"对应的叉积符号应为负数，但由于 iPhone 屏幕坐标系的 y 轴方向是向下的，这里的判定条件反转为 sign1 > 0。
• 对称处理：初始直线把平面分成两侧，分别用 (p1, p2) 与反向的 (p2, p1) 两个有向边递归，与 README 伪代码 findHull(S1, A, B)、findHull(S2, B, A) 完全对应。

递归核心：findHull

findHull 完整实现了 README 的 9 个步骤（View.swift）：

func findHull(_ points: [CGPoint], _ p1: CGPoint, _ p2: CGPoint) {
  // 如果点集为空，说明该直线右侧没有点，这条边就是凸包的一部分
  if points.isEmpty {
    return
  }

  var pts = points
  var maxDist: CGFloat = -1
  var maxPoint: CGPoint = pts.first!

  for p in pts { // 对每个点计算到直线的距离
    let dist = distance(from: p, to: (p1, p2))
    if dist > maxDist { // 记录距离更大的点
      maxDist = dist
      maxPoint = p
    }
  }

  // 把离直线最远的点插入到凸包中 p1 的后面
  convexHull.insert(maxPoint, at: convexHull.index(of: p1)! + 1)

  // 从 points 中移除 maxPoint，因为接下来要把数组按新直线一分为二
  pts.remove(at: pts.index(of: maxPoint)!)

  // 位于有向线 p1→maxPoint 右侧的点
  var s1 = [CGPoint]()
  // 位于有向线 maxPoint→p2 右侧的点
  var s2 = [CGPoint]()

  // p1 到 maxPoint 的向量
  let lineVec1 = CGPoint(x: maxPoint.x - p1.x, y: maxPoint.y - p1.y)
  // maxPoint 到 p2 的向量
  let lineVec2 = CGPoint(x: p2.x - maxPoint.x, y: p2.y - maxPoint.y)

  for p in pts {
    let pVec1 = CGPoint(x: p.x - p1.x, y: p.y - p1.y) // 从 p1 到 p 的向量
    let sign1 = lineVec1.x * pVec1.y - pVec1.x * lineVec1.y // 判断 p 在 lineVec1 的左侧还是右侧

    let pVec2 = CGPoint(x: p.x - maxPoint.x, y: p.y - maxPoint.y) // 从 maxPoint 到 p 的向量
    let sign2 = lineVec2.x * pVec2.y - pVec2.x * lineVec2.y // 判断 p 在 lineVec2 的左侧还是右侧

    if sign1 > 0 { // p1 maxPoint 直线右侧
      s1.append(p)
    } else if sign2 > 0 { // maxPoint p2 直线右侧
      s2.append(p)
    }
  }

  // 寻找新的凸包点
  findHull(s1, p1, maxPoint)
  findHull(s2, maxPoint, p2)
}

代码与 README 的步骤一一对应：

• 步骤 3（找最远点）：通过遍历比较 distance(from:to:) 找到 maxPoint。这里使用 if dist > maxDist（严格大于），配合初始值 -1，保证至少会选中第一个点作为候选。
• 步骤 4（插入凸包）：convexHull.insert(maxPoint, at: convexHull.index(of: p1)! + 1) 保证新点插入到 p1 之后，从而让凸包顶点数组始终按多边形周界顺序排列。
• 步骤 7、8（划分）：对剩余点逐一做两次叉积定向测试——只落在 line1 右侧的进 s1，只落在 line2 右侧的进 s2。两个 if 是互斥的（else if），这正好印证了 README 步骤 8 中的关键论断：不存在同时位于两条线右侧的点。
• 步骤 9（递归）：findHull(s1, p1, maxPoint) 与 findHull(s2, maxPoint, p2)，与 README 的递归伪代码逐字对应。

点到直线的距离公式

distance(from:to:) 是算法中"找最远点"环节的数学基础（View.swift）：

func distance(from p: CGPoint, to line: (CGPoint, CGPoint)) -> CGFloat {
  // 如果 line.0 和 line.1 是同一个点，它们无法定义一条直线
  // （否则距离公式中会出现除零）。此时退化为计算 line.0 与点 p 之间的欧氏距离。
  if line.0 == line.1 {
    return sqrt(pow(p.x - line.0.x, 2) + pow(p.y - line.0.y, 2))
  }

  // 公式出处：Deza, Michel Marie; Deza, Elena (2013),
  // Encyclopedia of Distances (2nd ed.), Springer, p. 86, ISBN 9783642309588
  return abs((line.1.y - line.0.y) * p.x
    - (line.1.x - line.0.x) * p.y
    + line.1.x * line.0.y
    - line.1.y * line.0.x)
    / sqrt(pow(line.1.y - line.0.y, 2) + pow(line.1.x - line.0.x, 2))
}

这里使用的是标准的点到直线距离公式（直线由两点 line.0、line.1 定义）：

• 分子是直线方程的 Ax + By + C 形式取绝对值（代码中通过叉积展开实现）；
• 分母是方向向量 (line.1 - line.0) 的模长。

实现中特别处理了一个退化情形：当 line.0 == line.1（两点重合，无法构成直线）时，若继续套用公式会导致除零，此时退化为计算两点间的欧氏距离。从算法流程看，findHull 递归时传入的两点必然不同（p1 ≠ maxPoint、maxPoint ≠ p2），这个分支更多是防御性处理，保证函数在任意输入下都不会崩溃。

可视化绘制

作为一个演示工程，draw(_:) 方法把计算结果渲染到屏幕上（View.swift）：

override func draw(_ rect: CGRect) {
  let context = UIGraphicsGetCurrentContext()

  // 绘制凸包：红色折线，线宽 2.0
  context!.setLineWidth(2.0)
  context!.setStrokeColor(UIColor.red.cgColor)
  context!.setFillColor(UIColor.black.cgColor)

  let firstPoint = convexHull.first!
  context!.move(to: firstPoint)
  for p in convexHull.dropFirst() {
    context!.addLine(to: p)
  }
  context!.addLine(to: firstPoint) // 闭合多边形
  context!.strokePath()

  // 绘制原始点：黑色实心圆，半径 5
  for p in points {
    let radius: CGFloat = 5
    let circleRect = CGRect(x: p.x - radius, y: p.y - radius, width: 2 * radius, height: 2 * radius)
    context!.fillEllipse(in: circleRect)
  }
}

绘制逻辑把凸包顶点依次连线并闭合，最后回到起点，形成红色多边形轮廓；所有原始点以黑色圆点绘制。由于 convexHull 在算法执行过程中始终维护着正确的周界顺序（每一步新点都插入在 p1 之后），这里可以直接顺序连线而无需重新排序。

应用入口在 Convex Hull/Convex Hull/AppDelegate.swift：didFinishLaunchingWithOptions 中创建 UIWindow，将 View(frame:) 设为根视图控制器的视图；View 的 init 会立刻调用 generateRandomPoints() 与 quickHull(points:)，因此应用一启动即可看到算法结果。

测试验证：被剔除的点确实不在凸包内

仓库在 Convex Hull/Tests/Tests.swift 中提供了一个单元测试，验证算法结果的正确性。测试构建了一个水平初始直线的场景：

func testHorizontalInitialLine() {
  let view = View()
  let excludedPoint = CGPoint(x: 146, y: 284)          // 应被排除的点
  let includedPoints = [
    CGPoint(x: 353, y: 22),   // 右上
    CGPoint(x: 22, y: 22),    // 左上
    CGPoint(x: 157, y: 447),  // 下方
  ]

  view.points = [CGPoint]()
  view.convexHull = [CGPoint]()
  view.points.append(contentsOf: includedPoints)
  view.points.append(excludedPoint)
  view.points.sort { (a: CGPoint, b: CGPoint) -> Bool in
    return a.x < b.x
  }

  view.quickHull(points: view.points)

  assert(includedPoints.filter({ view.convexHull.contains($0) }).count == 3,
         "\(includedPoints) should have been included")
  assert(!view.convexHull.contains(excludedPoint),
         "\(excludedPoint) should have been excluded")
}

这个测试用例的设计很巧妙：3 个"角点"（y = 22 的两个点和下方的点）构成三角形，第 4 个点 (146, 284) 恰好落在三角形内部——它位于 x = 22 与 x = 353 之间、y 介于 22 与 447 之间，属于三角形内部点。测试断言：

• 3 个角点全部出现在 convexHull 中（应被包含）；
• 内部点 (146, 284) 不出现在 convexHull 中（应被剔除）。

这正好验证了 README 步骤 5 的核心论断：三角形内部的点不可能成为凸包的一部分。测试工程位于 Convex Hull/Convex Hull.xcodeproj，scheme 配置见 Tests.xcscheme，其中声明了 Tests.xctest 测试 target，并对 Convex Hull.app 建立 target 依赖（测试通过 TEST_HOST 挂载到宿主 App 上运行）。

如何运行与观察

该模块是一个完整的 Xcode 工程（Convex Hull/Convex Hull.xcodeproj），包含两个 target：

Target	类型	说明
Convex Hull	iOS 应用（com.apple.product-type.application）	可视化演示主程序
Tests	单元测试 bundle（com.apple.product-type.bundle.unit-test）	算法正确性验证

从工程配置（project.pbxproj）可以看到：主 App 的 SWIFT_VERSION = 4.2、IPHONEOS_DEPLOYMENT_TARGET = 10.2，测试 target 的部署目标为 iOS 11.0。

运行方式：

1. 用 Xcode 打开 Convex Hull/Convex Hull.xcodeproj；
2. 选择 Convex Hull scheme 运行到 iPhone 模拟器——启动后屏幕会显示 100 个随机黑点与计算出的红色凸包轮廓；
3. 选择 Tests scheme 执行单元测试（⌘U），验证 testHorizontalInitialLine 的包含/排除断言是否通过。

重复运行 App 时，每次 arc4random 生成的点集都不同，可以直观感受 Quickhull 在不同点分布下的表现：多数随机分布下算法很快收敛；而如果点恰好高度对称或近似分布在圆周上，则更接近 README 所描述的最坏情形。

总结

本文围绕 swift-algorithm-club 的 Convex Hull/README.md 完整梳理了 Quickhull 凸包算法：

• 算法定位：Quickhull 由 W. Eddy（1977）与 A. Bykat（1978）分别提出，期望复杂度 O(n log n)，最坏 O(n²)，在高度对称或圆周分布的点集上性能会退化；
• 核心思想：以 x 最小/最大两点确定初始直线，用叉积把点集分到两侧；每侧找出距直线最远的点构成三角形，剔除三角形内部点后对两条新边递归；
• 实现细节：仓库源码使用 CGPoint 与叉积符号判定点的方位，用点到直线距离公式找最远点，用 convexHull.insert(_:at:) 维护顶点的周界顺序，并防御性地处理了线段退化为点的除零情形；
• 验证方式：单元测试通过"3 个角点 + 1 个内部点"的用例，断言角点全部入选、内部点被剔除，为算法正确性提供了直接证据。

本文所述实现由 Jaap Wijnen 为 Swift Algorithm Club 编写。如果想要继续深入，可以直接阅读 Convex Hull/Convex Hull/View.swift 的完整源码，或参考 README 中关于凸包算法的原始描述。