凸包基础

定义

凸集与凸多边形

​若集合 $C$ 中任意两点之间的整条线段仍属于 $C$，则称 $C$ 为凸集。一个简单多边形连同其内部构成凸集时，称它为凸多边形。若边界表示保留共线中间点，某些内角可以等于 $\pi$；所有内角都在 $(0,\pi )$ 内描述的是所有顶点均为严格转向、且已删除边界共线中间点的规范表示。

凸包

​点集 $S$ 的凸包 $\mathrm{conv}(S)$ 是包含 $S$ 的最小凸集，也就是 $S$ 中有限个点的所有凸组合构成的集合。

​有限点集的凸包允许退化：空集的凸包按约定为空，单点的凸包是该点，两点或全体点共线时凸包是线段；只有存在至少三个不共线点时，凸包才是具有正面积的凸多边形。

极点

​对于凸集 $C$ 中的点 $p\in C$，若 $p=\lambda x+(1-\lambda )y$（$x,y\in C,0<\lambda <1$）只能在 $x=y=p$ 时成立，则称 $p$ 为 $C$ 的极点。有限点集凸包的极点正是凸包真正的顶点；凸包边内部的共线点不是极点。

​支持线使整个凸集位于它的一个闭半平面内。支持线与凸集的交集可能是一个极点，也可能是一整条边；只有交集为单点时，该点才是这个方向暴露出的极点。因此，仅知道“其余点位于同一个闭半平面”而允许其它点落在支持线上，不能作为极点的充分判据；若其它不同坐标的点都严格位于同一个开半平面，则该支持线只接触 $p$，足以证明 $p$ 是极点。

极边

​对于二维非退化凸包，极边是支持线与凸包相交得到的完整一维面。支持线上的共线中间点可以位于极边上，但极边的两个端点才是极点。

求凸包

极点法

​枚举每个点，判断每个点是否是极点。

​依据：先删除重复坐标。一个点不是极点，当且仅当它属于其它点的凸包。根据 Carathéodory 定理，平面中的该点一定属于至多三个其它点的凸包；这里必须检查闭三角形及其边界，并允许退化为线段，不能只检查严格的三角形内部。

​时间复杂度：$O(n^4)$。

极边法

​枚举两点确定一条直线，判断它是否是凸包的支持线。

​依据：其它点在该直线的同一个闭半平面内。若支持线上还有其它共线点，应取这一维面的两个最远端点作为规范凸包的极边，不能把支持线上的任意点对都输出成边。

​时间复杂度：$O(n^3)$。

增量法

​每次用一个点去更新凸包。

• 若点在凸包内，舍弃
• 若点在凸包外，找凸包的切线

​可推广至三维凸包、动态凸包。

​若当前凸包有 $h$ 个顶点，暴力判断点是否在凸包内需要 $h$ 次 to-left 测试，即 $O(h)$。

​找凸包的切线：切点的前驱和后继都在对应射线的同一侧，暴力需要 $O(h)$。

​依次插入 $n$ 个点、每次都暴力扫描当前凸包时，总时间复杂度为 $O(n^2)$。

​对于已经按逆时针顺序给出并完成规范化的静态凸多边形，预处理 $O(h)$ 后，单次点内判定或严格外点的切点查询都可以做到 $O(\log h)$。若输入是 $n$ 个无序点，另需 $O(n\log n)$ 构造凸包；这两部分复杂度不能混写成一次查询 $O(n\log n)$。

Gift wrapping

​先删除重复坐标，从一个确定的极点出发；每一步遍历其它点，选择下一条极边。

​若同一方向上有多个共线候选，只输出真正极点时必须选择离当前点最远者，否则会把边内部点当成下一顶点。空集和单点直接返回，全共线点集返回线段的两个端点。

​时间复杂度为 $O(nh)$，最坏为 $O(n^2)$，其中 $h$ 表示所选输出策略下的凸包顶点数。

​起点可以取字典序最小点等确定的坐标极值端点。若某一坐标极值由一整条极边取得，应再用另一坐标选择该极边的一个端点，而不是任取边内部点。

Graham scan

​基于极角排序的求凸包算法。下面默认返回按逆时针排列、首点不在末尾重复的真正极点，不保留极边内部的共线点。首先按坐标删除重复点；设去重后点数为 $m$，则 $m=0,1,2$ 时直接返回对应的退化凸包。

​算法流程：

• 取纵坐标最小、再取横坐标最小的点作为基点；
• 将其它点按相对基点的极角排序，同极角时按到基点的距离递增；
• 依次处理排序后的点。当栈顶两个点与新点不构成严格逆时针转向，即叉积小于等于 $0$ 时，弹出栈顶；
• 将新点入栈，最终得到只含真正极点的凸包。全共线输入最终只保留两个端点。

​若题目要求保留所有边界共线点，不能只把弹栈条件机械改成“叉积小于 $0$”：还要正确处理同极角组，并将最大极角的最后一组按距离反向；全共线输入也应单独约定输出顺序。

​时间复杂度：$O(n\log n)$。瓶颈为极角排序。

Andrew’s algorithm

​基于坐标字典序排序的求凸包算法。输出约定与 Graham scan 相同。

​以最左最右两点为界，凸包可以分为上凸包和下凸包两部分。

​算法流程：

• 对点集以横坐标为第一关键字、纵坐标为第二关键字排序，并删除重复坐标；
• 去重后点数为 $0,1,2$ 时直接返回；
• 正序遍历各点维护下凸壳，倒序遍历各点维护上凸壳。若只保留真正极点，当末尾两点与新点的叉积小于等于 $0$ 时弹出末点；
• 拼接上下凸壳时，各自删除一个重复端点，且最终不重复首点。全共线输入返回字典序最小、最大的两个端点。

