想象一下这样的场景：幼儿园老师带着二十几个小朋友到操场做游戏，老师想让大家手拉手围成一个最紧凑的大圆圈，把所有人都圈在里面，而且这个圈的周长要最短、绳子要最省。你会怎么做？聪明的老师会说：“先找到一个最靠边的小朋友当旗手，其他人按从旗手看出去的方向排好队，然后一个接一个拉进圈里，发现有人拐弯方向不对（本该右转却左转）就请他出列。”这就是 Graham 扫描的思路。另一位老师更直接：“大家先按从左到右、矮个在前排好队，我先把上半圈的队伍拉出来，再把下半圈的队伍拉出来，拼在一起就是一个完整的大圈。”这就是 Andrew 单调链的思路。两条路殊途同归，都能用最快的方式找到那个“最外圈”，只是排队的规则、检查的细节不一样。本文带你用这个故事看懂两大凸包算法的原理、差异与选型，从此面对“一堆点怎么求外围边界”的问题时，心里永远有谱。

岗位关联

凸包是计算几何的基石操作，在自动驾驶障碍物圈定、图像轮廓提取、点云聚类等 AI 场景中无处不在。掌握 Graham 与 Andrew 两种经典算法及其取舍，是构建扎实工程能力的必经之路。

目录
  1. 可视化演示
  2. 凸包概念与意义
  3. 计算几何基础
  4. Graham 算法
  5. Andrew 算法
  6. 算法对比
  7. 退化与技巧
  8. 选型总结
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

凸包算法中Graham Scan基于极角排序，Andrew单调链基于坐标排序，两者都是O(nlogn)解法。本... 切换模式查看不同维度。

本节配有交互动效（进入视口后自动加载，约 3KB）。

一、凸包问题：核心原理 动态展示关键流程与数据流动 交互控件调节参数实时渲染 f(x) = transform(x) 核心概念的可视化呈现

凸包概念与意义

老师带着孩子们做围圈游戏，第一步要弄明白：什么才算“一个合格的圈”？规矩很简单：所有小朋友都必须站在圈内（或圈边上），圈必须是凸的——不能有凹进去的“口袋”，而且这个圈的周长要尽可能短。把小朋友抽象成平面上的点，这个“最短凸圈”就是凸包。

在数学上，凸包是包含点集的最小凸集。想象你在桌上钉了一排图钉，用一根橡皮筋把它们全部套住，松手后橡皮筋绷紧形成的多边形，就是这些图钉的凸包。橡皮筋只会碰到最外面的图钉，内部的图钉完全不影响它的形状。这正是凸包名字的由来——它是“包住所有点的最外层凸壳”。

凸包在 AI 与工程中无处不在：自动驾驶用凸包圈定障碍物群的安全范围，机器视觉用凸包描述手部轮廓，点云聚类后用凸包生成包围盒。理解凸包，就理解了“如何给一堆散点画最紧凑的边界”。

回到围圈游戏：凸包就是老师最终让小朋友手拉手形成的那条最短的凸线圈。接下来所有算法，都是在回答同一个问题——如何高效地找出“哪些小朋友该站在圈上”。

conv(S)={∑i=1nλipi  |  λi≥0,  ∑i=1nλi=1,  pi∈S}\mathrm{conv}(S) = \left\{ \sum_{i=1}^{n} \lambda_i p_i \;\middle|\; \lambda_i \geq 0,\; \sum_{i=1}^{n} \lambda_i = 1,\; p_i \in S \right\}
这个公式说：凸包是点集 S 中所有点的“加权平均”能到达的位置的集合。权重 λᵢ 非负且加起来等于 1，因此得到的点永远落在这些点围成的范围内，不会“飞出去”。
  1. 凸组合条件每个点 pᵢ 配一个权重 λᵢ，权重必须非负，且所有权重之和恰好为 1，保证结果点落在点集的“内部范围”内。
    ∑i=1nλi=1,λi≥0\sum_{i=1}^{n} \lambda_i = 1,\quad \lambda_i \geq 0
  2. 所有加权平均的集合遍历所有可能的权重分配，得到的全部点构成的集合就是凸包，它恰好是最小的凸多边形
    conv(S)={∑i=1nλipi  |  λi≥0,  ∑i=1nλi=1}\mathrm{conv}(S) = \left\{ \sum_{i=1}^{n} \lambda_i p_i \;\middle|\; \lambda_i \geq 0,\; \sum_{i=1}^{n} \lambda_i = 1 \right\}
  3. 几何直觉两个点的凸包是线段，三个点组成的凸包是三角形，多个点的凸包是最外圈围成的凸多边形
    凸包边界顶点⊆S\text{凸包边界顶点} \subseteq S

