凸包（convex hull）简述

凸包（convex hull）简述

这里主要介绍二维凸包，二维凸多边形是指所有内角都在$[0,\Pi ]$范围内的简单多边形。

凸包是指在平面上包含所有给定点的最小凸多边形。

数学定义：对于给定集合$X$，所有包含 $X$ 的凸集的交集 $S$ 被称为 $X$ 的 凸包。

凸包算法

Andrew 算法求凸包

Andrew 算法（也叫单调链算法）用于求解平面上一组点集的凸包，它的基本思想是先将点集按照横坐标（若横坐标相同则按照纵坐标）进行排序，然后通过遍历排序后的点依次构建凸包的上链和下链，最终合并得到完整的凸包。该算法的时间复杂度为 $O(n\log n)$，其中 $n$ 为待求凸包点集的大小。

算法过程：

1. 将点集$P$ 按照横坐标升序排序，若横坐标相同则按照纵坐标升序排序;
2. 构建凸包的下链，从左到右遍历排序后的点集，利用一个栈（可以用数组模拟）来维护凸包的下链。对于每个点，不断检查栈顶的两个点与当前点所构成的向量是否满足 “左转” 条件（通过叉积判断），若不满足则弹出栈顶元素，直到满足条件或者栈中元素个数小于 2，然后将当前点压入栈中;
3. 构建凸包的上链，从右到左遍历排序后的点集（不包括已经在凸包下链中的点），同样利用栈来维护凸包的上链，执行和构建下链类似的操作，不断检查栈顶的两个点与当前点所构成的向量是否满足 “左转” 条件，若不满足则弹出栈顶元素，直到满足条件或者栈中元素个数小于2 ，然后将当前点压入栈中;
4. 将凸包的下链（除了最后一个点，因为它和上链的第一个点重复）和凸包的上链合并起来，得到最终的凸包。

上图为排序好的点集

上图为从左到右构建下凸包的过程

上图为从右到左构建上凸包的过程，最后红色实线和黑色实线组成凸包。

Graham 扫描法

与 Andrew 算法相同，Graham 扫描法的时间复杂度为 $O(n\log n)$，复杂度瓶颈也在于对所有点排序。

算法过程：

1. 找到基点（最左下角的点）：遍历点集，找出纵坐标最小的点，如果有多个纵坐标最小的点，则选择其中横坐标最小的那个点作为基点。这个基点是后续极角排序以及构建凸包的重要参考点。
2. 极角排序：计算除基点外其他各点相对于基点的极角，按照极角从小到大对这些点进行排序（若极角相同，则按照距离基点的距离从小到大排序）。通过极角排序能确定点集的一种相对顺序，方便后续扫描构建凸包。
3. 扫描构建凸包：利用一个栈来维护凸包的点。先将基点和排序后的第一个点压入栈中，然后从第二个点开始依次遍历排序后的点集，对于每个点，检查栈顶两点与当前点所构成的向量是否满足 “左转” 条件（通过叉积判断），若不满足则弹出栈顶元素，直到满足左转条件或者栈中元素个数小于 2，之后将当前点压入栈中。最终栈中存储的点就是凸包的顶点。

参考

1. https://blog.csdn.net/Zhang_Chen_/article/details/102417129
2. https://zhuanlan.zhihu.com/p/340442313