凸包

凸包

凸包(Convex Hull)是一个计算几何(图形学)中的概念。
在一个实数向量空间V中,对于给定集合X,所有包含X的凸集的交集S被称为X的凸包。X的凸包可以用X内所有点(X1,…Xn)的凸组合来构造.
在二维欧几里得空间中,凸包可想象为一条刚好包著所有点的橡皮圈。
用不严谨的话来讲,给定二维平面上的点集,凸包就是将最外层的点连接起来构成的凸多边形,它能包含点集中所有的点。(来源于百度百科)

凸包是计算几何题目中经常出现的概念,一般形式为给你 $ n $ 个点,求这些点所构成的凸包的面积。

这张动图是求凸包的过程。

求凸包的基本顺序为:

  1. 找到凸包上的一个点,一般为x坐标最小的点。
  2. 将找到的点设为原点,根据极角排序方式将剩余的点进行排序
  3. 循环找凸包上的点
    1. 如果当前点比上一个点更可能是凸包上的点,那么就覆盖上一个点,更新为当前点。
    2. 如果当前点没有上一个点适合当凸包上的点,那么就先放进凸包集合中,继续寻找下一个点。
  4. 循环结束。

关于当前点是否更有可能是凸包上的点,用下面的几张图来讲解:

当前凸包内有三个点v0,v1,v2,接下来判断v3的时候,我们需要对它进行判断:

$v1$ 与 $v2,v3$ 相连,判断两条线的夹角的方向,如果是逆时针方向,那么就可以放入凸包集合中:

接下来同样的办法判断v4:

如果是顺时针方向,那么 $v4$ 就优于 $v3$ ,我们删去 $v3$ ,接下来继续判断:

逆时针,所以可以放入图包集合:

之后一直重复这个过程即可。

代码如下:

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
struct node{
int x,y;
int pos;
}p[maxn],q[maxn];
int n,l;
node getmag(node a,node b){//计算边 表示从a->b的向量
node s;
s.x=b.x-a.x;
s.y=b.y-a.y;
return s;
}
int multiX(node a,node b){//叉乘的正负代表两条直线夹角的顺逆
return a.x*b.y-a.y*b.x;
}
bool cmp(node a,node b){//根据极角排序
return multiX(getmag(p[1],a),getmag(p[1],b))>0;
}
void graham(){
int id=1;
for(int i=2;i<=n;i++){//找出最开始的一个点
if(p[i].x<p[id].x || (p[i].x==p[id].x && p[i].y<p[id].y)) id=i;
}
if(id!=1) swap(p[id],p[1]);

sort(p+2,p+n+1,cmp);//极角排序
q[++l]=p[1];//p: 所有点集合 q: 凸包点集合
for(int i=2;i<=n;i++){
//如果夹角是顺时针方向,那么就可以取代
while(l>=2 && multiX(getmag(q[l-1],p[i]),getmag(q[l-1],q[l]))>=0) l--;
q[++l]=p[i];
}
}
感谢您的支持
-------------本文结束感谢您的阅读-------------