第95课：凸包

学习目标

完成本课学习后，你将能够：

理解计算几何中“凸包”的概念及其几何意义。
掌握一种高效的凸包计算算法（Andrew算法）。
使用编程语言实现该算法，并能处理带有重复点的情况。
将凸包算法应用于解决简单的几何问题，如判断点是否在凸包边界上。

核心概念

1. 什么是凸包？ 想象在一块木板上钉着许多钉子。如果你用一根足够长的橡皮筋把所有钉子都圈在里面，然后松开手，橡皮筋会自然收缩并绷紧，最终围住外围的一些钉子。这个橡皮筋围成的多边形，就是这些点集的凸包。

更数学化的定义是：对于一个平面点集，凸包是包含该点集的最小凸多边形。凸多边形意味着多边形内部任意两点的连线都完全在多边形内部。

2. Andrew算法（单调链算法） 我们将学习一个名为 Andrew算法（或称单调链算法）的高效方法。它的核心思想是将问题分解为两个子问题：

构建下凸壳：从最左边的点开始，沿着x轴从左到右扫描，用栈维护一个“下凸”的边界。
构建上凸壳：从最右边的点开始，沿着x轴从右到左扫描，用栈维护一个“上凸”的边界。最后，将两部分边界合并，即得到完整的凸包。

3. 算法关键步骤

预处理：首先将所有点按照x坐标从小到大排序，如果x坐标相同，则按照y坐标排序。
利用叉积判断转向：这是核心操作。给定三个点 A, B, C，我们计算向量 AB 和 AC 的叉积（在2D中表现为一个标量值）。
- 叉积 > 0：表示从 AB 到 AC 是逆时针转向（左转）。
- 叉积 < 0：表示从 AB 到 AC 是顺时针转向（右转）。
- 叉积 = 0：表示三点共线。在构建凸壳时，我们需要确保边界始终是“凸”的，这意味着我们只能进行逆时针转向（或共线）。

代码示例

以下是一个完整的Python实现。代码包含详细注释，并处理了重复点的情况。

import sys

def cross(o, a, b):
    """
    计算向量 OA 和 OB 的叉积 (2D情况下是标量值)。
    o: 原点
    a: 第一个点
    b: 第二个点
    返回值: >0 (逆时针), <0 (顺时针), =0 (共线)
    """
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def convex_hull(points):
    """
    使用 Andrew 算法计算点集的凸包。
    参数 points: 一个包含 (x, y) 元组的列表
    返回值: 凸包顶点列表 (按逆时针顺序排列，且首尾相连)
    """
    # 1. 移除重复点并排序
    # 按 x 为主键，y 为次键排序，x 相同时按 y 排序
    points = sorted(set(points)) # 使用 set 去重，再排序
    # 如果点少于3个，则所有点都是凸包的一部分
    if len(points) <= 1:
        return points
    # 2. 构建下凸壳
    lower = []
    for p in points:
        # 当栈中至少有2个点，且新点p与栈顶两点形成的转向不是“逆时针或共线”时，弹出栈顶
        # 即如果新点p在栈顶两点连线的“右侧”（顺时针），说明栈顶点不是凸包的一部分
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    # 3. 构建上凸壳
    upper = []
    for p in reversed(points): # 从右向左扫描
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    # 4. 合并结果
    # 注意：下凸壳的最后一个点和上凸壳的第一个点是同一个点（最右边的点），因此需要去掉重复。
    # 同理，上凸壳的最后一个点和下凸壳的第一个点是同一个点（最左边的点）。
    # 合并后的列表即为完整的凸包顶点（逆时针顺序）。
    convex_polygon = lower[:-1] + upper[:-1]
    return convex_polygon

# 测试代码
if __name__ == "__main__":
    # 示例点集
    points_list = [
        (0, 0), (1, 1), (2, 2), (4, 4), (0, 1), (1, 0), (3, 1),
        (1, 2), (2, 1), (0, 2), (2, 0)
    ]
    print("输入点集:", points_list)
    hull = convex_hull(points_list)
    print("凸包顶点 (按逆时针顺序):", hull)
    # 预期输出应为：[(0, 0), (0, 2), (2, 2), (4, 4), (3, 1), (2, 0)] 或类似顺序的凸包顶点。

实践练习

练习1（基础）：验证边界点 编写一个函数 is_on_hull(point, hull_polygon)，判断一个给定的点是否是凸包多边形 hull_polygon 的一个顶点。

输入：点 (2, 1) 和上一个示例计算出的凸包列表。
预期输出：True 或 False。

练习2（进阶）：计算凸包周长 结合上一课“计算几何基础”中学习的距离计算知识，编写一个函数，计算给定凸包的周长。

输入：凸包顶点列表（逆时针顺序）。
提示：遍历每个顶点到下一个顶点的距离，最后一个顶点要与第一个顶点相连。
输入示例：使用上面代码示例生成的凸包。
预期输出：一个浮点数，表示凸包的总周长。

练习3（挑战）：带权重的凸包 假设每个点都有一个“权重”或“高度”，你需要计算的是“加权凸包”。加权凸包的定义是：在标准凸包的基础上，还需包含所有权重值大于凸包边界上平均权重的点。

输入：一个列表，元素为 (x, y, weight) 三元组。
算法思路：
1. 计算只考虑 (x, y) 的标准凸包。
2. 计算该凸包边界上所有点的平均权重。
3. 将原始点集中所有权重大于此平均权重的点加入结果集。
4. 对结果集再次运行凸包算法（因为新加入的点可能在更外层）。
这个问题有多种解释和解法，此练习旨在激发思考。

常见错误

未处理重复点：如果输入点集中有完全相同的点，排序后它们会相邻。在叉积计算和栈操作中可能导致除以零或逻辑错误。代码中使用 set 去重是关键一步。
排序错误：Andrew算法强烈依赖点按x坐标（主）和y坐标（次）排序。如果排序逻辑错误，算法将无法得到正确的凸壳。
叉积符号误解：cross 函数的符号（正/负）表示的转向方向必须与代码中的逻辑判断（<= 0）保持一致。误用符号会导致构建出凹的边界。请始终记住：“叉积 > 0 代表逆时针（左转）”。
忽略共线点：当前代码的处理方式（cross <= 0）会保留共线的边界点。如果题目要求只保留凸多边形的顶点（即严格凸包），那么判断条件应改为 cross < 0，这样共线点中的中间点会被弹出栈。需根据具体问题调整。
合并结果错误：在合并 lower 和 upper 列表时，需要小心去掉首尾的重复点（lower[:-1] + upper[:-1]）。常见的错误是连接点遗漏或重复添加。

小结

本课我们学习了计算几何中的一个重要问题——凸包，并重点掌握了Andrew算法。

核心思想：分而治之，利用x坐标排序将问题分解为构建下凸壳和上凸壳两个子任务。
关键工具：向量叉积是判断转向、维持凸性的数学基础。
算法步骤：排序 -> 构建下凸壳 -> 构建上凸壳 -> 合并结果。
实现要点：注意处理输入点的排序和去重，正确理解和使用叉积符号来控制栈的弹出条件。
复杂度：排序的复杂度为 O(n log n)，构建两个凸壳的复杂度为 O(n)，因此总时间复杂度为 O(n log n)，非常适合处理大规模点集。

掌握了凸包算法，你就拥有了解决许多复杂几何问题（如最远点对、点集直径、多边形交集）的基础。下一课，我们将进入另一个有趣的算法领域：离线算法与莫队。

练习编辑器

rust