凸包问题 --- 蛮力法，Graham扫描法

问题描述

给定一个平面上n个点的集合，它的凸包就是包含所有这些点的最小凸多边形，求取满足此条件的所有点。

另外，形象生动的描述：
（1）我们可以把这个问题看作如何用长度最短的栅栏把n头熟睡的老虎围起来。
（2）也可以这样看：请把所讨论的点想象成钉在胶合板上的钉子，胶合板代表平面。撑开一根橡皮筋圈，把所有的钉子都围住，然后啪一声松开手。凸包就是以橡皮圈为边界的区域。具体示意如下图所示：

蛮力法

• 解题思路：
  对于一个n个点集合中的两个点p1和p2，当且仅当该集合中的其它点都位于穿过这两点的直线的同一边时，它们的连线就是该集合凸包边界的一部分，简言之，p1和p2就是凸包问题中最小凸多边形的顶点。对每一对点都做一遍检验之后，满足条件的线段就构成了该凸包的边界。
  代码演示：

//凸包问题:蛮力法
#include <iostream>
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
struct node{int x;int y;
};
node p1[20],p2[20];
int a[20],m=0;
int jl;int getConvexPoint(node p[],int n)
{for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i == j){continue;}//获取直线方程的三个系数double a = p[i].y - p[j].y;double b = p[j].x - p[i].x;double c = p[i].x*p[j].y - p[i].y*p[j].x;//标记所有坐标中与直线距离的最大值和最小值double max=INT_MIN;double min=INT_MAX;for(int k = 0;k < n;k++){if(k == i || k ==j){continue;}jl = a*p[k].x + b*p[k].y + c;if(jl > max){max = jl;}if(jl < min){min =jl;}}//通过判断最大值和最小值是否同号，确定所有的坐标是否在同一方向。if(min*max >= 0){p2[m++]=p1[i];}}}return 0;
}bool compare(node p1,node p2)
{return p1.x < p2.x;
}int main()
{cout << "请输入坐标数：";int n;cin >> n;for(int i=0;i<n;i++){cin >> p1[i].x >> p1[i].y;}getConvexPoint(p1,n);cout << "其中坐标有：" << endl;sort(p2,p2+m,compare);for(int i=0;i<m;i++){if(p2[i].x==p2[i+1].x && p2[i].y==p2[i+1].y)continue;printf("(%d,%d) ",p2[i].x,p2[i].y);} cout << endl;return 0;
}

Graham扫描法

• 解题思路：
  Graham扫描的思想是先找到凸包上的一个点，然后从那个点开始按逆时针方向逐个找凸包上的点，实际上就是进行极角排序，然后对其查询使用。
  观察凸包：
  
  我们可以轻松看出向量p2p3是在p1p2的左边，向量p3p4在向量p2p3的左边。
  那么如果下一个向量在上一个向量的右边呢？
  
  由上图我们可以轻松看出，当向量p6p3在向量p2p6的右边时，p6实际上并不是凸包的顶点。
  由此我们只需要满足几个条件，我们就可以得到最终的凸包顶点：

1. 我们必须将平面上所有的点按照逆时针方向依次排好序，保证在遍历过程中我们能够扫描所有的点，而不会遗漏。
2. 我们必须确定p1,p2。即凸包边上相邻的两个顶点。
3. 判断向量p2p3是否在向量p1p2的左边。

如果满足以上条件的话，我们就可以通过遍历一个一个的把所有的凸包顶点找出来。

思路过程：
定义两个结构体数组p1[],p2[];p1[]用来存放所有坐标，p2[]用来存放凸包的顶点坐标。

1. 把所有点放在二维坐标系中，则纵坐标最小的点一定是凸包上的点，如图中的P0。
   
2. 计算各个点相对于 P0 的幅角 α ，按从小到大的顺序对各个点排序。当 α 相同时，距离 P0 比较近的排在前面。例如上图得到的结果为 P1，P2，P3，P4，P5，P6，P7，P8。我们由几何知识可以知道，结果中第一个点 P1 和最后一个点 P8 一定是凸包上的点。 （以上是准备步骤，以下开始求凸包）
3. 我们已经知道了凸包上的第一个点 P0 和第二个点 P1(已经满足第1，2个条件)。
4. 至于第3个条件，我们可以借助一下数学思想。（叉积）：当两个向量的叉积大于等于零时，则满足条件。反之则不满足条件。
5. 通过遍历依次判断每个坐标，当向量p2p3在向量p1p2右边时（如上图所示），我们需要回溯将之前存储在p2[]中的p2点删除，并将p3添加到p2[]中。
6. 就这样一直遍历下去。直到回到p0；

代码演示：

//凸包问题:扫描法
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node{int x;int y;
};
node p1[1000],p2[1000];
int number = 0;int cross(node a,node b,node c)//计算叉积，判断c在ab上还是下
{return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}double distance(node a,node b)
{return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}//排序查找第一个点
bool compare1(node a,node b)
{if(a.y != b.y){return a.y < b.y;}else{return a.x < b.x;}
}//根据极角排序
bool compare2(node a,node b)
{int x = cross(p2[0],a,b);if(x > 0){return 1;   }else if(x == 0){// 当向量fa和向量ab共线时，为避免影响后面判断，将a,b按照到f的距离排序return distance(p2[0],a) - distance(p2[0],b) <= 0;}else{return 0;}
}int getConvexPoint(node p[],int n)
{for(int i=2;i<n;i++){while(cross(p2[number-2],p2[number-1],p1[i])<0){number--;}p2[number++] = p1[i];}return 0;
}int main()
{cout << "请输入坐标数：";int n;cin >> n;for(int i=0;i<n;i++){cout << "请输入第" << i+1 << "个坐标：  " ;cin >> p1[i].x >> p1[i].y;}// 如果只有1-3个坐标，只需输出所有坐标，因为至少3点决定一个平面。if(n <= 3){cout << "坐标有：" << endl;for(int i=0;i<n;i++){printf("(%d,%d) ",p1[i].x,p1[i].y);}return 0;}//按照y排序，找到最下面的那个点，设为fsort(p1,p1+n,compare1);//p2[0]为最开始的第一个点。p2[number++] = p1[0];//按照极角排序。sort(p1+1,p1+n,compare2);p2[number++] = p1[1];getConvexPoint(p1,n);cout << "坐标有：" << endl;for(int i=0;i<number;i++){printf("(%d,%d) ",p2[i].x,p2[i].y);}cout << endl;return 0;
}