0%

计算几何/凸包/安德鲁

发表于 更新于 分类于

计算几何/凸包/安德鲁算法

先说一下凸包是啥

抽象解释：在一个实数向量空间V中，对于给定集合X，所有包含X的凸集的交集S被称为X的凸包。X的凸包可以用X内所有点(X1，…Xn)的凸组合来构造（来自百度百科）；

简单理解：对于一个平面空间上的点集，其中的一些点总可以构成一个凸多边形，这个多边形（包括边界）包含了改点集内所有的点，这个凸多边形就是凸包。
如图：
在这里插入图片描述
在计算几何领域，有很多个求凸包的方法，这里主要讲比较容易掌握安德鲁算法（Andrew’s Algorithm)（因为我菜…)

算法基本思路

1.将给定的集合的点按X坐标升序排序，X相同则按Y升序排序；

2.创建凸包上部：
将排序后的点按从小到大顺序加入凸包A，若新加入的点使凸包A不再是凸多边形，则逆序删除之前加入的点，直到重新变成凸多边形；
3.创建凸包下部：
将排序后的点按从大到小顺序加入凸包B，若新加入的点使凸包B不再是凸多边形，则逆序删除之前加入的点，直到重新变成凸多边形；

（显然排序后的第一个点和最后一个点必定在凸包上）
注：
若a X b > 0，表示a在b的顺时针方向上
若a X b < 0，表示a在b的逆时针方向上
若a X b == 0，表示a与b共线，但不确定方向是否相同

下面用图解说明一下安德鲁算法:

第一步，将最开始的两个点加入凸包。
在这里插入图片描述
第二步，按照顺序选定点Si（不入凸包），若Si在凸包的倒数第二个点和倒数第一个点构成的向量的逆时针方向，就从凸包中删除倒数第一个点，循环此过程，直至Si在该向量顺时针方向，此时将Si入凸包。

在这里插入图片描述
点2在点0指向点1的向量的顺时针方向，点2入凸包；

在这里插入图片描述

在这里插入图片描述
点3在点1指向点2的向量的逆时针方向，点2从凸包中删除，此时点3在点0指向点1的向量的顺时针方向，入凸包；
在这里插入图片描述
点4在点1指向点3的向量的顺时针方向，点4入凸包；
在这里插入图片描述
在这里插入图片描述
点5在点3指向点4的向量的逆时针方向，点4从凸包中删除，此时点5在点1指向点3的向量的顺时针方向，入凸包；
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
点6在点3指向点5的向量的逆时针方向，点5从凸包中删除，此时点6还在点1指向点3的向量的逆时针方向，点3从凸包中删除，此时点6在点0指向点1的向量的顺时针方向，入凸包；
在这里插入图片描述
最后点7在点1到点6的向量的顺时针方向，点7入凸包

凸包上部构建完成

下部同理

最后两部分相连，即可得凸包。

代码&例题

破oj3348 Cows
题目大意：
给出一些树的坐标，一这些树为顶点可以围成一片牧场，牧场中每50个单位可以放一头牛，问最多可以放多少牛。
求最大牧场面积，就是求凸包面积。

代码

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
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring> 
using namespace std;
struct point{
    int x,y;
    point(){}
    point(int xx,int yy){
        x=xx;
        y=yy;
    }
    point operator - (const point a)const{
        return point(x-a.x,y-a.y);
    }

}p[11000],ch[11000];    //储存原来的点集和凸包序列
bool cmp(point a,point b){     //点排序
    if(a.x==b.x)  return a.y<b.y;
    return a.x<b.x; 
}
double chachen(point a, point b) {    //返回叉乘的膜
    return a.x*b.y-a.y*b.x;
}

int tubao(point *p,int n, point *ch){    //构造凸包
    sort(p,p+n,cmp); 
    int m=0;
    for (int i=0;i<n;i++){                         //上部
        while (m>1&&chachen(ch[m-1]-ch[m-2],p[i]-ch[m -2])<=0) //删除不凸的点
            m--;
        ch[m++]=p[i];
    }
    int k=m;
    for (int i=n-2;i>=0;i--){                  //下部
        while (m>k&&chachen(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) //删除不凸的点
            m--;
        ch[m++]=p[i];
    }
    if(n>1)
    m--;
    return m;                  //返回凸包中元素个数
}
int main(void){
    int n,m,ans;
    double area = 0;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>p[i].x>>p[i].y;
    m=tubao(p,n,ch);
    for(int i=0;i<m;i++){
        area+=ch[i].x*ch[i+1%m].y-ch[i+1%m].x*ch[i].y;//计算面积
    }
    if(area<=0)
        area=-area;
    ans=area/100;                  //计算面积要除2，再加上计算结果要除50，总共除100
    cout<<ans<<endl;
    return 0;
}