数几何

凸包

字数统计: 1.6k字   |   阅读时长: 7分
, , ,

摘要: 本文介绍计算几何中关于凸包的基本问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，在文章 向量的实现 中，我们实现了一个二维向量的代码模板，主要是 Vector2 这个类。

此后基于二维向量的代码模板，我们解决了计算几何中关于点、直线和线段、极角、多边形中的常见问题，以及力扣中的几个相关题目。

本文我们介绍凸包的算法原理和代码模板，有 Graham-Scan 和分治两种算法，代码依然使用 Vector2。然后解决力扣 587。

凸包的算法原理

定义

在一个实数向量空间V中，对于给定集合X，所有包含X的凸集的交集S被称为X的凸包。X的凸包可以用X内所有点 $(X1, \cdots Xn)$ 的凸组合来构造。

算法1: Graham-Scan 算法

点集按照 (x, y) 进行字典序排序，第一个和最后一个点一定是凸包上的点。它们之间的部分可以分成上下两条链分别求解。

(1) 求下侧链：

从小到大处理排序后的点，逐步构造凸包。把当前凸包的点维护在栈里，构造过程中的凸包末尾加上新的点后，可能会破坏凸性，此时只要将凹的部分的点从栈顶弹出。

(2) 求上侧链：

与求下侧链的过程一样，只是枚举点改为从大到小处理排序后的点。

代码模板

三点共线的时候，中间的点也算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<Vector2> convex_hull(vector<Vector2>& p)
{
    int n = p.size();
    sort(p.begin(), p.end());
    vector<Vector2> result(n * 2); // 栈
    int k = 0; // 当前的凸包点个数，即 result.size()
    // 构造凸包的下侧
    for(int i = 0; i < n; ++i)
    {
        while(k > 1 && (result[k - 1] - result[k - 2]).cross(p[i] - result[k - 1]) < 0)
            --k;
        result[k++] = p[i];
    }
    // 构造凸包的上侧
    int t = k;
    for(int i = n - 2; i >= 0; --i)
    {
        while(k > t && (result[k - 1] - result[k - 2]).cross(p[i] - result[k - 1]) < 0)
            --k;
        result[k++] = p[i];
    }
    result.resize(k - 1);
    return result;
}

算法2: 分治

点集按照 (x, y) 进行字典序排序，第一个和最后一个点一定是凸包上的点。它们之间的部分可以分成上下两条链分别求解。

上侧链和下侧链我们都可以用分治法来解决。以上侧链为例，写出分治法的【分解-解决-合并】框架。

假设上侧链的点集排序后为 vec，共 m 个点，其中 A = vec[0] 和 B = vec[m - 1] 是最左边和最右边的点。

1
2
3
4
5
6
分解: p_left, p_right 为当前子链的最左点和最右点，找到距离线段 p_left, p_right 最远的点 p_mid
      p_mid 一定在凸包上，将原问题分解为 [p_left, p_mid] 和 [p_mid, p_right] 两个子链。
      注意 p_mid 需要在 p_left, p_right 上方或共线，通过向量的方式判定即可
解决: 如果 p_left + 1 = p_right，直接返回 p_left, p_right 即可。
合并: [p_left, p_mid] 上的凸包为 convex_hull1， [p_mid, p_right] 上的凸包为 convex_hull2。
      将 convex_hull1, convex_hull2 连接一下即可，在连接之前需要把 convex_hull1 的最后一个元素弹出。

下面解决如何找到距离线段 p_left, p_right 最远的点 p_mid。通过计算的 p_left, p_right, p_mid 的面积即可。

找到使得三角形面积最大的 p_mid，同时 p_mid 需要在 p_left, p_right 的凸包方向上或者共线。

