Algorithm

浅谈凸包算法

文章目录
  1. 1. 如何定义凸包
  2. 2. 凸包算法中涉及到的平面几何
  3. 3. 平面点集凸包的算法
  4. 4. 算法实战
  5. 5. 完整代码

先前在算法分析A的第二期题库里遇到了凸包算法这个问题，当时找了一些视频和资料进行相关学习后解决了那个题，但是私以为自己对于凸包算法的学习仍然停留在一个很浅的层面上，所以今天打算重新学习，加深自己对于凸包算法的理解。

如何定义凸包

在一个实数向量空间 {\displaystyle V} V中，对于给定集合 {\displaystyle X} X，所有包含X的凸集的交集 {\displaystyle S} S被称为 {\displaystyle X} X的凸包。

凸包算法中涉及到的平面几何

首先定义二维向量<x1,y1>和<x2,y2>的叉积为一个实数Cp=x1y2-x2y1。
1.叉积的一半是一个三角形的有向面积；
2.向量的叉积的符号代表着向量旋转的方向。
向量的叉积是不满足交换律的，向量A乘以向量B，如果为正则为A逆时针旋转向B 否则为顺时针。
在代码描述的过程中采用逆时针来判断该点是否可以加入点集。

平面点集凸包的算法

这里主要讲Graham扫描法，其时间复杂度是O(nlogn)。
关于Graham扫描法，必须明确以下几点基本操作：
1.找到横坐标最小的点，如果x存在相同的情况，那么就找到y轴最小的点，然后把这个点作为基点；
2.计算出各点与基点的向量，然后进行排序；
3.删除在同一线上的点；
4.找到所有的极点放进vector；
5.取出vector中的向量进行计算。

算法实战

1.找基点

1
2
3
4
5
6
7
8
9
10
11
12
node minn;
int minid=-1;
minn.x=INF;
minn.y=INF;
for(int i=0; i<n; i++)
if(minn.x>Pos[i].x || minn.x==Pos[i].x&&minn.y>Pos[i].y)
{
    minn.x=Pos[i].x;
    minn.y=Pos[i].y;
    minid=i;
}
swap(Pos[minid],Pos[0]);

找到最小的点和初始点（0点）交换位置，让其作为基点。

2.按从小到大的顺序
自定义sort排序

1
2
3
4
5
6
7
8
9
10
11
bool cmp(node p1,node p2)
{
    int x1=p1.x-Pos[0].x;
    int y1=p1.y-Pos[0].y;
    int x2=p2.x-Pos[0].x;
    int y2=p2.y-Pos[0].y;
    int s=x1*y2-x2*y1;
    if(s>0 || s==0 && pow(x1,2)+pow(y1,2)>pow(x2,2)+pow(y2,2))
        return true;
    else return false;
}

算出两个点和基点的向量，然后计算叉积，因为是根据逆时针来寻找点，所以必须满足叉积(s)大于0，如果叉积等于0的情况下，那就判断向量的模长，取最大的。

3.删除同一条线上的点
同一条线上的点不需要进行计算，作为凸包的边即可，判断是否在同一条边上，以及计算面积的大小都可以用这个式子来进行判断。

1
2
3
4
int dig(node x0,node x1,node x2)
{
    return (x2.x-x0.x)*(x1.y-x0.y)-(x1.x-x0.x)*(x2.y-x0.y);
}

把上述的判断式子带入代码中进行判断

1
2
3
4
int num=2;
    for(int i=2;i<n;i++)
        if(dig(Pos[0],Pos[i],Pos[i-1])!=0)
            Pos[num++]=Pos[i];

4.找到所有极点
首先需要明确一个点，一个完整的凸包至少需要三个点，所以这里先将前三个点放到vector中。

1
2
3
4
vector<node>vc;
vc.push_back(Pos[0]);
vc.push_back(Pos[1]);
vc.push_back(Pos[2]);

OK，下面开始寻找所有的极点来完成整个凸包构造。

1
2
3
4
5
6
7
8
9
10
for (int i = 3; i < num; i++)
{
    int t = vc.size() - 1;

    while (vc.size() >= 3 &&(t = vc.size() - 1)&&(dig(vc[t - 1], vc[t], Pos[i]) >= 0))
    {
            vc.pop_back();
    }
    vc.push_back(Pos[i]);
}

5.计算凸包面积

1
2
3
4
5
6
7
8
9
10
11
12
double ans = 0;
while (vc.size() >= 2)
{
    int t = vc.size() - 1;
    double m = dig(vc[0], vc[t], vc[t-1])/2.0;
    if (m < 0)
    {
        m = -m;
    }
    ans += m;
    vc.pop_back();
}

完整代码

题目来源:

1
http://acm.swust.edu.cn/#/problems/249/285?_k=cro6lv

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <cstdio>
#include <vector>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <cmath>
using namespace std;
#define INF 0x3f3f3f3f
#define maxn 110

struct node
{
    int x,y;
} Pos[maxn];

bool cmp(node p1,node p2)
{
    int x1=p1.x-Pos[0].x;
    int y1=p1.y-Pos[0].y;
    int x2=p2.x-Pos[0].x;
    int y2=p2.y-Pos[0].y;
    int s=x1*y2-x2*y1;
    if(s>0 || (s==0 && pow(x1,2)+pow(y1,2)>pow(x2,2)+pow(y2,2)))
        return true;
    else
        return false;
}

int dig(node x0,node x1,node x2)
{
    return (x2.x-x0.x)*(x1.y-x0.y)-(x1.x-x0.x)*(x2.y-x0.y);
}

int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n;
        scanf("%d",&n);
        for (int i = 0; i < n; i++)
        {
            scanf("%d%d", &Pos[i].x, &Pos[i].y);
        }
        if (n <= 2)
        {
            cout << "0.0" << endl;
            continue;
        }
        node minn;
        int minid = -1;
        minn.x = INF;
        minn.y = INF;
        //找到最小的点
        for (int i = 0; i < n; i++)
        {
            if (minn.y > Pos[i].y || (minn.y == Pos[i].y&&minn.x>Pos[i].x))
            {
                minn = Pos[i];
                minid = i;
            }
        }
        swap(Pos[minid], Pos[0]);

        //因为0点已经被替换为最小值，所以从1开始
        sort(Pos + 1, Pos + n, cmp);
        vector<node>vc;
        int num = 2;

        //删除同一条线上的点
        for (int i = 2; i < n; i++)
        {
            if (dig(Pos[0], Pos[i - 1], Pos[i]) != 0)
            {
                Pos[num++] = Pos[i];
            }
        }
        vc.push_back(Pos[0]);
        vc.push_back(Pos[1]);
        vc.push_back(Pos[2]);

        //找所有极点
        for (int i = 3; i < num; i++)
        {
            int t = vc.size() - 1;

            while (vc.size() >= 3 &&(t = vc.size() - 1)&&(dig(vc[t - 1], vc[t], Pos[i]) >= 0))
            {
                vc.pop_back();
            }
            vc.push_back(Pos[i]);
        }
        double ans = 0;
        while (vc.size() >= 2)
        {
            int t = vc.size() - 1;
            double m = dig(vc[0], vc[t], vc[t-1])/2.0;
            if (m < 0)
            {
                m = -m;
            }
            ans += m;
            vc.pop_back();
        }
        printf("%.1lf\n", ans);
    }
    return 0;
}