计算几何基础

围圈时老师需要一条规则来判断“新加入的小朋友应该站在哪儿”。这条规则就是“左转还是右转”：假设你已经确定了两个小朋友 A、B 的位置，现在来了一位新朋友 C，老师要看从 A 到 B 再到 C 的路线是向左拐还是向右拐。向左拐说明 C 在圈的外侧，可以保留；向右拐说明 C 缩进了圈内，得请他出列。这个“左转右转”的数学工具，就是向量叉积。

叉积是计算几何的“红绿灯”。两个平面向量 a、b 的叉积为一个标量（实际上叉积向量垂直于平面，其模长为 |a||b|sinθ）。它的符号直接告诉我们旋转方向：正数表示 b 在 a 的逆时针方向（左转），负数表示顺时针方向（右转），零表示两者共线。更妙的是，叉积可以通过坐标直接计算，不需要任何三角函数，整数坐标下甚至完全精确。

有了叉积这把尺子，Graham 和 Andrew 就有了共同的“检查口令”：每次准备把新点纳入凸包时，都看它相对于当前最后两个点是不是左转。如果是右转或共线，说明当前凸包顶点“突出去”了，需要回退。这个“左转保留、右转弹出”的规则，贯穿两大算法的全部扫描过程。

老师手里的“左转右转”规则，本质上就是叉积。下一个问题：有了规则，该按什么顺序把小朋友拉进圈里？这引出了两种截然不同的排队策略。

cross(a,b)=axby−aybx\text{cross}(a, b) = a_x b_y - a_y b_x
叉积的符号就是转向的判决：cross > 0 为左转（逆时针），cross < 0 为右转（顺时针），cross = 0 为共线或重合。
  1. 坐标代入将向量 a 的 x 分量乘 b 的 y 分量，减去 a 的 y 分量乘 b 的 x 分量，得到一个标量结果。
    cross(a,b)=ax×by−ay×bx\text{cross}(a,b)=a_x \times b_y - a_y \times b_x
  2. 符号判决结果为正表示 b 相对 a 逆时针旋转（左转），为负表示顺时针旋转（右转），为零表示两向量方向相同或相反（共线）。
    cross(a,b)>0⇒左转,cross(a,b)<0⇒右转\text{cross}(a,b) > 0 \Rightarrow \text{左转},\quad \text{cross}(a,b) < 0 \Rightarrow \text{右转}
  3. 三点转向判断 A→B→C 的转弯方向时，令 a = B−A、b = C−B，代入叉积公式即可，无需计算任何角度。
    cross(B−A,  C−B)\text{cross}(B-A,\; C-B)

Graham 算法

Graham 老师的做法很有仪式感：先请队伍最左下角的小朋友（y 坐标最小，若相同取 x 最小）当旗手，站到圈的中心参考点。然后其余小朋友按“从旗手看出去的方向角”从小到大排队——方向角最小的先来，像钟表指针从 0 度开始顺时针扫过一圈。排好队后，老师挨个把小朋友拉进圈，每拉进一个，就检查“最后三个人的转弯方向”：若是左转就留下，若是右转（或共线）就把中间那个小朋友请出列，继续回退检查，直到满足左转为止。

这个“拉进—检查—回退”的过程，在计算机里用栈完美模拟。栈里存的是当前认定的凸包顶点。新点到来时压入栈顶，然后 while 循环检查栈顶三个元素：若 cross（倒数第三，倒数第二，倒数第一） ≤ 0，说明倒数第二点不是凸包顶点，弹出它，继续检查，直到新的三个点形成左转。扫描完所有点后，栈中剩下的就是凸包顶点。

Graham 的关键在于“按角度排序后一趟扫描”。极角排序本身是 O(n log n)，扫描阶段每个点至多入栈一次、出栈一次，是 O(n)。它的思想之美在于把二维的“围圈”问题，通过角度排序降维成一维的“排队检查”问题。

Graham 老师的方向角排队法思路清晰、教学意义极强，但它有一个小隐患：计算方向角需要调用 atan2 反三角函数，这是浮点运算，在角度非常接近时可能产生精度误差。接下来出场的 Andrew 老师，换了一个更“憨厚”但更稳的排队方式。