代码模板

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
list<Vector2> solve(vector<Vector2>& p, int left, int right)
{
    // 返回 p[left..right] 的凸包
    if(left + 1 == right)
        return list<Vector2>{p[left], p[right]};
    int mid = -1;
    double max_area = -1;
    for(int i = left + 1; i < right; ++i)
    {
        if(ccw(p[left], p[i], p[right]) > 0)
            continue;
        double area = (p[left] - p[i]).triangle_area(p[right] - p[i]);
        if(area > max_area)
        {
            max_area = area;
            mid = i;
        }
    }
    if(mid == -1)
        return list<Vector2>{p[left], p[right]};
    list<Vector2> convex_hull_left = solve(p, left, mid);
    list<Vector2> convex_hull_right = solve(p, mid, right);
    convex_hull_left.erase(--convex_hull_left.end());
    convex_hull_left.insert(convex_hull_left.end(), convex_hull_right.begin(), convex_hull_right.end());
    return convex_hull_left;
}

bool cmp(const Vector2& p1, const Vector2& p2)
{
    if(p1.x == p2.x)
        return p1.y < p2.y;
    return p1.x < p2.x;
}

vector<Vector2> convex_hull(vector<Vector2>& p)
{
    int n = p.size();
    sort(p.begin(), p.end(), cmp);
    vector<Vector2> p_up, p_down;
    p_up.push_back(p[0]);
    for(int i = 1; i < n - 1; ++i)
        if(ccw(p[0], p[i], p[n - 1]) < EPS)
            p_up.push_back(p[i]);
    p_up.push_back(p[n - 1]);
    p_down.push_back(p[n - 1]);
    for(int i = n - 2; i >= 1; --i)
        if(ccw(p[0], p[i], p[n - 1]) > -EPS)
            p_down.push_back(p[i]);
    p_down.push_back(p[0]);
    list<Vector2> convex_hull_up = solve(p_up, 0, p_up.size() - 1);
    list<Vector2> convex_hull_down = solve(p_down, 0, p_down.size() - 1);
    vector<Vector2> result(convex_hull_up.size() + convex_hull_down.size() - 2);
    int idx = 0;
    for(auto it = convex_hull_up.begin(); it != --convex_hull_up.end(); ++it)
        result[idx++] = *it;
    for(auto it = convex_hull_down.begin(); it != --convex_hull_down.end(); ++it)
        result[idx++] = *it;
    return result;
}

题目: 587. 安装栅栏

给定一个数组 trees，其中 trees[i] = [xi, yi] 表示树在花园中的位置。

你被要求用最短长度的绳子把整个花园围起来，因为绳子很贵。只有把 所有的树都围起来，花园才围得很好。

返回恰好位于围栏周边的树木的坐标。

示例 1:
输入: points = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
输出: [[1,1],[2,0],[3,3],[2,4],[4,2]]

示例 2:
输入: points = [[1,2],[2,2],[4,2]]
输出: [[4,2],[2,2],[1,2]]

注意:

1
2
3
4
1 <= points.length <= 3000
points[i].length == 2
0 <= xi, yi <= 100
所有给定的点都是 唯一 的。

代码 (C++)

本题是凸包的模板题，直接使用 Vector2 和 convex_hull 的代码模板，本题可以轻易解决。

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
class Solution {
public:
    vector<vector<int>> outerTrees(vector<vector<int>>& points) {
        int n = points.size();
        if(n <= 3)
            return points;
        vector<Vector2> p;
        for(int i = 0; i < n; ++i)
            p.emplace_back(points[i][0], points[i][1]);
        bool flag = true;
        for(int i = 0; i < n; ++i)
        {
            int j = (i + 1) % n;
            int k = (i + 2) % n;
            if(fabs(ccw(p[i], p[j], p[k])) > EPS)
            {
                flag = false;
                break;
            }
        }
        if(flag)
        {
            // 所有点共线
            return points;
        }
        vector<Vector2> ch = convex_hull(p);
        int m = ch.size();
        vector<vector<int>> result(m, vector<int>(2));
        for(int i = 0; i < m; ++i)
        {
            result[i][0] = ch[i].x;
            result[i][1] = ch[i].y;
        }
        return result;
    }
};
Share