凸包问题

首先是凸包的定义,假设平面内有一些点,这些点中的一部分组成一个多边形,将其他的点都包含起来,当这个多边形是凸多边形的时候,我们就把他当成是一个凸包。
解决凸包问题有很多种算法,比较常见的有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;
}
}
  • 本文作者: Sixzeroo
  • 本文链接: https://www.liuin.cn/2017/04/17/凸包问题/
  • 发布时间: 2017年4月17日 - 09时04分
  • 最后更新: 2017年4月17日 - 10时04分
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!