while    cross(Pk−2,  Pk−1,  Pk)≤0:pop  Pk−1\text{while}\;\; \text{cross}\left(P_{k-2},\; P_{k-1},\; P_k\right) \leq 0:\quad \text{pop}\; P_{k-1}
这是 Graham 扫描的核心循环：只要最后三个点不是左转（右转或共线），就把中间那个点弹出栈，因为它不可能成为凸包顶点。
  1. 栈顶三点设栈中最后三个点按顺序为 P_{k-2}（倒数第三）、P_{k-1}（倒数第二）、P_k（当前新点）。
    Pk−2,  Pk−1,  PkP_{k-2},\; P_{k-1},\; P_k
  2. 叉积判定计算从 P_{k-2} 到 P_{k-1} 再到 P_k 的转向叉积，若 ≤ 0 表示右转或直行，此时中间点 P_{k-1} 凹进圈内。
    cross(Pk−2→Pk−1,  Pk−1→Pk)≤0\text{cross}(P_{k-2} \to P_{k-1},\; P_{k-1} \to P_k) \leq 0
  3. 弹栈回退将 P_{k-1} 弹出栈，因为它在凸包内侧不可能是边界点，然后继续用新的倒数第二、倒数第三与新点比较。
    stack.pop(),重复检查新栈顶\text{stack.pop()},\quad \text{重复检查新栈顶}

Andrew 算法

Andrew 老师的策略完全不同：不找旗手、不算角度，直接让所有小朋友按“从左到右，x 相同则矮个在前”排成一列。然后他从左端出发，先圈“上半圈”（下凸链）：一个接一个把小朋友拉进圈，规则和 Graham 一样——最后三个点必须左转，否则弹出中间点。走到最右端后，再调头从右往左走，圈出“下半圈”（上凸链）。两条链拼在一起，就是完整的凸包。

为什么不用角度排序？因为按 x 坐标排序是纯整数比较（或浮点比较），完全不涉及三角函数，数值上更干净。Andrew 的精妙之处在于：凸包天然由“上边界”和“下边界”两部分组成。从左往右扫，遇到的是不断“左转上升”的下边界；从右往左扫，遇到的是不断“左转下降”的上边界。两次扫描各维护一个单调栈，合起来恰好覆盖凸包的全部顶点。

这个思路被称为“单调链”（Monotone Chain），因为每条链在 x 方向上都是单调递增（或递减）的。对比 Graham 的“一维角度排序 + 一圈扫描”，Andrew 是“一维坐标排序 + 两段扫描”。两者排序都是 O(n log n)，扫描都是 O(n)，但 Andrew 的排序比较更简单、更稳，常数因子也更小——这也是它在工程上更受欢迎的原因。

Andrew 老师的“排两趟队”法既稳又省事，和 Graham 老师“按角度排一趟队”殊途同归。那么，两位老师的方案到底谁快谁稳？下一节我们掰开揉碎对比一番。

H=lower_chain∪upper_chainH = \text{lower\_chain} \cup \text{upper\_chain}
Andrew 的凸包由两条链拼成：从左到右走出的“下凸链”加上从右到左走出的“上凸链”，两条链首尾相接，恰好形成一个闭合的凸多边形。
  1. 坐标排序将所有点按 x 升序排列（x 相同按 y 升序），得到从左到右的一列队伍。
    P0,P1,…,Pn−1,Pi.x≤Pj.x  (i<j)P_0, P_1, \dots, P_{n-1},\quad P_i.x \leq P_j.x\;(i<j)
  2. 下凸链构建从左到右扫描每个点压入栈，若最后三个点叉积 ≤ 0（未左转）则弹出中间点，扫描完得到下边界。
    lower_chain=scan(P0→Pn−1)\text{lower\_chain} = \text{scan}\left(P_0 \to P_{n-1}\right)
  3. 上凸链构建从右到左再次扫描每个点，同样的左转检查，得到上边界，两链首尾相连构成凸包。
    upper_chain=scan(Pn−1→P0)\text{upper\_chain} = \text{scan}\left(P_{n-1} \to P_0\right)

算法对比

