2020-02-06 19:11 已编辑烟台二中

关注

数论小白都能看懂的平面凸包详解

0.前言：

本文将已详细的配图，带您轻松入门平面凸包。

1.引入：

假设一个操场上有一些小朋友，下面是航拍视角：

现在他们要围一个球场做游戏。

因为老师比较懒，所以就只能麻烦一些小朋友了（他们自己撑着绳子防止球滚出去）

而小朋友又不动脑子。所以就只能麻烦你来出主意了。

显然，最简单的方法是这样：

先把一圈大绳子放在外面，然后往里缩，直到：

最外圈的小朋友撑起了绳子。

此时黑线围成的多边形的顶点就是小朋友所在的位置。

由此，我们就定义黑线围成的图形为一个平面凸包

那么，换一种定义方式，我们就定义：

平面凸包是指覆盖平面上n个点的最小的凸多边形。

当然，我们发现在程序中却无法模拟此过程，于是有了下文的诞生。

2、斜率逼近法

其实这也是一种容易想到的算法，但是并不常用（代码复杂度高），我们稍作了解

然后我们可以把这个思路具体化：

(1)首先在所有点钟找出一个y值最小的点，记为\(P_1\)
(2)从\(P_1\)出发，刚开始k=0，即为水平状态。然后按照上图的示意沿逆时针方向寻找。即开始在\(k>0\)且\((x_2>x1,y_2>y_1)\)中找k最小的点\(P_2\)，以此类推。

Q:如果过程中有多个点符合要求怎么办？

A:那么就去距离\(P_1\)最远的点，因为这样能保证划定的范围最大。

（3）从\(P_2\)出发，用（2）的方法找\(P_3\)
(4)最后直到\(P_m=P_1\)为止（已形成凸包）。

Q:为什么要刚开始找y值最小的点？

A:结合刚开始的小朋友拉绳子可知，我们在下面的绳子一定会被y值最小的小朋友挡住，即他一定在凸包上，于是就以他为基准来操作。

Q:万一最后没有一个\(P_m\)使得\(P_m=P_1\)呢？

A:易证必有，平面凸包总是存在的。

时间复杂度：O(nm)

n为所有小朋友的数量，m为舍己为人的小朋友的数量。

说到这里大家都明白了，一但凸包上的两个点的斜率趋于无穷大，那么就无法解决了。

于是~~窝的日报又能进行下去了~~有人就提出了一种新的方法。

3、Jarvis算法

这其实是一种数学构造法

我们还是把那群小朋友骗聘过来：

我们考虑让一个小朋友手里拿着一根棒子：

从外往里旋转。

然后会撂倒碰到另一个小朋友：

然后我们让被棒子碰到的小朋友再取一根棒子~~继续打人~~，重复以上操作。

就是这样。

但如果遇到以下情况：

有的小朋友在旋转棍子时同时碰到了多于一个点（即三点共线），那么显然我们需要选择最远的点。

不难证明，这样下来也可以围成一个平面凸包。

以上是定向的想象，那么下面就来严谨的说明一下

描述如下：

首先找到一条直线\(l\)过其中一点A，使得所有其他的点都在\(l\)的同一侧。

这种直线显然一定能找到。

由此也易证A一定为凸包上一点。

让直线\(l\)以A为轴点沿顺时针或逆时针方向旋转，直到抡到除A以外的一点B

别忘了上面那个~~形象的~~讲述，在遇到多于一个点时要取最远的。

重复以上操作，直到l碰到A点。

在过程中受伤被碰到的点就构成了平面凸包的顶点序列。

在此过程中，虽然我们发现上述过程仍然不太好实现，但是我们还是可以通过一系列的玄学转换得到

