凸包算法

凸包算法（Convex Hull Algorithm）是计算几何中的经典问题，用于在给定一组平面点的情况下，找到包含所有点的最小凸多边形。凸包在计算机图形学、地理信息系统（GIS）、机器人路径规划等领域有广泛应用。

基本概念

什么是凸包？

在二维平面上，给定一组点，凸包是包含所有点的最小凸多边形。凸多边形的定义是：多边形内任意两点的连线仍完全包含在多边形内。

数学定义：对于点集$S\subset {\mathbb{ℝ}}^2$，其凸包$\text{CH}(S)$是所有包含$S$的凸集的交集。

凸包的性质

• 凸包的顶点一定是原始点集中的点。
• 凸包是唯一的（对于给定点集）。
• 凸包边界上的点按顺时针或逆时针方向排列。

常见算法

Graham扫描法

Graham扫描法（Graham's Scan）是时间复杂度为$O(n\log n)$的经典算法，步骤如下：

1. 找到最左下角的点（作为基准点）。 2. 按极角排序其他点（若极角相同，则按距离排序）。 3. 使用栈维护凸包，依次检查每个点是否能与栈顶两点构成“非左转”关系。

def convex_hull_graham(points):
    # 找到最左下角的点
    start = min(points, key=lambda p: (p[1], p[0]))
    
    # 极角排序函数
    def polar_angle(p):
        return math.atan2(p[1] - start[1], p[0] - start[0])
    
    # 按极角排序（若极角相同，按距离排序）
    sorted_points = sorted(points, key=lambda p: (polar_angle(p), (p[0]-start[0])**2 + (p[1]-start[1])**2))
    
    # 初始化栈
    stack = [start, sorted_points[0], sorted_points[1]]
    
    # Graham扫描
    for p in sorted_points[2:]:
        while len(stack) >= 2:
            # 检查是否左转（叉积）
            x1, y1 = stack[-2]
            x2, y2 = stack[-1]
            x3, y3 = p
            cross = (x2 - x1)*(y3 - y1) - (y2 - y1)*(x3 - x1)
            if cross <= 0:  # 非左转则弹出栈顶
                stack.pop()
            else:
                break
        stack.append(p)
    
    return stack

输入示例：

points = [(0, 0), (1, 1), (2, 2), (3, 1), (2, 0), (1, 0.5)]

输出示例：

[(0, 0), (2, 0), (3, 1), (2, 2), (1, 1)]

Andrew单调链算法

Andrew算法是另一种$O(n\log n)$算法，通过上下凸链构造凸包： 1. 按x坐标（若x相同则按y）排序点。 2. 构造下凸链和上凸链。 3. 合并两条链得到凸包。

def convex_hull_andrew(points):
    points = sorted(points)
    lower = []
    upper = []
    for p in points:
        while len(lower) >= 2 and (lower[-1][0]-lower[-2][0])*(p[1]-lower[-2][1]) <= (lower[-1][1]-lower[-2][1])*(p[0]-lower[-2][0]):
            lower.pop()
        lower.append(p)
    for p in reversed(points):
        while len(upper) >= 2 and (upper[-1][0]-upper[-2][0])*(p[1]-upper[-2][1]) <= (upper[-1][1]-upper[-2][1])*(p[0]-upper[-2][0]):
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]

可视化示例

graph TD A[输入点集] --> B[选择算法] B --> C[Graham扫描] B --> D[Andrew算法] C --> E[排序点集] E --> F[构建凸包] D --> G[构造上下链] G --> H[合并凸包] F --> I[输出凸包] H --> I

应用场景

• 计算机图形学：碰撞检测、可见性计算。
• 机器人导航：计算可通行区域。
• GIS系统：地图边界简化。
• 模式识别：形状特征提取。

性能比较

算法对比

算法	时间复杂度	适用场景
Graham扫描	$O(n\log n)$	适合极角分布均匀的点集
Andrew算法	$O(n\log n)$	适合x坐标分布均匀的点集
Jarvis步进法	$O(nh)$（h为凸包点数）	适合凸包点数较少的情况

扩展阅读

• 三维凸包算法（如Quickhull算法）。
• 动态凸包维护（支持点集的插入和删除）。
• 近似凸包算法（用于大规模数据）。