​若要保留边界共线点，通常只在叉积小于 $0$ 时弹出，但必须特判全共线输入，避免上下凸壳把中间点重复输出。

​时间复杂度：$O(n\log n)$。瓶颈为排序。

凸包进阶

凸包二分

判断点是否在凸多边形中

​以下假设凸多边形有 $h\ge 3$ 个顶点，已经删除冗余共线点并按逆时针顺序排列，且默认边界算作内部。退化情况应单独处理：空凸包不包含任何点，单点只包含自身，线段只包含位于该闭线段上的点。

按横坐标（x）二分：

​确定最左、最右端点 $L,R$，将边界分成横坐标单调的上凸壳和下凸壳。先排除横坐标位于 $[x_L,x_R]$ 外的查询点，再用 $\mathrm{cross}(R-L,p-L)$ 的符号选择对应凸壳，在该链上二分找到查询点横坐标所在的相邻顶点区间，并通过方向测试判断是否越过边界。也可以分别二分两条链；最左、最右点不唯一、查询点落在弦 $LR$ 上或存在竖直极边时，需要按既定边界语义处理。

​单次查询的时间复杂度为 $O(\log h)$。

利用极角序二分：

​固定一个顶点 $v_0$，先用射线 $v_0{v}_1$ 和 $v_0{v}_{h-1}$ 判断查询点是否位于整个扇形内，再按 $\mathrm{cross}(v_i-v_0,p-v_0)$ 的符号二分找到相邻射线 $v_0{v}_i,v_0{v}_{i+1}$，最后判断查询点是否位于闭三角形 $v_0{v}_i{v}_{i+1}$ 中。

​已有规范凸多边形时，检查或建立上述索引需要 $O(h)$，单次查询为 $O(\log h)$，$q$ 次查询为 $O(h+q\log h)$。若从 $n$ 个无序点开始，还要另加一次 $O(n\log n)$ 的凸包构造，不能把它计入每次查询。

判断直线是否与凸多边形相交

​设直线为 $l(t)=p+tv$，其中方向向量 $v\ne 0$，对凸多边形顶点定义 $f_i=\mathrm{cross}(v,v_i-p)$。直线与闭凸多边形相交，当且仅当 $min{f}_i\le 0\le max{f}_i$。利用凸多边形边向量的循环极角序，可以分别查询这个线性函数在两个相反方向上的支撑极值；极值形成相等平台时，返回平台任一端点即可。

​规范化预处理后，单次查询为 $O(\log h)$；若相切也算相交，等号必须保留。点或线段等退化凸包需单独处理。

过一点求凸多边形切线

​本节讨论从严格位于凸多边形外部的点 $p$ 引出的两条支撑切线。若 $p$ 位于内部，则不存在经过 $p$ 的支持线；若 $p$ 位于边界上，可能得到所在边的支持线，或在顶点处得到一族支持线，需要另行约定返回协议，不能简单归入“没有切线”。

​对于严格外点，切点处相邻顶点位于射线 $p{v}_i$ 的同一侧。沿规范的循环凸多边形考察相邻顶点相对射线的方向符号，两个切点对应这一循环序列的两个转折位置，可以通过循环二分分别找到。

​该 $O(\log h)$ 查询要求顶点已经按逆时针顺序排列，并且已经删除冗余共线点；若允许切线与整条边重合，还要规定返回边的哪个端点。方向为 $0$、查询点位于边界以及 $h<3$ 时均需单独处理。规范化需要 $O(h)$，之后每个严格外点的两切点查询为 $O(\log h)$。

动态凸包（不删）

​只增动态凸包维护一个数据结构，支持以下两个操作：

• 修改：在当前点集中加入一个点
• 询问：查询一点是否在当前点集的凸包内

​分别使用按横坐标有序的结构维护上凸壳和下凸壳，才能完成整个凸包的点内查询。相同横坐标下，上凸壳只保留必要的最高候选，下凸壳只保留必要的最低候选；重复点和边界共线点采用与静态凸包一致的删除策略。

​初始化时应单独处理空集、单点和线段。新点位于当前横坐标范围之外时，某一侧可能没有前驱或后继，应按凸壳端点插入处理，不能假设两个邻居始终存在。

• 询问：分别在上下凸壳中二分相邻点，单次最坏时间为 $O(\log h)$；
• 修改：二分找到新点横坐标附近的前驱、后继。若新点不可能成为该凸壳的顶点则舍弃；否则插入，并向左右连续删除所有破坏凸性的旧顶点。

​设某次插入共删除 $k$ 个旧顶点。使用邻接迭代器，并采用类似 std::set::erase(iterator) 的摊还常数时间删除接口时，本次代价为 $O(\log h+k)$，单次最坏可能达到 $O(h)$。若数据结构的迭代器删除不是这一复杂度，或每删除一个点都按键重新查找，则还会多出相应的对数因子。

​一个点一旦从不断扩大的凸包中被删除，之后不会重新成为极点，所以每个点在每条凸壳上至多被删除一次。连续插入 $N$ 个点时，总删除次数为 $O(N)$，总时间为 $O(N\log N)$，即每次插入摊还 $O(\log N)$，而不是单次最坏 $O(\log N)$。若另有 $q$ 次点内查询，总复杂度为 $O((N+q)\log N)$。