我们考虑到B点是最先碰到的，那么新的直线\(l'\)必然在A和除B及自身以外其他点的连线中与\(l\)的夹角最小

即紫∠比红∠大

那么在下图中：

\(if(\vec {AP}\times \vec {AP_i})z>0\)

则\(\vec {AP}\)到\(\vec {AP_i}\)的旋转为逆时针旋转。

显然，\(\vec {AP_i}\)与l的夹角比\(\vec {AP}\)的更接近。为更好的答案。

\(else\)

\(if(\vec {AP}\times \vec {AP_i})z=0\)

那说明A，P，\(P_i\)三点共线，自然取最远的。

我们按这个顺序扫描所有的点，就能找到这个凸包上的一条边。

显而易见：此时间复杂度为\(O(nm)\)，即每次扫n个点，一共m次可构成凸包。

但是。。。这个时间复杂度还是会凉。。。

假设就是这道题,那么我们观察到\(n\leq 10000\),这是一道平面凸包的模板题，但是如果数据构造到m=n甚至和n相差不大的情况，那就会轻而易举的超时。

可见，此算法仅仅适用于随机点集，对于刻意构造的数据就会被卡成\(O(n^2)\)

而毒瘤的OI怎么会不卡呢？

连模板题都过不了，看来这个算法还是得优化，所以我们还是得用保险的算法，于是

4、Graham算法

本质：

Graham扫描算法维护一个凸壳通过不断在凸壳中加入新的点和去除影响凸性的点最后形成凸包

至于凸壳： 就是凸包的一部分

算法主要由两部分构成：

排序
扫描

（1）排序

我们的Graham算法的第一步就是对点集进行排序，这样能保证其有序性，从而在后续的处理中达到更高效的效果，这也是Graham算法更优的原因。

开始操作：

我们还是选择一个y值最小（如有相同选x最小）的点，记为\(P_1\)
剩下的点集中按照极角的大小逆时针排序，然后编号为\(P_2\)~\(P_m\)

~~达成成就：种草达人~~

我们按照排序结束时的顺序枚举每一个点，依次连线，这里可以使用一个栈来存储，每次入栈，如果即将入栈的元素与栈顶两个元素所构成了一个类似于凹壳的东西，那么显然处于顶点的那个点一定不在这个点集的凸包上，而他正好在栈顶，所以把它弹出栈，新点入栈。

但是，新来的点有可能既踢走了栈顶，再连接新的栈顶元素后却发现仍然可以踢出，此时就不能忘记判断。

怎么样，感觉这个算法如何？

如果您不想纠缠于繁杂的文字描述，那么下面就有精美图片解说献上。

（ps:下列解说中右转左转等是指以上一条连线为铅垂线，新的连线偏移的方位）

刚开始，我们的点集是这样的：

其中p1为起始点

然后p2准备入栈，由于栈中元素过少，所以检验合格，可直接进入。

之后因为p3仍为向左转，符合凸包条件，所以暂时先让它进去

p4出现了右转现象，那么我们就把顶点p3舍去，在检查p2的性质，合格

于是p3出栈，p4入栈

p5一切正常，入栈。

p6这里就要复杂一些

首先他往右转，于是将p5弹出

又发现他相对于\(P_2P_4\)向右转，于是将p4弹出

之后p6进栈。

p7一切正常（左转），入栈

p8一切正常（左转），入栈

所以说最后就连到了起点p1。

由此，我们的Graham算法的全过程就结束了。

凸包形成（即绿线所围的多边形）

扫描的时间复杂度：\(O(n)\)

但是显然不可能做到这么优秀.

于是还有排序的时间复杂度：\(O(nlog_2n)\)

合起来总的时间复杂度：\(O(nlog_2n)\)

可见，我们在排序的帮助下省去了一些盲目的扫描，虽然排序作为一个预处理时间复杂度占据了总时间复杂度，但相比前一个算法还是更为优秀

现在我们到模板题上来。

P2742 【模板】二维凸包 / [USACO5.1]圈奶牛Fencing the Cows

题意简叙：

求一个点集凸包的边长和。

分析：

平面凸包模板题，注意浮点数之类的别弄丢精度就行，其他直接套模板,代码里有注释。

code：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int n;
struct ben
{
    double x,y;
}p[10005],s[10005];
double check(ben a1,ben a2,ben b1,ben b2)//检查叉积是否大于0，如果是a就逆时针转到b 
{
    return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);
}
double d(ben p1,ben p2)//两点间距离。。。 
{
    return sqrt((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));
}
bool cmp(ben p1,ben p2)//排序函数，这个函数别写错了，要不然功亏一篑 
{
    double tmp=check(p[1],p1,p[1],p2);
    if(tmp>0) 
        return 1;
    if(tmp==0&&d(p[0],p1)<d(p[0],p2)) 
        return 1;
    return 0;
}
int main()
{
    
    scanf("%d",&n);
    double mid;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&p[i].x,&p[i].y);
        if(i!=1&&p[i].y<p[1].y)//这是是去重 
        {
            mid=p[1].y;p[1].y=p[i].y;p[i].y=mid;
            mid=p[1].x;p[1].x=p[i].x;p[i].x=mid;
        }
    } 
    sort(p+2,p+1+n,cmp);//系统快排 
    s[1]=p[1];
    int cnt=1;//最低点一定在凸包里 
    for(int i=2;i<=n;i++)
    {
        while(cnt>1&&check(s[cnt-1],s[cnt],s[cnt],p[i])<=0) 
            cnt--;
        cnt++;
        s[cnt]=p[i];
    }
    s[cnt+1]=p[1];
    double ans=0; 
    for(int i=1;i<=cnt;i++) 
        ans+=d(s[i],s[i+1]);
    printf("%.2lf\n",ans);
    return 0;
}