【计算几何】凸包问题 (Convex Hull)

引言

凸多边形

凸多边形是指所有内角大小都在 $[0, π]$ 范围内的简单多边形

凸包

在平面上能包含所有给定点的最小凸多边形叫做凸包。

其定义为：对于给定集合 X，所有包含 X 的凸集的交集 S 被称为 X 的凸包。

实际上可以理解为用一个橡皮筋包含住所有给定点的形态。

凸包用最小的周长围住了给定的所有点。如果一个凹多边形围住了所有的点，它的周长一定不是最小，如下图。根据三角不等式，凸多边形在周长上一定是最优的。

在这里插入图片描述

凸包的求法

主要介绍Graham扫描法

Graham Scan 算法求凸包

Graham Scan 算法是一种十分简单高效的二维凸包算法，能够在 $O (n l o g n)$
的时间内找到凸包。

Graham Scan 算法的做法是先确定一个起点（一般是最左边的点和最右边的点），然后一个个点扫过去，如果新加入的点和之前已经找到的点所构成的 “壳” 凸性没有变化，就继续扫，否则就把已经找到的最后一个点删去，再比较凸性，直到凸性不发生变化。分别扫描上下两个 “壳”，合并在一起，凸包就找到了。这么说很抽象，我们看图来解释：

在这里插入图片描述

先找 “下壳”，上下其实是一样的。首先加入两个点 A 和 B。

然后插入第三个点 C，并计算 $\vec{AB} \times \vec{BC}$ 的向量积，却发现向量积系数小于（等于）0，也就是说 $\vec{BC}$
在 $\vec{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
}