二维凸包

摘要

二维凸包是计算几何中比较入门的部分

二维凸包的定义

对于平面上的若干个点 ,二维凸包指的是一个面积最小的凸多边形,把所有的点包含在内部。这个凸多边形以点集的形式表示。实际上可以理解为用一个橡皮筋包含住所有给定点的形态。

平面向量叉积

这里说的叉积不是三维向量中的概念。

如果两个向量 的叉积 ,那么 b 的方向对于 a 的方向而言是顺时针旋转的(即 a 顺时针旋转不超过 180 度与 b 的方向相同),反之亦然。

这东西有什么用?都放在凸包的文章里了显然是用来求凸包啊……

Andrew 算法

计算凸包的算法大同小异,Andrew 算法通过分开计算上凸壳和下凸壳的方式计算凸包。我们将点按横坐标排序,那么一个凸壳的相邻边对应的向量的叉积是同号的(要么一直大于 0, 要么一直小于 0,一般不会保留凸壳边上的点),这个可以用一个栈来维护。

我们顺序扫描排序后的点集,计算上凸壳。这时我们要保证向量是持续向右(顺时针)旋转的,即叉积小于 0. 一旦遇到叉积大于等于 0 的点,说明当前栈顶的点不在凸壳上,那么弹栈。以此类推。

然后我们倒序扫描点集计算下凸壳,这时我们仍然要求向量是顺时针旋转的,叉积小于 0. 唯一的限制是不能选择上凸壳中的点,因此要对上凸壳中的点预先打个标记防止再次被访问。

图:咕咕

struct point{// 注意,事实上向量和点都可以表示为 (x,y) 的形式,因此这个结构体也表示向量
    double x, y;
    point(double _x=0, double _y=0) {x=_x, y=_y;}
    point operator-(point p) {return point(x-p.x,y-p.y);}// 两点之差为向量
    bool operator<(point p) {return x<p.x;}// 排序用的比较函数
    double operator*(point p) {return x*p.y-y*p.x;}// 向量叉积
};
point a[N];

int s[N],tp=0;
bool vis[N];

void solve(){sort(a+1,a+n+1);
    s[++tp]=1;
    for(int i=2;i<=n;i++){while(tp>1&&(a[s[tp]]-a[s[tp-1]]) * (a[i]-a[s[tp]])>=0)
            --tp;
        s[++tp]=i;
    }
    for(int i=1;i<=tp;i++)vis[s[i]]=1;
    vis[1]=0;// 用于在下凸壳结尾的时侯连接到 1
    int t=tp;
    for(int i=n;i>=1;i--) if(!vis[i]){while(tp>t&&(a[s[tp]]-a[s[tp-1]]) * (a[i]-a[s[tp]])>=0)
            --tp;
        s[++tp]=i;
    }
    // 注意,最后多出了一个 1
}

  转载请注明: Sshwy's Blog 二维凸包

 上一篇
最小割树 最小割树
摘要 最近发现的一个小 Tip 任意两点最小割 对于一个网络图,我们要求任意两点间的最小割 考虑在网络图 的一个最大流 . 这显然也是 $s\right
2019.05.07
下一篇 
浅谈一类分治算法 浅谈一类分治算法
摘要 仍然是啃论文,这次啃一啃数据结构的部分 修改与询问我们常常遇到数据结构题,要求我们维护修改与询问的操作。这些题目的要求各不相同,而操作之间的关系也各不相同。在满足特定关系的操作中,我们利用条件的线性性与相关性,可以将一类动态问题转化
2019.05.05
  目录