凸包问题

发表于 | 分类于 | 阅读次数:
字数统计: 668 字

首先是凸包的定义，假设平面内有一些点，这些点中的一部分组成一个多边形，将其他的点都包含起来，当这个多边形是凸多边形的时候，我们就把他当成是一个凸包。
解决凸包问题有很多种算法，比较常见的有O(n^3)的暴力穷举算法以及O(nlogn)d的分治算法，这里讲的是一个时间复杂度为O(nlogn)的Graham扫描法。

算法

图中点的编号排序

首先建立一个极坐标系，选取所有点中最左下的点作为极点，将所有的点按照逆时针方向进行排序，角度相同的点，距离极点小的点排在前面。

依次寻找凸包上面的点

用栈来存储凸包的点（因为我们要读取栈顶的两个点，所以不用STL中的queue，而是用数组建栈)，依次考察排序好的点,判断是否弹出栈顶元素。考察规则：从栈中取出栈顶的两个点，两点连接成一条直线，然后判断当前考虑的点在再这条直线的左边还是右边（利用叉乘进行判断），在左边表示这个点在凸包上，入栈；在右边表示当前栈顶元素不是凸包上的点，将这个点出栈，然后继续取出栈顶的两个点进行考虑，直到可以将这个点加入栈中。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
struct point
{
	double x,y;
}p[maxn],t[maxn];
int n;    //点的个数

//得到相应的叉乘
double get_X(point a,point b,point c)        //ab到ac的叉乘计算
{
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

double len(point a,point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

bool cmp(point &a,point &b)
{
	double pp=get_X(p[0],a,b);
	if(pp>0) return true;
	if(pp<0) return false;
	return len(p[0],a)<len(p[0],b);
}

int Graham()     //返回凸包所含有的点的个数
{
	if(n<=2) return 0;
	else
	{
		for(int i=1;i<n;i++)     //找到起始点
		{
			if(p[i].x<p[0].x) swap(p[i],p[0]);
			else if(p[i].x==p[0].x && p[i].y<p[0].y) swap(p[i],p[0]);
		}
		sort(p+1,p+n,cmp);
		t[0]=p[0];
		t[1]=p[1];
		int top=1;    //栈顶位置
		for(int i=2;i<n;i++)
		{
			while(t>0 && get_X(t[top-1],t[top],p[i])<=0) top--;    //考虑的点在右侧的时候将栈顶的点弹出
			top++;
			t[top]=p[i];
		}
		return top;
	}
}