凸包是一个计算几何中的概念，其形式化定义为在一个实数向量空间$V$中，对于给定集合$X$，所有包含$X$的凸集的交集$S$被称为$X$的凸包。在二维欧几里得空间中，凸包可想象为将最外层的点连接起来构成的凸多边形，它能包含点集中所有的点。
常见的求解二维凸包的算法有很多种，这里只简单介绍一下Andrew算法。
以LeetCode587为例，这道题可以说是一道二维凸包的模板题。
Andrew算法正是用于求解凸包上的所有点（围成所有点的最小周长），其算法逻辑将凸包分为「上凸壳」和「下凸壳」，并分别求出，如下图所示，蓝色分割线将凸包分为两部分：
Andrew算法的流程如下：
- 1. 对所有点进行排序，先根据$x$坐标排升序，后根据$y$坐标排升序;根据$x$排升序的目的，是为了我们能够往一个方向画出凸包边缘（从左往右画出一半凸壳，从右往左画出另外一半），而将$y$升序目的是可以确保一旦我们现在从$a$到$b$进行连线，那么$a$到$b$之间的所有点能够确保被围住;
- 2. 使用栈来维护所有凸包上的点，或者说凸包上的边，会更为准确，因为凸包起点元素会在栈中出现两次（首尾），因此更为准确的描述应该是使用栈维护凸包的所有的边，栈中相邻元素即代表凸包上的一条边;
- 3. 分别「从左往右」和「从右往左」处理排序好的所有点，来分别画出凸包的上下两部分，根据画的是第一部分还是第二部分，维护栈内元的处理逻辑稍有不同：
- 第一部分(上凸壳):
- 3.1 若栈内元素少于2个，由于组成一条线至少需要两个点，说明此时第一条边都还没画出，直接将元素添加到栈中；
- 3.2 若栈内元素不少于2个，考虑是否要将栈顶的边删掉（由栈顶前两个元素组成的边）假设栈顶元素为$b$，栈顶元素的下一位为$a$，即栈顶存在一条$a$到$b$的边，当前处理到的点为$c$，此时我们根据$ac$边是否在$ab$边的顺时针方向来决定是否要将$ab$边去掉。
- 第二部分(下凸壳):
- 3.3 逻辑同理，唯一需要注意的是，第一部分的凸包边我们不能删去，假定处理完第一部分凸包，我们栈内有$m$个元素，我们需要将上述「栈顶元素不少于2个」的逻辑替换为「栈顶元素大于$m$个」，同时已参与到凸包第一部分的点，不能再考虑，因此需要额外使用一个$vis$数组来记录使用过的点。
为了方便取得栈顶的前两位元素，我们使用数组实现栈。
具体的AC代码如下：
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
| class Solution {
public:
vector<pair<int,int> > points;
pair<int,int> sub(pair<int,int> a,pair<int,int> b)
{
return make_pair(a.first-b.first,a.second-b.second);
}
double cross(pair<int,int> a,pair<int,int> b)
{
return a.first*b.second-a.second*b.first;
}
double getarea(pair<int,int> a,pair<int,int> b,pair<int,int> c)
{
return cross(sub(b,a),sub(c,a));
}
vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
int n=trees.size();
for(int i=0;i<n;i++) points.emplace_back(make_pair(trees[i][0],trees[i][1]));
sort(points.begin(),points.end());
vector<int> stack(n+10);
vector<int> vis(n);
int tp=0;
tp++;
stack[tp]=0;
for(int i=1;i<n;i++)
{
pair<int,int> c=points[i];
while(tp>=2)
{
pair<int,int> a=points[stack[tp-1]];
pair<int,int> b=points[stack[tp]];
if(getarea(a,b,c)<0)
{
vis[stack[tp]]=0;
tp--;
}
else break;
}
tp++;
stack[tp]=i;
vis[i]=1;
}
int size=tp;
for(int i=n-1;i>=0;i--)
{
if(vis[i]==1) continue;
pair<int,int> c=points[i];
while(tp>size)
{
pair<int,int> a=points[stack[tp-1]];
pair<int,int> b=points[stack[tp]];
if(getarea(a,b,c)<0) tp--;
else break;
}
tp++;
stack[tp]=i;
}
vector<vector<int>> ans;
for(int i=1;i<tp;i++)
{
vector<int> temp(2);
temp[0]=points[stack[i]].first;
temp[1]=points[stack[i]].second;
ans.emplace_back(temp);
}
return ans;
}
};
|
end☆~
