凸包-Andrew算法&&Graham扫描法

程序员文章站 2022-06-06 14:46:22

...

凸包简介：

在二维平面上(二维凸包)给出若干个点，能够包含这若干个点的面积最小的凸多边形称为凸包（可以想像有很多个钉子钉在墙上，然后用一个橡皮圈套在所有的钉子上，最后橡皮圈形成的就是一个凸包）。

Graham扫描法：

Graham扫描法是一种基于极角排序的进行求解的算法，其大致流程如下：

①找一个一定在凸包上的点P0（一般找纵坐标最小的点）；

②将其余所有的点以P0为基准进行极角排序；

③从P0出发扫描所有的点，不断地更新最外围的点，是否在最外围可由叉乘判断。这里用个图说明一下：

凸包-Andrew算法&&Graham扫描法

当前对点P进行判断，P1,P2为前面加入的两个点：

Ⅰ）若点P在内部（图一），则有向量b叉乘向量a小于零，此时点P是凸包的顶点，应将P点加入凸包。

Ⅱ）若在点P在外部，则有向量b叉乘向量a大于零，此时应该将点P1舍弃，继续对前两个点进行判断，直到P、P1、P2三个点满足向量b叉乘向量a小于零，再将P点加入凸包。

当然网上面还有更详细的例子，不懂得话可以再看看其余的资料(￣▽￣)。

具体代码如下：

//Graham扫描法-hdu1392
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e6+10;
const double esp=1e-10;
struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){
        x=_x;y=_y;
    }
}P[maxn],Convexhull[maxn];
typedef Point Vector;
Vector operator + (Vector A,Vector B){
    return Vector(A.x+B.x,A.y+B.y);
}
Vector operator - (Vector A,Vector B){
    return Vector(A.x-B.x,A.y-B.y);
}
Vector operator * (Vector A,double d){
    return Vector(A.x*d,A.y*d);
}
Vector operator / (Vector A,double d){
    return Vector(A.x/d,A.y/d);
}
double Dot(Vector A,Vector B){
    return A.x*B.x+A.y*B.y;
}
double Cross(Vector A,Vector B){
    return A.x*B.y-A.y*B.x;
}
double Length(Vector A){
    return sqrt(Dot(A,A));
}
int dcmp(double x){
    return fabs(x)<esp?0:x<0?-1:1;
}
bool Angle_Cmp(Point p1,Point p2){
    double res=Cross(p1-P[0],p2-P[0]);
    return dcmp(res)>0||(dcmp(res)==0&&dcmp(Length(p1-P[0])-Length(p2-P[0]))<0);
}
int Graham(int n){
    int k=0;
    Point p0=P[0];
    for(int i=1;i<n;i++){
        if(p0.y>P[i].y||(p0.y==P[i].y&&p0.x>P[i].x)){
            k=i;p0=P[i];
        }
    }
    swap(P[0],P[k]);
    sort(P+1,P+n,Angle_Cmp);
    Convexhull[0]=P[0];                 //Assume n>2
    Convexhull[1]=P[1];
    int top=2;
    for(int i=2;i<n;i++){
        while(top>1&&Cross(P[i]-Convexhull[top-2],Convexhull[top-1]-Convexhull[top-2])>=0)top--;
        Convexhull[top++]=P[i];
    }
    return top;
}
int main(){
    freopen("in.txt","r",stdin);
    int n;
    while(~scanf("%d",&n)&&n){
        for(int i=0;i<n;i++)scanf("%lf%lf",&P[i].x,&P[i].y);
        int cnt=Graham(n);
        double ans=0;
        if(cnt!=2)ans+=Length(Convexhull[0]-Convexhull[cnt-1]);
        for(int i=0;i<cnt-1;i++)ans+=Length(Convexhull[i]-Convexhull[i+1]);
        printf("%.2lf\n",ans);
    }
    return 0;
}

Andrew算法：

Andrew算法是一种基于水平序的算法，在许多的资料上都会发现说该算法可以看作Graham扫描法的一种变体，为什么这么说呢？我的理解就是二者都是对所有的点进行扫描得到凸包，不过扫描之前做的处理不同，Andrew算法的大致流程如下：

①将所有的点按照横坐标从小到大进行排序，横坐标相同则按纵坐标从小到大排；

②将P[0]和P[1]加入凸包，然后从P[2]开始判断，判断方式同Graham算法中的判断一致；

③将所有的点扫描一遍以后，我们便可以得到一个“下凸包”（为什么？画个图就懂了--横坐标不会减小）；

④同理，我们从P[n-2]开始(P[n-1]已经判过了)，反着扫描一遍，便可以得到一个“上凸包”；

⑤将两个“半凸包”合在一起就是一个完整的凸包，注意的是由于起点P[0]在正着扫描和反着扫描时都会将其加入凸包，故需要将最后一个点(P[0])去掉才为最终结果。

具体代码如下：

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e6+10;
const double esp=1e-10;
struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){
        x=_x;y=_y;
    }
}P[maxn],Convexhull[maxn];
typedef Point Vector;
Vector operator + (Vector A,Vector B){
    return Vector(A.x+B.x,A.y+B.y);
}
Vector operator - (Vector A,Vector B){
    return Vector(A.x-B.x,A.y-B.y);
}
Vector operator * (Vector A,double d){
    return Vector(A.x*d,A.y*d);
}
Vector operator / (Vector A,double d){
    return Vector(A.x/d,A.y/d);
}
double Dot(Vector A,Vector B){
    return A.x*B.x+A.y*B.y;
}
double Cross(Vector A,Vector B){
    return A.x*B.y-A.y*B.x;
}
double Length(Vector A){
    return sqrt(Dot(A,A));
}
int dcmp(double x){
    return fabs(x)<esp?0:x<0?-1:1;
}
bool operator <(Point p1,Point p2){
    return dcmp(p1.x-p2.x)<0||(dcmp(p1.x-p2.x)==0&&dcmp(p1.y-p2.y)<0);
}
int Andrew(int n){      //Assume n>2
    sort(P,P+n);
    int top=0;
    for(int i=0;i<n;i++){
        while(top>1&&dcmp(Cross(P[i]-Convexhull[top-2],Convexhull[top-1]-Convexhull[top-2]))>=0)top--;
        Convexhull[top++]=P[i];
    }
    int k=top;
    for(int i=n-2;i>=0;i--){
        while(top>k&&dcmp(Cross(P[i]-Convexhull[top-2],Convexhull[top-1]-Convexhull[top-2]))>=0)top--;
        Convexhull[top++]=P[i];
    }
    return top-1;
}
int main(){
    freopen("in.txt","r",stdin);
    int n;
    while(~scanf("%d",&n)&&n){
        for(int i=0;i<n;i++)scanf("%lf%lf",&P[i].x,&P[i].y);
        int cnt=Andrew(n);
        double ans=0;
        if(cnt!=2)ans+=Length(Convexhull[0]-Convexhull[cnt-1]);
        for(int i=0;i<cnt-1;i++)ans+=Length(Convexhull[i]-Convexhull[i+1]);
        printf("%.2lf\n",ans);
    }
    return 0;
}

小结：

显然两种算法的复杂度均为O(nlogn)，若输入有序的话时间复杂度就均为O(n)，但是紫薯上说“和原始的Graham算法相比，Andrew算法更快，且数值稳定性更好”，或许是因为排序二者排序过程中的差异--Graham算法中的极角排序需要进行大量的叉乘计算。