【计算几何】凸包问题 (Convex Hull)
引言
凸多边形
凸多边形是指所有内角大小都在 [ 0 , π ] [0,π] [0,π]范围内的简单多边形
凸包
在平面上能包含所有给定点的最小凸多边形叫做凸包。
其定义为:对于给定集合 X,所有包含 X 的凸集的交集 S 被称为 X 的 凸包。
实际上可以理解为用一个橡皮筋包含住所有给定点的形态。
凸包用最小的周长围住了给定的所有点。如果一个凹多边形围住了所有的点,它的周长一定不是最小,如下图。根据三角不等式,凸多边形在周长上一定是最优的。
凸包的求法
主要介绍Graham扫描法
Graham Scan 算法求凸包
Graham Scan 算法是一种十分简单高效的二维凸包算法,能够在 O ( n l o g n ) O(nlogn) O(nlogn)
的时间内找到凸包。
Graham Scan 算法的做法是先确定一个起点(一般是最左边的点和最右边的点),然后一个个点扫过去,如果新加入的点和之前已经找到的点所构成的 “壳” 凸性没有变化,就继续扫,否则就把已经找到的最后一个点删去,再比较凸性,直到凸性不发生变化。分别扫描上下两个 “壳”,合并在一起,凸包就找到了。这么说很抽象,我们看图来解释:
先找 “下壳”,上下其实是一样的。首先加入两个点 A 和 B。
然后插入第三个点 C,并计算 A B ⃗ × B C ⃗ \vec{AB} \times \vec{BC} AB×BC的向量积,却发现向量积系数小于(等于)0,也就是说 B C ⃗ \vec{BC} BC
在 A B ⃗ \vec{AB} AB的顺时针方向上。
于是删去 B 点。
按照这样的方法依次扫描,找完 “下壳” 后,再找 “上壳”。
#include <algorithm>struct Point {double x, y;// 重载减法运算符,用于计算向量差Point operator-(Point& p) {Point t;t.x = x - p.x;t.y = y - p.y;return t;}// 计算向量叉积double cross(Point p) {return x * p.y - p.x * y;}
};// 比较函数,用于排序点
bool cmp(Point& p1, Point& p2) {if (p1.x != p2.x) return p1.x < p2.x;return p1.y < p2.y;
}Point point[1005]; // 无序点
int convex[1005]; // 保存组成凸包的点的下标
int n; // 坐标系的无序点的个数// 获取凸包的函数
int GetConvexHull() {// 按照x坐标排序,如果x相同则按照y坐标排序sort(point, point + n, cmp);int temp;int total = 0;// 构建下凸包for (int i = 0; i < n; i++) {// 如果当前栈中至少有两个点,并且新点使得栈顶的两个点与新点形成的向量不满足逆时针方向while (total > 1 &&(point[convex[total - 1]] - point[convex[total - 2]]).cross(point[i] - point[convex[total - 1]]) <= 0)total--; // 弹出栈顶点convex[total++] = i; // 将当前点加入栈中}temp = total; // 记录下凸包的点数// 构建上凸包for (int i = n - 2; i >= 0; i--) {// 如果当前栈中至少有两个点,并且新点使得栈顶的两个点与新点形成的向量不满足逆时针方向while (total > temp &&(point[convex[total - 1]] - point[convex[total - 2]]).cross(point[i] - point[convex[total - 1]]) <= 0)total--; // 弹出栈顶点convex[total++] = i; // 将当前点加入栈中}return total - 1; // 返回组成凸包的点的个数,实际上多了一个,就是起点,所以组成凸包的点个数是 total - 1
}
代码解释
结构体 Point:
-
包含两个成员变量 x 和 y,表示点的坐标。
-
重载了减法运算符 operator-,用于计算两个点的向量差。
-
定义了 cross 方法,用于计算两个向量的叉积。
比较函数 cmp:
- 用于对点进行排序,首先按 x 坐标排序,如果 x 坐标相同则按 y 坐标排序。
全局变量:
-
point 数组存储无序点。
-
convex 数组存储组成凸包的点的下标。
-
n 表示无序点的个数。
函数 G e t C o n v e x H u l l GetConvexHull GetConvexHull:
-
首先对点进行排序。
-
构建下凸包:从左到右遍历点,使用栈来维护凸包的点,确保每次新加入的点与栈顶的两个点形成的向量满足逆时针方向。
-
构建上凸包:从右到左遍历点,使用栈来维护凸包的点,确保每次新加入的点与栈顶的两个点形成的向量满足逆时针方向。
-
返回组成凸包的点的个数,注意实际点的个数是 total - 1,因为起点被重复计算了一次。