编辑“︁Graham扫描法”︁

= Graham扫描法 =

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

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

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

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

== 算法步骤详解 ==
=== 伪代码描述 ===
<syntaxhighlight lang="python">
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
</syntaxhighlight>

=== 示例输入输出 ===
'''输入点集'''：<code>[(0, 3), (1, 1), (2, 2), (4, 4), (0, 0), (1, 2), (3, 1), (3, 3)]</code>

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

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

== 复杂度分析 ==
* 时间复杂度：<math>O(n \log n)</math>（排序步骤占主导）
* 空间复杂度：<math>O(n)</math>（存储排序后的点和栈）

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

== 变体与优化 ==
* '''Andrew算法'''：采用双次扫描（上下凸包）避免三角函数计算。
* '''Chan算法'''：结合分治策略实现<math>O(n \log h)</math>复杂度（h为凸包顶点数）。

== 常见问题 ==
=== 如何处理共线点？ ===
在排序阶段保留距离最远的点，扫描阶段剔除中间点。

=== 浮点数精度问题 ===
使用符号比较代替直接叉积值比较：
<syntaxhighlight lang="python">
def cross_product(o, a, b):
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x)
</syntaxhighlight>

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:计算几何算法]]