凸包（Convex Hull）

目录

1、前言

1.1什么是凸包

2、算法基础铺垫

2.1数学基础

2.1.1叉积

2.2数据结构基础

2.2.1栈

3、算法实现（C++）

3.1算法（Andrew）讲解

3.2代码复现

1、前言

1.1什么是凸包

给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边形，它能包含点集中所有的点

2、算法基础铺垫

2.1数学基础

2.1.1叉积

对于两个空间向量、，叉积定义为：

当纵坐标时，即当向量、处于同一平面时，我们有：

此时，我们可以知道：

若，向量、共线

若，向量在向量的逆时针区域内

若，向量在向量的顺时针区域内

2.2数据结构基础

2.2.1栈

此处略

3、算法实现（C++）

3.1算法（Andrew）讲解

文字说明：

（1）将点集中的所有点按横坐标升序排列（横坐标相同时，按纵坐标升序排列）

（2）遍历排序后的点集以构建下凸壳：当栈中点数不少于 2 时，每新入一个点，都通过叉积回溯检查栈顶点，剔除凹点或共线点，直至完成下凸壳构建

（3）遍历点集以构建上凸壳：以下凸壳完成时的栈大小为界，当栈中点数超过下凸壳的点数时，每新入一个点，都通过叉积回溯检查栈顶点，剔除凹点或共线点，直至完成上凸壳构建

图片说明：

如下，为一个点集，其中每个点都涵盖两个参数——其横纵坐标值，即该点在平面的坐标：

（1）根据各自横坐标进行排序

（2）将点1、点2入栈

（3）新入点3时，回溯时发现点2为凹点，于是将点2弹出，点3入栈

于是得到：

（4）新入点4，回溯检查，无误

（4）新入点5，回溯时发现点4为凹点，于是将点4弹出，点5入栈

于是得到：

继续回溯检查，发现点3为凹点，于是将点3弹出，点5入栈，得到：

【注】

我们以点集中的遍历顺序为依据把一个凸包分成两部分，即下凸壳和上凸壳

同理下凸壳，上凸壳的求解流程图如下：

（5）

（6）

（7）

（8）

该点集的完整凸包求解完毕

显然，栈中有个元素，则凸包上有个元素（将点1重复置于栈内）

显然，凸包周长为：

3.2代码复现

例题：【洛谷P2742】

代码：

#include<algorithm> #include<iostream> #include<iomanip> #include<utility> #include<cmath> #include<vector> #include<stack> using namespace std; stack<pair<double, double>> st; vector<pair<double, double>> point; bool Cross(pair<double, double> p1, pair<double, double> p2, pair<double, double> p3) { double cross = (p2.first - p1.first)* (p3.second - p1.second)- (p2.second - p1.second)* (p3.first - p1.first); return cross <= 0; } void Convex_Hull(int n) { sort(point.begin() + 1, point.end()); for (int i = 1; i <= n; ++i) { while (st.size() >= 2) { pair<double, double> Pa = st.top(); st.pop(); pair<double, double> Pb = st.top(); pair<double, double> S = point[i]; if (Cross(Pb, Pa, S)) continue; else { st.push(Pa); break; } } st.push(point[i]); } int tmp = st.size(); for (int i = n - 1; i >= 1; i--) { while (st.size() > tmp) { pair<double, double> Pa = st.top(); st.pop(); pair<double, double> Pb = st.top(); pair<double, double> S = point[i]; if (Cross(Pb, Pa, S)) continue; else { st.push(Pa); break; } } st.push(point[i]); } } double dis(double x1, double y1, double x2, double y2) { return sqrt(pow((x1 - x2), 2) + pow((y1 - y2), 2)); } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; double l = 0; double x; double y; point.emplace_back(0, 0); for (int i = 1; i <= n; i++) { cin >> x >> y; point.emplace_back(x, y); } Convex_Hull(n); while (st.size() > 1) { double x1 = st.top().first; double y1 = st.top().second; st.pop(); double x2 = st.top().first; double y2 = st.top().second; l += dis(x1, y1, x2, y2); } cout << fixed << setprecision(2) << l; return 0; }

3.3反思

（1）在 Andrew 单调链凸包算法中，栈内点集始终保持凸性单调链性质，即从栈底到栈顶，任意连续三点均满足左转（凸）关系。当处理新点时，若当前栈顶的三个点构成非左转（凹或共线）关系，则弹出栈顶点；当首次检测到栈顶三点满足左转（凸）性质时，即可停止回溯并退出循环。

这是因为：

此前的回溯操作已保证栈内剩余部分仍为合法的凸性单调链；

新点与当前栈顶两点构成凸关系后，其与更下方的栈内点的转向关系必然也满足凸性，无需继续回溯。

while (st.size() >= 2) { pair<double, double> Pa = st.top(); st.pop(); pair<double, double> Pb = st.top(); pair<double, double> S = point[i]; if (Cross(Pb, Pa, S)) continue; else { st.push(Pa); break; } }

因此，算法仅需在首次检测到凸性成立时退出循环（break），即可保证后续栈内点集的凸性，无需回溯到底。