2025年凸包与Graham扫描法求凸包

大家好，我是讯享网，很高兴认识大家。

前置芝士

凸多边形

凸多边形指的是所有内角都在 $(0,\pi]$ 范围内的多边形。

凸包

对于一个平面上的一个给定的点集，他们对应的凸包就是能把他们全部包含的最小凸多边形。

如果形象一点，可以把平面上的点集想象成木板上的钉子，而其对应的凸包则是一根将所有点围在内部的橡皮筋。

讯享网

凸包求法

常用的凸包求法有Graham扫描法和Andrew算法，这里主要讲解Graham扫描法，Andrew算法可以看OI-Wiki对应内容。

复杂度

Graham扫描法的时间复杂度是 $\log n)$ ，瓶颈主要在对所有点的极角排序上。

过程

选取基准点

首先我们选择一个点来当做我们的基准点。
这个点需要在整个点集的最下方，而如果有多个纵坐标相同的点我们选横坐标最小的点，所以我们直接 $O (n)$ 扫一遍即可。

极角排序

然后把剩下的点以刚才我们选出的点为基准进行极角排序。
因为这个点的左下方没有点，那么任意一个点的极角只能在 $(0,\pi]$ 范围内。
会的可以跳过。

下面将我们目前需要比较的两个点称作 $P_i$ 和 $P_j$ ，将基准点称为 $P_0$ 。

我们可以选择两种方法来进行排序。

首先是一种比较浅显的，通过极角的余弦值的相反数来排序。
通过观察，我们可以发现在 $(0,\pi]$ 范围内，函数 $f(x)=-\cos(x)$ 是单调递增的。
所以我们如果知道了 $-\cos(\angle P_i P_0 x) < -\cos(\angle P_j P_0 x)$ ，那就可以推出来 $\angle P_i P_0 x < \angle P_j P_0 x$ 。

代码如下：

double dis(Point a, Point b) { 
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } bool cmp(Point lhs, Point rhs) { 
    double lang = -((lhs.x - p[b].x) / dis(lhs, p[b])); double rang = -((rhs.x - p[b].x) / dis(rhs, p[b])); if(lang - rang == 0)return dis(lhs, p[b]) < dis(rhs, p[b]); else return lang < rang; }

讯享网

或者是构造出来两个向量，通过向量的叉积来判断两者的位置。

我们构造出来两个向量 $\overrightarrow{P_0 P_i}$ 和 $\overrightarrow{P_0 P_j}$ ，然后计算出来两个向量的叉积。
如果叉积为正，那么就可以证明 $\angle P_i P_0 x < \angle P_j P_0 x$ 。

代码如下：

讯享网double dis(Point a, Point b) { 
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } double oprod(Point a, Point b, Point c, Point d) { 
    return (b.x - a.x) * (d.y - c.y) - (d.x - c.x) * (b.y - a.y); } bool cmp(Point lhs, Point rhs) { 
    double chq = oprod(p[b], lhs, p[b], rhs); if(chq == 0)return dis(lhs, p[b]) < dis(rhs, p[b]); else return chq > 0; }

构建凸包

首先来一个图来演示一下构建凸包的过程：

我们使用一个栈来维护当前在凸包上的点。

首先，我们将基准点和第一个点无条件加入栈中。

然后，我们遍历剩下的点，每一次将将要加入栈中的点 $P$ 与栈顶的点 $S_1$ 和栈顶下方的第一个点 $S_2$ 构成两个向量 $\overrightarrow{S_1 P}$ 和 $\overrightarrow{S_2 S_1}$ ，如果 $\overrightarrow{S_1 P}$ 较 $\overrightarrow{S_2 S_1}$ 向顺时针方向旋转，即叉积 $\overrightarrow{S_1 P} \times \overrightarrow{S_2 S_1} < 0$ ，我们就将 $S_1$ 弹出栈，返回上一步继续检测，直到栈中只剩一个点或叉积非负为止。
最后把点加入栈中。

代码如下：

vector<Point>v; for(int i = 1; i <= n; i++) if(i != b)v.push_back(p[i]); sort(v.begin(), v.end(), cmp);//稍微麻烦一点的排序 p[1] = p[b]; for(int i = 2; i <= n; i++) p[i] = v[i - 2]; sta[1] = 1, sta[2] = 2, tt = 2;//初始化栈 for(int i = 3; i <= n; i++) { 
    while(tt >= 2 && oprod(p[sta[tt - 1]], p[sta[tt]], p[sta[tt]], p[i]) <= 0) tt--; sta[++tt] = i; }

2025年凸包与Graham扫描法求凸包

前置芝士

凸多边形

凸包

凸包求法

复杂度

过程

选取基准点

极角排序

构建凸包

相关推荐