凸包
二维凸包
定义
凸多边形
凸多边形是指所有内角大小都在 [0,𝜋][0,π]
范围内的 简单多边形 ．
凸包
在平面上能包含所有给定点的最小凸多边形叫做凸包．
其定义为：对于给定集合 𝑋X，所有包含 𝑋X 的凸集的交集 𝑆S 被称为 𝑋X 的 凸包 ．
实际上可以理解为用一个橡皮筋包含住所有给定点的形态．
凸包用最小的周长围住了给定的所有点．如果一个凹多边形围住了所有的点，它的周长一定不是最小，如下图．根据三角不等式，凸多边形在周长上一定是最优的．
Andrew 算法求凸包
常用的求法有 Graham 扫描法和 Andrew 算法，这里主要介绍 Andrew 算法．
性质
该算法的时间复杂度为 𝑂(𝑛log𝑛)O(nlogn)，其中 𝑛n 为待求凸包点集的大小，复杂度的瓶颈在于对所有点坐标的双关键字排序．
过程
首先把所有点以横坐标为第一关键字，纵坐标为第二关键字排序．
显然排序后最小的元素和最大的元素一定在凸包上．而且因为是凸多边形，我们如果从一个点出发逆时针走，轨迹总是「左拐」的，一旦出现右拐，就说明这一段不在凸包上．因此我们可以用一个单调栈来维护上下凸壳．
因为从左向右看，上下凸壳所旋转的方向不同，为了让单调栈起作用，我们首先 升序枚举 求出下凸壳，然后 降序 求出上凸壳．
求凸壳时，一旦发现即将进栈的点（𝑃P）和栈顶的两个点（𝑆1,𝑆2S1,S2，其中 𝑆1S1 为栈顶）行进的方向向右旋转，即叉积小于 00：←←←←←←→𝑆2𝑆1 ×←←←←←→𝑆1𝑃 <0S2S1→×S1P→<0，则弹出栈顶，回到上一步，继续检测，直到 ←←←←←←→𝑆2𝑆1 ×←←←←←→𝑆1𝑃 ≥0S2S1→×S1P→≥0 或者栈内仅剩一个元素为止．
通常情况下不需要保留位于凸包边上的点，因此上面一段中 ←←←←←←→𝑆2𝑆1 ×←←←←←→𝑆1𝑃 <0S2S1→×S1P→<0 这个条件中的「<<」可以视情况改为 ≤≤，同时后面一个条件应改为 >>．
实现
代码实现
C++Python
---|---
---|---
根据上面的代码，最后凸包上有 𝑎𝑛𝑠ans 个元素（额外存储了 11 号点，因此 ℎh 数组中有 𝑎𝑛𝑠 +1ans+1 个元素），并且按逆时针方向排序．周长就是
𝑎𝑛𝑠∑𝑖=1∣←←←←←←←←→ℎ𝑖ℎ𝑖+1∣∑i=1ans|hihi+1→|
Graham 扫描法
性质
与 Andrew 算法相同，Graham 扫描法的时间复杂度为 𝑂(𝑛log𝑛)O(nlogn)，复杂度瓶颈也在于对所有点排序．
过程
首先找到所有点中，纵坐标最小的一个点 𝑃P．根据凸包的定义我们知道，这个点一定在凸包上．然后将所有的点以相对于点 P 的极角大小为关键字进行排序．
和 Andrew 算法类似地，我们考虑从点 𝑃P 出发，在凸包上逆时针走，那么我们经过的所有节点一定都是「左拐」的．形式化地说，对于凸包逆时针方向上任意连续经过的三个点 𝑃1,𝑃2,𝑃3P1,P2,P3，一定满足 ←←←←←←→𝑃1𝑃2 ×←←←←←←→𝑃2𝑃3 ≥0P1P2→×P2P3→≥0．
新建一个栈用于存储凸包的信息，先将 𝑃P 压入栈中，然后按照极角序依次尝试加入每一个点．如果进栈的点 𝑃0P0 和栈顶的两个点 𝑃1,𝑃2P1,P2（其中 𝑃1P1 为栈顶）行进的方向「右拐」了，那么就弹出栈顶的 𝑃1P1，不断重复上述过程直至进栈的点与栈顶的两个点满足条件，或者栈中仅剩下一个元素，再将 𝑃0P0 压入栈中．
代码实现
---|---
## 闵可夫斯基和
### 定义
点集 𝑃P 和点集 𝑄Q 的闵可夫斯基和 𝑃 +𝑄P+Q 定义为 𝑃 +𝑄 ={𝑎 +𝑏|𝑎 ∈𝑃,𝑏 ∈𝑄}P+Q={a+b|a∈P,b∈Q}，即把点集 𝑄Q 中的每个点看做一个向量，将点集 𝑃P 中每个点沿这些向量平移，最终得到的结果的集合就是点集 𝑃 +𝑄P+Q．此处仅讨论 **凸包** 的闵可夫斯基和．
例如：对于点集 𝑃 ={(0,0),( −3,3),(2,1)}P={(0,0),(−3,3),(2,1)} 和 点集 𝑄 ={(0,0),( −1,3),(1,4),(2,2)}Q={(0,0),(−1,3),(1,4),(2,2)}，
将 𝑃P 沿 𝑄Q 的每个向量平移：
不难发现新图形也是一个 **凸包** ：
### 性质
1. 若点集合 𝑃P，𝑄Q 为凸集，则其闵可夫斯基和 𝑃 +𝑄P+Q 也是凸集．
证明
设 𝑒,𝑓 ∈𝑃 +𝑄e,f∈P+Q，有 𝑎,𝑏 ∈𝑃a,b∈P，𝑐,𝑑 ∈𝑄c,d∈Q 且 𝑒 =𝑎 +𝑐,𝑓 =𝑏 +𝑑e=a+c,f=b+d，则对任意 𝑡 ∈[0,1]t∈[0,1] 均有：
𝑡𝑒+(1−𝑡)𝑓=𝑡(𝑎+𝑐)+(1−𝑡)(𝑏+𝑑)=(𝑡𝑎+(1−𝑡)𝑏)+(𝑡𝑐+(1−𝑡)𝑑)∈𝑃+𝑄.te+(1−t)f=t(a+c)+(1−t)(b+d)=(ta+(1−t)b)+(tc+(1−t)d)∈P+Q.
证毕．
1. 若点集 𝑃P，𝑄Q 为凸集，则其闵可夫斯基和 𝑃 +𝑄P+Q 的边集是由凸集 𝑃P，𝑄Q 的边按极角排序后连接的结果．
证明
不妨假设凸集 𝑃P 中任意一条边的斜率与 𝑄Q 中任意一条边的斜率均不相同．将坐标系进行旋转，使得 𝑃P 上的一条边 𝑋𝑌XY 与 𝑥x 轴平行且在最下方．
设此时 𝑄Q 中最低的点 𝑈U，𝑃 +𝑄P+Q 的 **最低** 且 **靠左** 的点 𝐴A．
可知 ⃗𝐴 =⃗𝑋 +⃗𝑈A→=X→+U→，所以 𝐴A 必然在 𝑃 +𝑄P+Q 的边界上．
同理，𝑃 +𝑄P+Q 中 **最低** 且 **靠右** 的点 𝐵B 有 ⃗𝐵 =⃗𝑌 +⃗𝑈B→=Y→+U→，也必然在 𝑃 +𝑄P+Q 的边界上．
因此，有 ⃗𝐴𝐵 =⃗𝑋𝑌 +⃗𝑈AB→=XY→+U→．
若按顺序进行旋转，则结果连续的构成了 𝑃 +𝑄P+Q 中的每条边．
证毕．
### 实现
我们可以根据性质 2，将凸集 𝑃,𝑄P,Q 极角排序，得到它们在 𝑃 +𝑄P+Q 上的出现顺序，把 𝑃1 +𝑄1P1+Q1 看做 𝑃 +𝑄P+Q 的起点，然后用类似 **归并** 的做法依次放边即可．
时间复杂度：𝑂(𝑛 +𝑚)O(n+m)
实现
---|---
例题
[例题 [JSOI2018] 战争](https://loj.ac/p/2549)
有两个凸包 𝑃,𝑄P,Q，平移 𝑞q 次 𝑄Q，问每次移动后是否有交点．1 ≤𝑛,𝑚 ≤105,1 ≤𝑞 ≤1051≤n,m≤105,1≤q≤105．
实现
---|---
## 三维凸包
### 基础知识
> 圆的反演：反演中心为 𝑂O，反演半径为 𝑅R，若经过 𝑂O 的直线经过 𝑃P,𝑃′P′，且 𝑂𝑃 ×𝑂𝑃′ =𝑅2OP×OP′=R2，则称 𝑃P、𝑃′P′ 关于 𝑂O 互为反演．
### 过程
求凸包的过程如下：
* 首先对其微小扰动，避免出现四点共面的情况．
* 对于一个已知凸包，新增一个点 𝑃P，将 𝑃P 视作一个点光源，向凸包做射线，可以知道，光线的可见面和不可见面一定是由若干条棱隔开的．
* 将光的可见面删去，并新增由其分割棱与 𝑃P 构成的平面． 重复此过程即可，由 [Pick 定理](../pick/)、欧拉公式（在凸多面体中，其顶点 𝑉V、边数 𝐸E 及面数 𝐹F 满足 𝑉 −𝐸 +𝐹 =2V−E+F=2）和圆的反演，复杂度 𝑂(𝑛2)O(n2)．1
### 模板题
[P4724【模板】三维凸包](https://www.luogu.com.cn/problem/P4724)
重复上述过程即可得到答案．
代码实现
---|---
练习
参考资料与注释
- 三维凸包学习小记 ↩
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Ir1d, H-J-Granger, StudyingFather, countercurrent-time, Enter-tainer, NachtgeistW, CCXXXI, ksyx, sshwy, Tiphereth-A, AngelKitty, c-forrest, cjsoft, diauweb, Early0v0, ezoixx130, GekkaSaori, Henry-ZHR, iamtwz, Konano, LovelyBuggies, lychees, Makkiy, mgt, minghu6, P-Y-Y, PotassiumWings, SamZhangQingChuan, Suyun514, weiyong1024, Xeonacid, xglight, AtomAlpaca, F1shAndCat, GavinZhengOI, Gesrua, gi-b716, gitbugfsj, kxccc, livrth, megakite, Menci, ouuan, Peanut-Tang, shawlleyw, shuzhouliu, Sshwy, SukkaW, wjy-yy 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用