计算几何之凸包 Andrew算法代码模板与实现过程

﹏ヽ暗。殇╰゛Y 2022-11-06 08:59 180阅读 0赞

### 凸包的定义 ###

啥是凸包呢？我们不严谨地把这个词拆开来看，凸是指凸多边形的意思，包是指包住所有的点，因此凸包就是一个包住所有的点的凸多边形。简单来说，就是给你n个点，将这n个点的最外层的点连起来，将所有的点包在内部，这就是这n个点的凸包。可以想象这n个点都插了一根柱子，然后用一个橡皮筋将所有的柱子套住，然后再松开，橡皮筋所包住的图形就是这个凸多边形。

因此这里**凸包有一个性质**：凸包是平面中包括住所有点的多边形中周长最小的。

--------------------

### 凸包的求法 ###

凸包的求法有很多种，有Graham扫描法、Jarvis步进法等等，掌握一个就行，这里讲一个简单一点的方法Andrew算法。  
Andrew算法是Graham算法的改良版，好写一点，据说比Graham快一点。Andrew并不难，就两步：

**第一步：** 首先将所有点排个序，以x坐标为第一关键字，以y坐标为第二关键字。  
**第二步：** 从左至右维护上半部分的边界，从右至左维护下半部分的边界。

那么问题的关键就是如何维护来找到这个边界呢？这里我们用栈来维护，找上边界时，我们从第一个点也就是最左边的点出发，然后一次枚举下一个点，如果**下一个点在栈顶向量延长线的左侧**（注意这里栈顶向量指的是栈顶第二个点指向站顶点的向量），那么我们就**删去栈顶这个点**，**将新点入栈**；若下一个点在栈顶那个**向量延长线的右侧**，就不用将栈顶点出栈，**直接将新点入栈**即可。这样找到最右边的点时，上边界就确定完了。注意这里的**出栈是个while**过程，当栈顶点在左侧时，一直删掉栈顶点，直到在右侧为止。  
然后我们在按照相同的方法找下边界，我们从右向左找，若新点在栈顶向量延长线的左侧，则栈顶的点出栈，新点入栈；若新点在右侧，则不用出栈，直接将新点入栈即可。注意这里从右边往左边找的时候要直到最左边的点后才结束，也就是说也要判断最开始走的第一个点。具体如下图：  
![eg][]  
若出现第①种情况，就是求上边界时，下一个点在延长线的右侧时，直接将新点入栈；若是第②种情况，下一个点在延长线的左侧时，先将栈顶点出栈，再将新点入栈，因为上一个点一定会被新点包含进去。  
![eg][eg 1]

下边界同理，如上图存在两种情况，在右侧的直接入栈，左侧的先将栈顶点出栈再入栈。  
而到最后一定要将第一个点也就是出发点判断一下，不然有可能会出现下图这种情况：  
![eg][eg 2]  
凸包并不是黑色线条的图形，最后两条边应该是蓝色的边，这里就需要队出发点进行一次判断。

Andrew的步骤就是这两步，有些人会有疑问：如何判断一个点在该直线的左侧还是右侧，就是最常用的**向量法**，用两向量的[叉积正负值][Link 1]来判断在左侧还是在右侧，如图，我们只需要判断向量u和v的叉积，若为正，则在左侧；若为负，则在右侧。  
![eg][eg 3]  
那么如果下一个点就在延长线上，那么出不出栈就看题目要求了，若要找所有点，那就不出栈；若要找最少点数，那就出栈。

--------------------

### 代码模板 ###

#include<iostream>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int N = 10010;
    typedef pair<double,double> PDD;
    
    int n,top,stk[N];	//手动开一个栈stk，top是栈顶指针
    PDD p[N];		//用pair来存点
    bool used[N];		//判断某点是否被用过，当作边界
    
    double lens(PDD a,PDD b)	//求ab两点距离的函数
    { 
    	double x = a.first - b.first;
    	double y = a.second - b.second;
    	return sqrt(x*x + y*y);		//距离=根号下x、y坐标的平方和
    }
    
    PDD operator-(PDD a,PDD b)	//重载一下减号，可以用在两个pair间直接减
    { 
    	return { a.first-b.first,a.second-b.second};
    }
    
    double cross(PDD a,PDD b,PDD c)		//计算两个向量的叉积
    { 
    	PDD u,v;	//定义u、v两个向量
    	u = b - a,v = c - a;	//u是b-a，v是c-a
    	return u.first*v.second - v.first*u.second;	//叉积是x1*y2 - x2*y1
    }
    
    double andrew()		//andrew算法
    { 
    	sort(p,p+n);	//第一步先对点进行排序，pair存点的好处就是好排序
    	for(int i = 0;i < n;i++)	//从左往右维护每一个点
    	{ 
    		while(top >= 2 && cross(p[stk[top-1]],p[stk[top]],p[i]) > 0)	//如果栈里元素大于等于两个并且叉积大于0，注意是while
    		{ 
    			used[stk[top]] = 0;	//取消用了的标记
    			top--;	//先出栈
    		}
    		stk[++top] = i;		//新点入栈
    		used[i] = 1;		//标记该点用了
    	}
    	used[0] = 0;	//取消第一个点的标记，我们要再判断一下第一个点
    	for(int i = n-2;i >= 0;i--)	//从右往左维护每个点
    	{ 
    		if(used[i])	//如果某点用作上边界了，直接跳过
    			continue;
    		while(top >= 2 && cross(p[stk[top-1]],p[stk[top]],p[i]) > 0)	//如果栈里元素个数大于等于2且叉积大于0
    			top--;		//先出栈
    		stk[++top] = i;		//新点入栈
    	}
    
    	double perimeter = 0;	//周长
    	for(int i = 2;i <= top;i++)	//循环每个点，这里栈里是从1开始存的
    		perimeter += lens(p[stk[i]],p[stk[i-1]]);	//计算两点间距离，加和
    	return perimeter;	//返回周长
    }
    
    int main()
    { 
    	cin >> n;	//n个点
    	for(int i = 0;i < n;i++)
    	{ 
    		double x,y;
    		cin >> x >> y;		//输出n个点的坐标
    		p[i] = { x,y};
    	}
    
    	double ans = andrew();		//andrew算法求凸包
    	printf("%.2lf\n",ans);		//输出凸包周长
    
    	return 0;
    }

--------------------

### 经典例题 ###

题解传送门：[Acwing 2935：信用卡凸包][Acwing 2935]

[eg]: /images/20221023/87032b04b6054107890d1cafcc552873.png
[eg 1]: /images/20221023/c34d9bae38dc408fac9707fb3174f446.png
[eg 2]: /images/20221023/e449c000c5d04fb38b71d4c49beb613d.png
[Link 1]: https://blog.csdn.net/qq_45735851/article/details/114382634
[eg 3]: /images/20221023/d42c528e166f43c2bc7f0dc166b756fe.png
[Acwing 2935]: https://blog.csdn.net/qq_45735851/article/details/114625791