(几何) 凸包问题

文章目录

前言
向量积
凸包算法
END

前言

凸包问题（Convex Hull）是计算几何中的经典问题，也是众多计算几何的入门问题。

凸包_百度百科顾名思义就是一个凸的多边形，在视觉上也许比较容易看出，但是如何证明哪些是凸包点，如何用代码实现这并不容易。

练习题：

力扣：587. 安装栅栏

力扣：812. 最大三角形面积

相关讲解：

安装栅栏 - 官方题解 - 力扣（LeetCode）

相比于网上找的其他凸包的代码，这个题解写的友好很多，其中每个算法的动图推荐看一下

本文几乎是按照该题解编写，其中加了自己的理解和注释等

算法	时间复杂度	空间复杂度
Jarvis 算法	${O(n^2)}$ (每次暴力搜索所有点)	${O(n)}$
Graham 算法	${O(nlogn)}$ （ ${O(n)(出入栈) + O(nlogn)(排序)}$ ）	${O(n)}$ (不计排序)
Andrew 算法	${O(nlogn)}$ （ ${O(n)(出入栈) + O(nlogn)(排序)}$ ）	${O(n)}$ (不计排序)

向量积

向量积_百度百科

叉积

**几何意义：**结果为一个向量，与原向量垂直

**代数意义：**模长：（在这里θ表示两向量之间的夹角（共起点）（0°≤θ≤180°），它位于这两个矢量所定义的平面上。）

模长的绝对值表示两条向量构成的平行四边形的面积

下图中p点，q点，r点向量 ${pq}$ ，向量 ${qr}$ 的向量积

为正，则角度＜ 180度 ${qr相对pq左偏}$
为0，则角度 = 180度 (平行)
为负，则角度 > 180度 ${qr相对pq右偏}$

本主题以该图为思路

p 前驱点 pre
q 中转点 cur
r 搜寻点 nex

不需要强记关系

只需要知道一正一负，代表两个不同的偏向即可

// p0p1 x p0p2     共起点p0
inline int cross(vector<int>& p0, vector<int>& p1, vector<int>& p2) {
    int x0 = p1[0] - p0[0], y0 = p1[1] - p0[1];
    int x1 = p2[0] - p0[0], y1 = p2[1] - p0[1];
    return x0 * y1 - y0 * x1;
}
// p0p1 x p1p2     p1作为p0p1的终点，p0p1的起点
inline int cross(vector<int>& p0, vector<int>& p1, vector<int>& p2) {
    int x0 = p1[0] - p0[0], y0 = p1[1] - p0[1];
    int x1 = p2[0] - p1[0], y1 = p2[1] - p1[1];
    return x0 * y1 - y0 * x1;
}
1
2
3
4
5
6
7
8
9
10
11
12

凸包算法

Jarvis 算法

思路：

寻找一个最外围的点作为起始点
为了便于建立坐标，选取x轴最低点

不断寻找下一个临近的外围凸点
暴力遍历搜寻每个点
一轮循环结束，找到当前可作为下一个点的cur
再次搜寻平行点
合格的点若未访问，则为答案

直到找到点与起始点相同，则围成一个圈

// Jarvis 算法
class Solution {
public:
    // 解决凸包问题中只要是正确的叉乘效果即可
    // p0p1 x p0p2     共起点p0
    inline int cross(vector<int>& p0, vector<int>& p1, vector<int>& p2) {
        int x0 = p1[0] - p0[0], y0 = p1[1] - p0[1];
        int x1 = p2[0] - p0[0], y1 = p2[1] - p0[1];
        return x0 * y1 - y0 * x1;
    }

