凸包基础
定义
凸多边形
所有内角大小都在 $[0,\pi]$ 范围内的简单多边形。
凸包
在平面上能包含所有给定点的最小凸多边形。
可以理解为用一个橡皮筋包含住所有给定点的形态。
性质：凸包用最小的周长围住了所有点。
极点
凸包的顶点
性质：若点 P 是点集 S 的一个极点，那么存在一条经过点 P 的直线 l，使得点集 S 中除了 P 的所有点都在 l 的同一侧。
极边
凸包的边
性质：点集中除了极边上的点外都在极边所在直线的同一侧。
求凸包
极点法
枚举每个点，判断每个点是否是极点。
依据：将凸包以凸包内一点为顶点进行三角剖分，非极点一定落在某个三角形内部，枚举另外三个点组成三角形，若点落在了某个三角形内部，则它不是极点。
时间复杂度：$O(n^4)$。
极边法
枚举两点组成的边，判断它是否是极边。
依据：其它点在极边所在直线的同一侧。
时间复杂度：$O(n^3)$。
增量法
每次用一个点去更新凸包。
- 若点在凸包内，舍弃
- 若点在凸包外，找凸包的切线
可推广至三维凸包、动态凸包。
判断点在凸包内：$n$ 次 to-left 测试。$O(n)$。
找凸包的切线：前驱和后继都在射线的同一侧。暴力 $O(n)$。
时间复杂度：$O(n^2)$。
判断点在凸包内和找凸包的切线均存在 $O(n\log n)$ 做法。
Gift wrapping
从一条极边出发遍历其它点找到下一条极边。
时间复杂度：$O(nh)$，最坏 $O(n^2)$，$h$ 表示凸包的极点数。
起点的确定：
点集中最左/右/上/下的点一定是凸包的极点（若最左/右/上/下的点不唯一，则是极边上的点，此时取另一个方向上坐标最大/小的点）。
Graham scan
基于极角排序的求凸包算法。
算法流程：
- 以最左下角的点为极点，进行极角排序。
- 将极点与极点的下一个点入栈。
- 对于要入栈的下一个点，如果从栈顶连向该点需要顺时针旋转，则弹出栈顶。
- 重复 3，直到从栈顶连向该点需要逆时针旋转。
- 将下一个点入栈，回到 3。
时间复杂度：$O(n\log n)$。瓶颈为极角排序。
Andrew’s algorithm
基于横坐标（x）排序的求凸包算法。
以最左最右两点为界，凸包可以分为上凸包和下凸包两部分。
算法流程：
- 对点集以横坐标（x）为第一关键字，纵坐标（y）为第二关键字排序。
- 正序遍历每个点，用栈维护下凸包。
- 倒序遍历每个点，用栈维护上凸包。
栈的维护方式与 Graham scan 一致。
时间复杂度：$O(n\log n)$。瓶颈为排序。