Graham扫描法

Graham扫描法

Graham扫描法（Graham's scan）是一种用于求解平面点集凸包问题的经典算法，由罗纳德·格雷厄姆（Ronald Graham）于1972年提出。该算法的时间复杂度为$O(n\log n)$，是计算几何中的基础算法之一。

算法概述

Graham扫描法通过以下步骤构造凸包： 1. 选择极点：找到点集中y坐标最小的点（若y坐标相同，则选择x坐标最小的点），作为凸包的起始点（称为“极点”）。 2. 极角排序：将剩余点按照相对于极点的极角从小到大排序（若极角相同，则按距离极点从近到远排序）。 3. 扫描构造：使用栈结构依次处理排序后的点，剔除会导致非凸性的点，最终栈中保留的点即为凸包顶点。

数学基础

极角排序

极角指从极点出发的向量与x轴正方向的夹角，可通过叉积判断方向关系。对于两点$p_1$和$p_2$： $\text{叉积}=(p_1-p_0)\times (p_2-p_0)$ 若叉积为正，则$p_1$在$p_2$的逆时针方向；若为负则相反；若为零则共线。

凸性检测

在扫描过程中，通过检查连续三个点的转向关系（叉积符号）判断是否保持凸性。

算法步骤详解

伪代码描述

def graham_scan(points):
    # Step 1: 找到极点
    p0 = min(points, key=lambda p: (p.y, p.x))
    
    # Step 2: 极角排序
    sorted_points = sorted(points, key=lambda p: (atan2(p.y - p0.y, p.x - p0.x), p.distance_squared(p0)))
    
    # Step 3: 扫描构造
    stack = []
    for p in sorted_points:
        while len(stack) >= 2 and cross_product(stack[-2], stack[-1], p) <= 0:
            stack.pop()
        stack.append(p)
    return stack

示例输入输出

输入点集：[(0, 3), (1, 1), (2, 2), (4, 4), (0, 0), (1, 2), (3, 1), (3, 3)]

输出凸包顶点（逆时针顺序）： [(0, 0), (3, 1), (4, 4), (0, 3)]

graph TD A[(0,0)] --> B[(3,1)] B --> C[(4,4)] C --> D[(0,3)] D --> A

复杂度分析

• 时间复杂度：$O(n\log n)$（排序步骤占主导）
• 空间复杂度：$O(n)$（存储排序后的点和栈）

实际应用

1. 碰撞检测：在游戏开发中快速判断物体是否可能碰撞。 2. 地理围栏：确定GPS点集的地理边界。 3. 模式识别：提取图像中物体的轮廓特征。

变体与优化

• Andrew算法：采用双次扫描（上下凸包）避免三角函数计算。
• Chan算法：结合分治策略实现$O(n\log h)$复杂度（h为凸包顶点数）。

常见问题

如何处理共线点？

在排序阶段保留距离最远的点，扫描阶段剔除中间点。

浮点数精度问题

使用符号比较代替直接叉积值比较：

def cross_product(o, a, b):
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x)

扩展阅读

• 三维凸包问题可通过类似思路扩展（如QuickHull算法）。
• 动态凸包维护适用于点集增删场景。