两位老师都声称自己的围圈方法“最快”，那到底怎么比？先看总工作量：Graham 的排序基于 atan2 角度，每个点要算一次反三角函数，再按浮点角度排序；Andrew 的排序基于坐标大小，直接比较 x、y 数值。从时间复杂度的“大 O”视角看，排序都是 O(n log n)、扫描都是 O(n)，两者在最坏情况下渐近复杂度完全一致，都是 O(n log n)。

但实际工程中，常数因子同样重要。Graham 每排一个点就要算一次 atan2——这是一个昂贵的数学函数，可能比一次整数比较慢几十倍；而 Andrew 的比较只是几次加减法和乘法。在 10 万个点的数据上，这种常数差距可能是几百毫秒对几毫秒的差别。此外，Graham 排序后对共线点的处理依赖极角相等的浮点判断，而 Andrew 的共线判断用的是整数叉积，更可控。

数值稳定性是另一个关键维度。atan2 在角度相差极小（比如几个点几乎在同一方向但略偏）时，浮点舍入可能导致排序错位，进而让凸包“掉点”或“多出尖刺”；而 Andrew 的坐标比较在输入为整数时完全精确，即使输入是浮点数，比较的相对误差也小得多。因此在要求稳健的工业代码中，Andrew 几乎是默认答案。

从“复杂度相同”这个结论看，两位老师打了个平手。但赛场上的真实差别在细节——排序的单价、浮点的误差、以及面对“歪瓜裂枣”的退化输入时的表现。

T(n)=O(nlog⁡n)+O(n)=O(nlog⁡n)T(n) = O(n \log n) + O(n) = O(n \log n)
两种算法的时间复杂度都由排序主导：排序 O(n log n) 加上扫描 O(n)，总复杂度相同。真正的差异藏在“排序的代价”和“数值的稳健性”里，而不是渐近复杂度里。
  1. 排序主导排序阶段是瓶颈，两种算法都需要对 n 个点排序，因此总时间至少为 O(n log n)。
    Tsort(n)=O(nlog⁡n)T_{\text{sort}}(n) = O(n \log n)
  2. 扫描线性排序完成后，每个点至多入栈和出栈各一次，扫描阶段是线性的。
    Tscan(n)=O(n)T_{\text{scan}}(n) = O(n)
  3. 总量相同两部分相加，大 O 意义下两者均为 O(n log n)，复杂度不分伯仲。
    TGraham(n)=TAndrew(n)=O(nlog⁡n)T_{\text{Graham}}(n) = T_{\text{Andrew}}(n) = O(n \log n)

退化与技巧

真实世界里，小朋友不会整整齐齐站成理想位置：可能有两人站同一位置（重复点），可能三个以上的人恰好站在同一条直线上（共线点），也可能位置坐标带有小数点。这些“退化情况”正是算法翻车的高发区。

先处理重复点。如果点集里有完全相同的坐标，排序后它们会相邻，扫描时叉积为 0 会触发弹栈逻辑，虽然通常不影响最终凸包，但最好在预处理阶段用哈希表去重，既省时间又避免意外。共线点则更微妙：假设一排小朋友站成直线，凸包只需要两个端点，中间的人都是“冗余”的。两种算法用叉积 ≤ 0 弹出共线点，天然去掉了中间点，但如果你希望凸包边上保留所有共线点（比如需要描边），就要把条件改成 < 0。

浮点误差是另一只“隐形老虎”。Graham 的 atan2 在角度极接近时可能因舍入排错序，而 Andrew 的整数叉积在坐标是整数时零误差。若坐标本身是浮点数，建议设置一个极小阈值 eps（如 1e-9）来判定叉积是否为 0，避免把“几乎共线”误判成“左转或右转”。这些小技巧，都是工程师在实践中踩坑踩出来的。

退化情况就像操场上的突发状况，考验的是老师的临场应变。两位老师的应对策略大同小异，但 Andrew 因为少了三角函数，在“精度防线”上天然更坚固。那么，到了真正带队出发时，该选哪套方案？

cross(a,b)=0  ⇔  a∥b  (或  a,b  共线)\text{cross}(a,b) = 0 \;\Leftrightarrow\; a \parallel b \;(\text{或} \; a,b \; \text{共线})
叉积为零意味着两个向量共线——在凸包问题中，这代表三个点处于同一条直线上，中间那个点是否保留取决于你对“严格凸”还是“退化凸”的需求。
  1. 共线判定当叉积结果恰好为 0 时，三个点共线（或两点重合），这是退化情况的核心判据。
    cross(a,b)=0\text{cross}(a,b)=0
  2. 去重预处理在排序前用集合或哈希表去除坐标完全相同的点，让后续扫描更干净。
    points=unique(S),∣S∣≥∣points∣\text{points} = \text{unique}(S),\quad |S| \geq |\text{points}|
  3. 阈值容错浮点坐标下引入 eps 阈值，把 |cross| < eps 视为共线，抵御舍入误差。
    ∣cross(a,b)∣<ε  ⇒  视为共线|\text{cross}(a,b)| < \varepsilon \;\Rightarrow\; \text{视为共线}

