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

作者: wjyyy 分类: 凸包/凸壳,学习笔记,快速排序,计算几何 发布时间: 2018-06-23 22:49

点击量:29

 

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

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

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

   为了减小精度误差,我们尽量少用除法和根号,于是我们就有了向量外积(叉积),只要有两个向量的坐标,就能求出它们的方向是“左拐”还是“右拐”,因为外积体现的是相对夹角的大小,因为相对夹角可正可负,所以外积可正可负。外积的计算公式是\(\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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */