凸包（Convex Hull）

目录1、前言1.1什么是凸包2、算法基础铺垫2.1数学基础2.1.1叉积2.2数据结构基础2.2.1栈3、算法实现C3.1算法Andrew讲解3.2代码复现1、前言1.1什么是凸包给定二维平面上的点集凸包就是将最外层的点连接起来构成的凸多边形它能包含点集中所有的点2、算法基础铺垫2.1数学基础2.1.1叉积对于两个空间向量、叉积定义为当纵坐标时即当向量、处于同一平面时我们有此时我们可以知道若向量、共线若向量在向量的逆时针区域内若向量在向量的顺时针区域内2.2数据结构基础2.2.1栈此处略3、算法实现C3.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入栈得到【注】我们以点集中的遍历顺序为依据把一个凸包分成两部分即下凸壳和上凸壳凸包部分遍历顺序下凸壳从小到大上凸壳从大到小同理下凸壳上凸壳的求解流程图如下5678该点集的完整凸包求解完毕显然栈中有个元素则凸包上有个元素将点1重复置于栈内显然凸包周长为3.2代码复现例题【洛谷P2742】代码#includealgorithm #includeiostream #includeiomanip #includeutility #includecmath #includevector #includestack using namespace std; stackpairdouble, double st; vectorpairdouble, double point; bool Cross(pairdouble, double p1, pairdouble, double p2, pairdouble, 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) { pairdouble, double Pa st.top(); st.pop(); pairdouble, double Pb st.top(); pairdouble, 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) { pairdouble, double Pa st.top(); st.pop(); pairdouble, double Pb st.top(); pairdouble, 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) { pairdouble, double Pa st.top(); st.pop(); pairdouble, double Pb st.top(); pairdouble, double S point[i]; if (Cross(Pb, Pa, S)) continue; else { st.push(Pa); break; } }因此算法仅需在首次检测到凸性成立时退出循环break即可保证后续栈内点集的凸性无需回溯到底。