选型总结

现在回到最初的问题：作为工程师（或者那位老师），到底该用 Graham 还是 Andrew？答案很直接：绝大多数场景默认选 Andrew。原因我们已经反复看到——坐标排序更简单、常数因子更小、整数输入下零误差、共线点处理更直观。它就像一个“不会出错的稳重老师”，适合批量生产环境。

那 Graham 就一无是处吗？当然不。Graham 的“极角排序”思想是计算几何中最优雅的抽象之一：把二维问题通过角度降维成一维问题。理解 Graham，你对“如何设计排序让扫描更简单”会有更深的体会。在教学、面试讲解、或者需要按角度访问点时，Graham 仍然不可替代。此外，Graham 的变体在动态凸包（增量加点）场景中也更易扩展。

最后给出工程建议：默认用 Andrew，但两者结果在理想情况下完全一致。不妨在你的代码库里同时实现两个版本，用随机点集做对拍测试——你会发现它们输出完全相同的凸包。这种“双实现互验”的做法，本身就是工程上检验算法正确性的利器。

两位老师最终都带着孩子们围出了那个最紧凑的圈。Graham 用角度排序画出一条优美的弧线，Andrew 用坐标排序踏出两条踏实的小路。你手上的场景，决定你请哪位老师出马。

HGraham=HAndrewH_{\text{Graham}} = H_{\text{Andrew}}
在无重复点、无浮点误差的理想条件下，两种算法输出的凸包完全一致。它们只是用不同的排序策略和扫描路径，抵达了同一个答案。
  1. 算法等价性两种算法求出的凸包顶点集合相同，差异仅在顶点排列的起点和方向（可能不同）。
    HGraham=HAndrewH_{\text{Graham}} = H_{\text{Andrew}}
  2. 选择偏好工程默认取 Andrew，因为其在常数因子、数值稳定性、代码简洁度上全面占优。
    prefer⇒Andrew Monotone Chain\text{prefer} \Rightarrow \text{Andrew Monotone Chain}
  3. 学习路径先掌握 Graham 理解极角排序思想，再切换到 Andrew 写出生产级代码，是推荐的学习曲线。
    learn:Graham→Andrew\text{learn}: \text{Graham} \to \text{Andrew}

AI 应用场景

自动驾驶中的障碍物包围圈

阶段：感知与路径规划

解决的问题：激光雷达扫描到障碍物的点云是散乱点，传统方法用矩形包围盒（AABB）框住障碍物会留下大量无效区域，尤其当障碍物群呈斜向分布时浪费严重。用凸包圈出点云的最外边界，可以得到贴合障碍物真实轮廓的最小凸多边形，为路径规划提供精准的安全边界。

具体案例：自动驾驶车辆在十字路口检测到前方 15 米处有 3 个行人，LiDAR 产生约 200 个点。系统用 Andrew 单调链对这些点求凸包，生成贴合行人群轮廓的蓝色包围圈。规划模块以此为障碍物区域计算绕行轨迹，凸包计算耗时不到 0.5 毫秒，远快于障碍物跟踪的帧间隔。

手势识别中的凸包与凸缺陷检测

阶段：特征提取

解决的问题：手部轮廓有很多凹陷（手指间的缝隙），直接用轮廓匹配难以区分手势。先对指尖点集求凸包，再计算凸包与手部轮廓之间的“凸缺陷”区域，凸缺陷的个数和深度能精确反映伸出了几根手指，这是识别剪刀、石头、布等手势的经典特征。

具体案例：智能电视的隔空手势控制中，摄像头捕获手部深度图，算法提取手部轮廓关键点后求凸包，检测出 4 个凸缺陷对应 4 根手指伸展。手势“握拳”对应 0 个凸缺陷，“张开手掌”对应 4 个凸缺陷，系统据此切换电视页面。

点云聚类后的簇边界生成

阶段：数据后处理与结果可视化

