凸包学习笔记【计算几何】【凸包】

点击量：238

   求凸包就是求一个最小周长凸多边形，使得所求点集都被包含在这个凸多边形里。

   为什么是凸多边形？根据三角形不等式，如果有一个满足包含所有点的凹多边形，一定存在额外的一条边使得多边形的边数减少，同时边长减小。

   凸包模型是比较好分析出来的，那么怎么求凸包呢？

   为了减小精度误差，我们尽量少用除法和根号，于是我们就有了向量外积（叉积），只要有两个向量的坐标，就能求出它们的方向是“左拐”还是“右拐”，因为外积体现的是相对夹角的大小，因为相对夹角可正可负，所以外积可正可负。外积的计算公式是$ \vec{a}=(x_1,y_1),\vec{b}=(x_2,y_2),\Rightarrow |\vec{a} \times \vec{b}|=|\vec{a}||\vec{b}||\sin \theta |=x_1y_2-x_2y_1(θ=<\vec{a},\vec{b}>)$。外积计算结果是一个向量，方向满足$ \vec{a}, \vec{b}, \vec{a} \times \vec{b}$ 成右手系，不过我们一般利用它的正负来判断向量之间的关系。

   凸包的Graham-Scan算法是一种$ n\log n$的算法，利用了栈。其思想是：选定横坐标最小的点（如果有多个选择纵坐标最小的）作为极点（因为横坐标最小，所以这个点一定在凸包上），把剩下的点按极角排序。点的极角就是该点与极点的连线与极轴间夹角$ (\theta \in \mathbf{R})$。极坐标系的定义

   我们联想上面的图，发现所有的轨迹都是“左拐”的。如果$ \vec{AB},\vec{BC}$两向量叉积大于0，那么$ A\rightarrow B\rightarrow C$的轨迹是“右拐”的，具体原因与思想可以研究叉积的本质。

   一旦我们发现$ A,B,C$的轨迹是右拐，那么就可以断定$ B$点是含于线段$ AC$内侧的，我们如果用栈来储存凸包上的点，那么将$ B$点出栈，继续判断A点是否满足，直到满足左拐或只剩原点。

   这样程序运行到最后栈内存的就是凸包上的点了。

Code：（例题：圈奶牛）

#include<cstdio>
#include<algorithm>
#include<cmath>
using std::sort;
struct pnt//点
{
    double x,y;
    pnt(double x,double y)
    {
        this->x=x;
        this->y=y;
    }
    pnt(){}
    friend bool operator <(pnt a,pnt b)//找横坐标最小的点
    {
        if(a.x!=b.x)
            return a.x<b.x;
        return a.y<b.y;
    }
}p[10100];
struct V//向量
{
    double x,y;
    V(double x,double y)
    {
        this->x=x;
        this->y=y;
    }
    V(pnt a,pnt b)
    {
        x=b.x-a.x;
        y=b.y-a.y;
    }
    V(){}
};
double cross(V v1,V v2)//计算两向量叉积
{
    return v1.x*v2.y-v2.x*v1.y;
}
pnt source;//原点
bool cmp(pnt a,pnt b)//排序用，判断a是否在b的逆时针方向
{
    double ans=cross(V(a,source),V(b,source));
    if(ans==0)
        return a.x<b.x;
    return ans>0;
}
int n;
int s[10100],top=0;//栈
void Graham()
{
    s[++top]=1;//前两个点是初始状态
    s[++top]=2;
    for(int i=3;i<=n;i++)
    {
        while(top>=2&&(cross(V(p[i],p[s[top]]),V(p[s[top]],p[s[top-1]])))>0)//直到满足情况
            top--;
        s[++top]=i;
    }
    return;
}
double dis(pnt a,pnt b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main()
{
    scanf("%d",&n);
    if(n==0||n==1)//凸包大小为0
    {
        printf("0.00\n");
        return 0;
    }
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&p[i].x,&p[i].y);
    sort(p+1,p+1+n);
    source=p[1];
    sort(p+2,p+n+1,cmp);
    Graham();
    double sum=dis(source,p[s[top]]);
    while(top>1)
    {
        sum+=dis(p[s[top]],p[s[top-1]]);
        top--;
    }
    printf("%.2lf\n",sum);
    return 0;
}