凸包
二维凸包
定义
凸多边形
凸多边形是指所有内角大小都在
凸包
在平面上能包含所有给定点的最小凸多边形叫做凸包。
其定义为：对于给定集合
实际上可以理解为用一个橡皮筋包含住所有给定点的形态。
凸包用最小的周长围住了给定的所有点。如果一个凹多边形围住了所有的点，它的周长一定不是最小，如下图。根据三角不等式，凸多边形在周长上一定是最优的。
Andrew 算法求凸包
常用的求法有 Graham 扫描法和 Andrew 算法，这里主要介绍 Andrew 算法。
性质
该算法的时间复杂度为
过程
首先把所有点以横坐标为第一关键字，纵坐标为第二关键字排序。
显然排序后最小的元素和最大的元素一定在凸包上。而且因为是凸多边形，我们如果从一个点出发逆时针走，轨迹总是“左拐”的，一旦出现右拐，就说明这一段不在凸包上。因此我们可以用一个单调栈来维护上下凸壳。
因为从左向右看，上下凸壳所旋转的方向不同，为了让单调栈起作用，我们首先 升序枚举 求出下凸壳，然后 降序 求出上凸壳。
求凸壳时，一旦发现即将进栈的点（
通常情况下不需要保留位于凸包边上的点，因此上面一段中
实现
=== "C++"
```cpp
// stk[] 是整型，存的是下标
// p[] 存储向量或点
tp = 0; // 初始化栈
std::sort(p + 1, p + 1 + n); // 对点进行排序
stk[++tp] = 1;
// 栈内添加第一个元素，且不更新 used，使得 1 在最后封闭凸包时也对单调栈更新
for (int i = 2; i <= n; ++i) {
while (tp >= 2 // 下一行 * 操作符被重载为叉积
&& (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0)
used[stk[tp--]] = 0;
used[i] = 1; // used 表示在凸壳上
stk[++tp] = i;
}
int tmp = tp; // tmp 表示下凸壳大小
for (int i = n - 1; i > 0; --i)
if (!used[i]) {
// ↓求上凸壳时不影响下凸壳
while (tp > tmp && (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0)
used[stk[tp--]] = 0;
used[i] = 1;
stk[++tp] = i;
}
for (int i = 1; i <= tp; ++i) // 复制到新数组中去
h[i] = p[stk[i]];
int ans = tp - 1;
```=== "Python"
```python
stk = [] # 是整型，存的是下标
p = [] # 存储向量或点
tp = 0 # 初始化栈
p.sort() # 对点进行排序
stk[tp] = 1
tp = tp + 1
# 栈内添加第一个元素，且不更新 used，使得 1 在最后封闭凸包时也对单调栈更新
for i in range(2, n + 1):
while tp >= 2 and (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0:
# 下一行 * 操作符被重载为叉积
used[stk[tp]] = 0
tp = tp - 1
used[i] = 1 # used 表示在凸壳上
stk[tp] = i
tp = tp + 1
tmp = tp # tmp 表示下凸壳大小
for i in range(n - 1, 0, -1):
if used[i] == False:
# ↓求上凸壳时不影响下凸壳
while tp > tmp and (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0:
used[stk[tp]] = 0
tp = tp - 1
used[i] = 1
stk[tp] = i
tp = tp + 1
for i in range(1, tp + 1):
h[i] = p[stk[i]]
ans = tp - 1
```根据上面的代码，最后凸包上有
三维凸包
基础知识
圆的反演：反演中心为
，反演半径为 ，若经过 的直线经过 , ，且 ，则称 、 关于 互为反演。
过程
求凸包的过程如下：
- 首先对其微小扰动，避免出现四点共面的情况。
- 对于一个已知凸包，新增一个点
- 将光的可见面删去，并新增由其分割棱与
模板题
重复上述过程即可得到答案。
练习
参考资料与注释
Footnotes
贡献者：@Menci@Jimmy@minakokojima@F1shAndCat@Shuzhou@Ir1d@WenzelTian@livrth@mgt@ksyx@sshwy@H-J-Granger@Henry-ZHR@Sshwy@ouuan@wjy-yy
本页面最近更新：2/3/2023, 12:00:00 AM，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用