解决的问题：无人配送车的 3D 点云经过 DBSCAN 聚类后得到若干簇，每个簇需要生成紧凑边界用于后续障碍物匹配。凸包比 AABB 包围盒更贴合簇的实际形状，又比直接绘制所有点更轻量，是簇描述与可视化的标准选择。

具体案例：仓储机器人对仓库环境的实时点云聚类后，对每个簇用 Andrew 算法计算凸包并渲染为绿色半透明多边形，地图上清晰显示货架与行人的外轮廓，同时将凸包顶点作为特征送入分类器，区分“静态障碍物”与“移动行人”。

Python 演示

python68 行
import mathimport random  class Point:    def __init__(self, x, y):        self.x = x        self.y = y     def __repr__(self):        return f"({self.x}, {self.y})"  def cross(o, a, b):    """向量 oa 与 ob 的叉积正负判定方向"""    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)  def graham_scan(points):    """Graham 扫描：极角排序 + 栈式扫描"""    pts = sorted(points, key=lambda p: (p.y, p.x))    base = pts[0]    rest = sorted(pts[1:], key=lambda p: math.atan2(        p.y - base.y, p.x - base.x))    stack = [base]    for p in rest:        while len(stack) >= 2 and cross(                stack[-2], stack[-1], p) <= 0:            stack.pop()        stack.append(p)    return stack  def andrew_monotone_chain(points):    """Andrew 单调链：坐标排序 + 上下链构建"""    pts = sorted(points, key=lambda p: (p.x, p.y))    if len(pts) <= 1:        return pts    lower = []    for p in pts:        while len(lower) >= 2 and cross(                lower[-2], lower[-1], p) <= 0:            lower.pop()        lower.append(p)    upper = []    for p in reversed(pts):        while len(upper) >= 2 and cross(                upper[-2], upper[-1], p) <= 0:            upper.pop()        upper.append(p)    return lower[:-1] + upper[:-1]  def hull_key(hull):    return sorted((p.x, p.y) for p in hull)  if __name__ == "__main__":    random.seed(42)    pts = [Point(random.randint(0, 50), random.randint(0, 50))           for _ in range(20)]    hull_g = graham_scan(pts)    hull_a = andrew_monotone_chain(pts)    assert hull_key(hull_g) == hull_key(hull_a), "两算法结果不一致"    print("随机点:", pts)    print("Graham 凸包:", hull_g)    print("Andrew 凸包:", hull_a)    print("凸包顶点数:", len(hull_a))
目的：随机生成 20 个点，分别用 Graham 扫描与 Andrew 单调链求凸包，并断言两者结果完全一致，验证两种算法的等价性。
  1. key=lambda p: (p.y, p.x)先按 y 找最左下点作为旗手，这是 Graham 的第一步。
  2. math.atan2(p.y - base.y, p.x - base.x)计算每个点相对旗手的极角，按角度排队。
  3. cross(stack[-2], stack[-1], p) <= 0核心守卫：不是左转就弹出栈顶点，保证凸包严格凸。
  4. key=lambda p: (p.x, p.y)Andrew 直接按坐标排序，不需要任何三角函数。
  5. for p in reversed(pts)从右到左再扫一遍，构建上凸链。
  6. lower[:-1] + upper[:-1]拼接上下链时去掉首尾重复的端点，得到闭合凸包。

常见误区

误区我一直以为凸包就是用一个多边形把所有点围起来，所以多边形内部的点也应该算作凸包的“一部分”，求凸包就是保留所有点的坐标。

正解凸包只关心最外圈的边界顶点，内部点对凸包形状毫无贡献，就像围圈游戏里只有站在圈上的小朋友是“边界”，站在圈里的小朋友不会影响圈的形状。Graham 和 Andrew 的栈操作会把内部点全部弹出，最终栈里只留下凸包顶点。如果你需要保留所有点，那是在做“点集划分”，与凸包是两回事。

为何常见：生活直觉里“围住等于包含”，而数学上凸包是边界多边形而非集合本身，初学者容易把“被围住的对象”误当成凸包的元素。

误区Graham 扫描是教科书里第一个教的凸包算法，肯定比后出现的 Andrew 单调链更高效，生产环境应该优先选 Graham。