    vector<vector<int>> outerTrees(vector<vector<int>>& points) {
        int n = points.size();
        if (n <= 3) {
            return points;
        }

        // x 最左 再y 最下
        int leftSide = 0;
        for (int i = 0; i < n; i++) {
            // C++中 vector依次比较元素
            if (points[i] < points[leftSide]) {
                leftSide = i;
            }
        }

        vector<vector<int>> ans;
        vector<bool> vis(n);

        int pre = leftSide;
        do {
            // 一直寻找目标点存入ans
            int cur = (pre + 1) % n;
            // 遍历所有点查询下一个目标
            for (int nex = 0; nex < n; nex++) {
                // 只要统一朝一个方向，保证三者关系的一致性即可
                if (cross(points[pre], points[cur], points[nex]) < 0) {
                    cur = nex;
                }
            }

            // 处理平行线
            for (int nex = 0; nex < n; nex++) {
                // 未访问 且不是前两个点
                if (vis[nex] || nex == pre || nex == cur) {
                    continue;
                }
                // 是平行线
                if (cross(points[pre], points[cur], points[nex]) == 0) {
                    vis[nex] = true;
                    ans.emplace_back(points[nex]);
                }
            }

            if (!vis[cur]) {
                vis[cur] = true;
                ans.emplace_back(points[cur]);
            }

            // 传递
            pre = cur;
        } while (pre != leftSide);

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

Graham 算法

思路：

寻找一个最外围的点作为起始点

为了便于建立坐标，选取y轴最低点

其余点按照极坐标进行排序极角小的在前

极角相同按距离排序（近 —> 远）
最后一条凸包线中的点按距离排序（远 —> 近）

用栈记录凸包点

首先保存前buttom 和 sorted的首个点
栈顶的点作为中转点 cur 并弹出
此时新的栈顶点作为 pre
寻找内偏点与sort的cross判断一致
将在搜寻nex点时 cross 不一致的舍弃
直到cross一致或者平行

最后栈中的点即为全部的凸包点

注意点：

sort中极角相同的处理情况

这个问题最好看示意图，模拟走一遍，文字不好说明

非最后的凸包线（近 —> 远）
优先处理近点，再处理到远点时，可以把近点舍去

最后的凸包线（远 —> 近）
因为是最后的凸包线，因此该线上的所有点均合格
先处理远点后，近点必然都合格

// Graham 算法
class Solution {
   public:
    // 解决凸包问题中只要是正确的叉乘效果即可
    // p0p1 x p0p2     共起点p0
    inline int cross(vector<int>& p0, vector<int>& p1, vector<int>& p2) {
        int x0 = p1[0] - p0[0], y0 = p1[1] - p0[1];
        int x1 = p2[0] - p0[0], y1 = p2[1] - p0[1];
        return x0 * y1 - y0 * x1;
    }
    // 两点间距离，确保精度不用开根号
    inline int distance(vector<int>& p0, vector<int>& p1) {
        int x = p0[0] - p1[0], y = p0[1] - p1[1];
        return x * x + y * y;
    }

    vector<vector<int>> outerTrees(vector<vector<int>>& points) {
        int n = points.size();
        if (n <= 3) {
            return points;
        }

        // 只要找到y轴的最下方一个点即可
        // 与该点平行的点均会自动处理
        int buttom = 0;
        for (int i = 0; i < n; i++) {
            if (points[i][1] < points[buttom][1]) {
                buttom = i;
            }
        }
        // 将该点至于首部，不用排序与遍历
        swap(points[0], points[buttom]);

        // 按照极角的大小排序
        sort(points.begin() + 1, points.end(),
             [&](vector<int>& a, vector<int>& b) {
                 int angle = cross(points[0], a, b);
                 // 若平行，则小距离在前
                 return (angle == 0)
                            ? (distance(points[0], a) < distance(points[0], b))
                            : (angle > 0);
             });

        // 将最后一条线中的点，距离buttom远的排在前
        int e = n - 1;
        while (e >= 0 && cross(points[0], points[n - 1], points[e]) == 0) {
            e--;
        }
        // 已经有序，反转即可
        reverse(points.begin() + e + 1, points.end());

        stack<int> stk;
        stk.push(0);
        stk.push(1);
        // 预存的两个点后，从idx2开始遍历
        for (int nex = 2; nex < n; nex++) {
            int cur = stk.top();
            stk.pop();

            // 若朝外，则表示中转点在内部，不合格
            // 这里的cross判断条件与sort中的相反
            while (!stk.empty() &&
                   cross(points[stk.top()], points[cur], points[nex]) < 0) {
                cur = stk.top();
                stk.pop();
            }

            // 这里表示中转点cur可以接受nex点
            // 即朝内或平行
            stk.push(cur);
            stk.push(nex);
        }

        // 栈中即为凸包的所有点
        vector<vector<int>> ans;
        while (!stk.empty()) {
            ans.emplace_back(points[stk.top()]);
            stk.pop();
        }

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

Andrew 算法

思路：

所有点按照x轴排序，再按y轴排序
point.front() 最左用于一轮遍历找一边
point.back() 最右用于二轮遍历找另一边

让端点入栈
不用vis记录因为要闭合需要入栈两次

两轮遍历保持同一个偏向以初始入栈的点为水平线 (假设先左后右，先下后上)
第一轮从左往右搜索下边
第二轮从右往左搜索上边

遍历结束，以最左端入栈结束，同时又是第一个入栈的 (入栈两次)
pop() 掉入栈两次的起点，获得凸包的点栈

// Andrew 算法
class Solution {
public:
    // 解决凸包问题中只要是正确的叉乘效果即可
    // p0p1 x p0p2     共起点p0
    inline int cross(vector<int>& p0, vector<int>& p1, vector<int>& p2) {
        int x0 = p1[0] - p0[0], y0 = p1[1] - p0[1];
        int x1 = p2[0] - p0[0], y1 = p2[1] - p0[1];
        return x0 * y1 - y0 * x1;
    }

    vector<vector<int>> outerTrees(vector<vector<int>>& points) {
        int n = points.size();
        if (n <= 3) {
            return points;
        }

        // 先按x轴排，再按y轴排
        // point.front() 最左     point.back() 最右
        sort(points.begin(), points.end(), [](vector<int>& a, vector<int>& b) {
            return a[0] != b[0] ? a[0] < b[0] : a[1] < b[1];
        });

        // 两轮循环分别求以stk.front()为水平线的上下一半
        stack<int> stk;
        // 因此该vis会像SPFA一样改值
        vector<bool> vis(n, false);

        // 最左点入栈
        stk.push(0);
        
        // 为了闭合，最左点要入栈两次，不用记录vis
        // 两轮保证一样的cross方向
        // 略过从左往右的起点
        for (int nex = 1; nex < n; nex++) {
            int cur = stk.top();
            stk.pop();
            // 保住首尾的一个元素
            while (stk.size() > (1 - 1) &&
                   cross(points[stk.top()], points[cur], points[nex]) < 0) {
                vis[cur] = false;
                cur = stk.top();
                stk.pop();
            }

            // 这里表示中转点cur可以接受nex点
            // 即朝内或平行
            stk.push(cur);
            stk.push(nex);
            vis[nex] = true;
        }

        int half = stk.size();
        // 略过从右往左的起点
        for (int nex = n - 2; nex >= 0; nex--) {
            // 该点已被上一轮记录过
            if (vis[nex]) {
                continue;
            }
            int cur = stk.top();
            stk.pop();
            // 保住上一轮搜索到的点
            while (stk.size() > (half - 1) &&
                   cross(points[stk.top()], points[cur], points[nex]) < 0) {
                vis[cur] = false;
                cur = stk.top();
                stk.pop();
            }
            
            // 这里表示中转点cur可以接受nex点
            // 即朝内或平行
            stk.push(cur);
            stk.push(nex);
            vis[nex] = true;
        }

        vector<vector<int>> ans;
        // 去掉重复加入的水平标志
        for (stk.pop(); !stk.empty(); stk.pop()) {
            ans.push_back(points[stk.top()]);
        }

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

END

相关阅读:
【07节】Python3+Selenium4自动化 unittest 测试框架详解
Qt5开发从入门到精通——第六篇三节（图像与图片——双缓冲机制）
GitHub上有哪些C++写的FTP库
[附源码]SSM计算机毕业设计智能视频推荐网站JAVA
极星开启「中国元年」
Sql语句的执行流程
【MySQL】MySQL架构
探究 Meme 的金融与社交属性
(JS逆向专栏九)某壳平台网站登入RSA
解读人工智能的理论基石

原文地址：https://blog.csdn.net/CUBE_lotus/article/details/125418673