凸包（Convex Hull）是一个计算几何（图形学）中的概念。在一个实数向量空间中，对于给定集合X，所有包含X的凸集的交集S被称为X的凸包。X的凸包可以用X内所有点(X1，...Xn)的凸组合来构造。在二维欧几里得空间中，凸包可想象为一条刚好包著所有点的橡皮圈。用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有的点。
Graham扫描法
image.png
- 将随机生成的点放在一个平面直角坐标系中，Y 轴中最小的点一定是凸包上面的点，并以此作为坐标的原点则P0。
- 以P0作为顶角，X 轴作为一条边其他顶点与 P0 连接生成第三边例如∠P1P0X 。
- 计算各个点相对于 P0 的幅角 α ，按从小到大的顺序对各个点排序。很容易得知 P1 和 P8 必为凸包上的点。当幅角 α 相同时将靠近P0的点排在前面。
- 将凸包上的点入栈，如 P1 入栈，并将 P0 与栈顶元素连接如 P0-P1。判断Pn+1 在 PO 与栈顶连线 L 的左边还是右边。如果在左边或在同一直线上时即将它与栈顶元素相连，显然 P2 与 P1连接。
- 将新连接线段的坐标与前一线段坐标进行叉积运算，如果叉积结果为负则必为凸包上的点将其入栈否则出栈，如果栈顶元素不是 幅角 α 最大的元素继续执行步骤4，否则结束当前栈中元素即为凸包上的顶点。
- 例如
按步骤 4 的做法已将P1 P2 P3 连接，{P1，P2}，{P2，P3} 进行叉积，所得到的结果为 + 则 P2 不是凸包上的点出栈，P3进栈返回执行步骤4。则需要判断 {Pn-1,Pn} {Pn,Pn+1} 的叉积。
矢量叉积定义
矢量叉积
设有点p0(x0,y0),p1(x1,y1),p2(x2,y2).（p0p1）,（p0p2）是共p0的两条向量，叉积d = （p0p1）x(p0p2) = (x1-x0)(y2-y0) - (x2-x0)(y1-y0)
叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系：
若 d > 0 , 则(p0p1)在(p0p2)的顺时针方向。
若 d < 0 , 则(p0p1)在(p0p2)的逆时针方向。(图示方向)
若 d = 0 , 则(p0p1)与(p0p2)共线，但可能同向也可能反向。
实现代码
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<stack>
6 #include <math.h>
7 #include <stdio.h>
8 #include <algorithm>
9 using namespace std;
10 struct point
11 {
12 long long x;
13 long long y;
14 } P[50005],S[50005]; //P 中存点，S模拟栈存凸包的点；
15
16 long long xx;
17 long long yy;
18
19 // 计算各个点相对于 P0 的幅角 α ，按从小到大的顺序对各个点排序。当 α 相同时，距离 P0 比较近的排在前面。
20 bool cmp(struct point a,struct point b)
21 {
22 if(atan2(a.y-yy,a.x-xx)!=atan2(b.y-yy,b.x-xx))
23 return (atan2(a.y-yy,a.x-xx))<(atan2(b.y-yy,b.x-xx));
24 return a.x<b.x;
25 }
26
27 //叉积判断点的位置
28 long long CJ(long long x1,long long y1,long long x2,long long y2)
29 {
30 return (x1*y2-x2*y1);
31 }
32
33 long long Compare(struct point a,struct point b,struct point c)
34 {
35 return CJ((b.x-a.x),(b.y-a.y),(c.x-a.x),(c.y-a.y));
36 }
37
38
39 int main()
40 {
41 int n,i,j;
42 while(~scanf("%d",&n))
43 {
44 int top = 1;
45 yy = 1000000+5;
46 for(i=0;i<n;i++)
47 {
48 scanf("%lld%lld",&P[i].x,&P[i].y);
49 if(P[i].y<yy)
50 {
51 yy = P[i].y;
52 xx = P[i].x;
53 j = i;
54 }
55 }
56 P[j] = P[0];
57 sort(P+1,P+n,cmp);
58 S[0].x = xx;
59 S[0].y = yy;
60 S[1] = P[1];
61 for(i = 2;i<n;)
62 {
63 if(top&&(Compare(S[top-1],S[top],P[i])<0)) top--;
64 else S[++top] = P[i++];
65 }
66 for(i=0;i<=top;i++)
67 printf("%lld %lld\n",S[i].x,S[i].y);
68 }
69 return 0;
70 }
菜鸡实现过程可能解释得不通顺，望请见谅。
网友评论