正解两者的渐近复杂度完全一样，都是 O(n log n)。真正的差别在常数因子：Graham 每个点都要算一次 atan2 反三角函数，这个函数可能比一次整数比较慢几十倍；Andrew 只需比较坐标。在十万级点集上，Andrew 通常比 Graham 快 2-3 倍，且代码更简洁。工程上默认选 Andrew 并非因为它“更高级”，而是因为它更省、更稳。

为何常见：教学顺序容易让人产生“先学到的就是最好的”的错觉，而忽略了算法分析中常数因子和工程实现成本的重要性。

误区既然 Graham 要按极角排序，那我用 math.atan2 算出每个点的角度再排序，结果一定是精确的，不需要担心任何问题。

正解atan2 返回的是浮点数，当两个点相对旗手的角度非常接近（例如 0.000001 弧度之差）时，浮点舍入可能让排序结果发生交换，导致扫描时叉积判断错乱，凸包出现“掉点”或“多余尖刺”。Andrew 用坐标排序完全没有这个隐患；若一定要用 Graham，可将 atan2 换成比较叉积的 comparator（即按象限 + 叉积排序），用整数运算避免浮点误差。

为何常见：现代 CPU 的浮点运算看起来“够精确”，但排序对顺序极其敏感，微小误差会被放大成结构性的错误，初学者很难意识到这一点。

误区即使所有点都在同一条直线上，凸包也应该是一个扁扁的多边形，顶点数应该接近点的个数。

正解当所有点共线时，凸包退化为一条线段，只有两个端点。Graham 和 Andrew 的弹栈条件（cross ≤ 0）会把中间的共线点全部剔除。如果你希望保留所有共线点，需要把弹栈条件改成 cross < 0，并且预先处理好重复点。理解退化的关键在于：凸包是“最小凸多边形”，而“退化多边形”允许退化为线段甚至点。

为何常见：头脑中的“凸多边形”模板默认至少有三条边，忽视了几何对象在退化情况下可以降维这一事实。

误区几何算法肯定要处理浮点数，整数坐标没法做叉积和角度计算，所以坐标类型必须是 float。

正解恰恰相反，整数坐标在凸包问题中是“最幸福”的输入。Andrew 算法全程只用加减乘法和比较，整数叉积零误差；Graham 虽然需要 atan2（浮点），但可以改成基于叉积的极角比较器来保持整数精度。浮点输入反而要引入 eps 阈值处理“几乎共线”的情况。很多竞赛题和高性能计算场景刻意用整数坐标来规避精度陷阱。

为何常见：受中学解析几何“坐标是实数”的惯性影响，忽略了计算机中整数运算的精确性和浮点运算的误差代价。

面试题

Q1. 点集凸包描述正确的是哪一项？

单选题 · easy

  • A.包含所有点的最小凸多边形← 正确答案
  • B.包含所有点的最小圆
  • C.所有点的外围矩形
  • D.连接最远两点间的线段

答案：A。凸包是包含点集的最小凸多边形，边界由最外层点构成，内部点不参与边界。最小圆（外接圆）不是多边形，AABB 矩形是轴对齐包围盒，连接最远两点的线段只覆盖两个点，都偏离凸包定义。可以用“最紧凑围圈”的比喻来记忆：圈只沿最外面的点绷紧。

Q2. Graham 扫描与 Andrew 单调链的时间复杂度均为多少？

单选题 · easy

  • A.O(n)
  • B.O(n log n)← 正确答案
  • C.O(n²)
  • D.O(log n)

答案：B。两种算法都包含一个排序步骤（Graham 极角排序、Andrew 坐标排序），排序是 O(n log n)；排序后的扫描阶段每个点至多入栈出栈一次，是 O(n)。因此总复杂度由排序主导，为 O(n log n)。这就像老师先花时间排队，再快速挨个检查，排队的开销决定了整体效率。

Q3. 叉积 cross(a,b) = a.x×b.y − a.y×b.x 的值为负，表示向量 b 相对向量 a 的方向是？

单选题 · mid

  • A.逆时针（左转）
  • B.顺时针（右转）← 正确答案
  • C.同向
  • D.反向

答案：B。叉积为正表示 b 在 a 的逆时针方向（左转），为负表示顺时针方向（右转），为零表示共线。想象方向盘：叉积为负就像向右打方向盘，车辆右转。这个方向判断是凸包扫描中“弹栈还是保留”的核心依据。

Q4. Graham 扫描中，选取的基准点（旗手）满足什么条件？

单选题 · mid

  • A.x 坐标最小的点
  • B.y 坐标最小的点，相同则取 x 最小← 正确答案
  • C.离原点最近的点
  • D.x 坐标最大的点

答案：B。Graham 选择 y 坐标最小的点作为基准，保证该点一定是凸包顶点；若 y 相同取 x 最小，是为了在“最底部一横排”中固定一个唯一的起点。选择基准后，其余点按相对它的极角排序，完成一圈扫描。最左下角的选择让基准天然位于凸包底边，不会被后续扫描弹出。

Q5. Andrew 单调链算法对点集进行排序的规则是？

单选题 · mid

  • A.按极角从小到大
  • B.按 x 坐标升序，相同则按 y 升序← 正确答案
  • C.按到原点距离从近到远
  • D.随机打乱

答案：B。Andrew 用坐标排序而非角度排序：先按 x 升序，x 相同按 y 升序。这样排序后的点天然形成从左到右的序列，之后从左到右构建下凸链、从右到左构建上凸链。坐标排序只涉及数值比较，避免了 atan2 的浮点误差，是 Andrew 数值稳健的根源。

Q6. 关于 Andrew 单调链的构建过程，下列说法正确的有哪些？

多选题 · mid

  • A.从左到右扫描构建下凸链← 正确答案
  • B.从右到左扫描构建上凸链← 正确答案
  • C.两条链拼接得到完整凸包← 正确答案
  • D.只需要扫描一次即可得到凸包

答案：ABC。Andrew 的凸包由下凸链和上凸链拼接而成：从左到右一路“左转上升”得到下凸链，从右到左一路“左转下降”得到上凸链，首尾相连闭合为凸包。选项 D 错误——只扫一次只能得到一条链，无法构成闭合多边形。这就像围圈分两趟：先围上半圈，再回头围下半圈。

Q7. 在大规模工程应用中，Andrew 通常比 Graham 更受推荐的根本原因是什么？

单选题 · hard

  • A.时间复杂度更低
  • B.不需要排序
  • C.坐标比较避免 atan2 浮点误差且常数因子更小← 正确答案
  • D.能得到不同结果的凸包

答案：C。两者渐近复杂度相同，都是 O(n log n)，因此 A 不对；两者都需要排序，B 不对；结果在理想条件下完全一致，D 不对。Andrew 的优势在于排序阶段只用坐标比较，而 Graham 需要算 atan2——一个昂贵的三角函举。在十万级点集上，Andrew 的常数因子通常只有 Graham 的一半甚至更低，且整数坐标下零误差。

Q8. 以下哪些场景会用到凸包算法？

多选题 · mid

  • A.自动驾驶中点云障碍物安全边界圈定← 正确答案
  • B.图像手势识别中的凸缺陷检测← 正确答案
  • C.点云聚类后的簇轮廓生成← 正确答案
  • D.数组快速排序

答案：ABC。凸包的典型应用包括：1）点云障碍物圈定边界，2）手部轮廓凸缺陷分析，3）聚类簇的可视化与特征描述。数组快速排序与凸包无关。记住一句话：凡是需要给“一堆散点画最紧凑外圈”的地方，都可能有凸包的身影。

Q9. Graham 扫描的 while 循环中，若叉积 cross(stack[-2], stack[-1], p) ≤ 0，应执行什么操作？

单选题 · hard

  • A.将 p 压入栈
  • B.弹出 stack[-1] 并继续检查← 正确答案
  • C.弹出 stack[-2] 并继续检查
  • D.结束扫描

答案：B。叉积 ≤ 0 表示从 stack[-2] 到 stack[-1] 再到 p 的转向为右转或共线，此时 stack[-1] 位于凸包内侧，不可能是边界顶点，因此弹出它，然后用新的栈顶两个点与新点 p 继续检查，直到满足左转再压入 p。这就像围圈时发现中间的小朋友“凹进圈里”了，老师请他出列，再检查前一位。

Q10. 当所有点都共线时，凸包的顶点个数是多少？

单选题 · easy

  • A.等于点数 n
  • B.2 个（两个端点）← 正确答案
  • C.1 个
  • D.0 个

答案：B。所有点共线时凸包退化为一条线段，只有两个端点。Graham 和 Andrew 的弹栈条件 cross ≤ 0 会剔除中间的共线点，仅保留首尾两个最远点。若想保留全部共线点，需将条件改为 cross < 0。这提醒我们：凸包是“最小凸多边形”，在极端情况下允许退化为线段。