Graham扫描法解凸包问题

本篇是继续上篇的凸包问题的解法——将采用Graham扫描法来解凸包问题

我们再上一篇说到用分治法去解决凸包问题的最坏时间复杂度是O(n^2)。

那么利用Graham扫描法解决凸包问题可以降到O(nlogn)的量

Graham扫描法

我们可以采用一个贪心法的策略来解凸包问题

什么是贪心算法

我们区别于动态规划算法的那种从整体考虑部分，加以选择，而是从某种意义或者一些普遍真理的一种量度去达到局部的最优解。它是以贪心策略为准则进行考虑。也就是选取一个优秀的贪心策略能够让求解算法问题达到一种极致。

贪心算法运用贪心策略对每个子问题的解决方案都做出选择，不能回退。

好我们来看一下利用贪心法来解凸包问题

Graham扫描法

Graham采用了极坐标的贪心策略来很好的解决了该问题：
1、选取点集上最小的纵坐标的点，如果有多个，则选取横坐标最小的点（即最左边的点）。
2、以在第一步选取的这个点P0为基准，将剩下的点相对于P1以逆时针方向进行极角排序（即升序排序），如果夹角相同，距离p0近的编号小
3、将P0,P1的点加入栈。从编号为2的点依次遍历所有的点，每次取栈顶的两个点连城一条直线（方向由栈顶的第二个点指向栈顶）与当前的点pi比较，如果pi在直线的左侧pi直接入栈，如果pi在直线的右侧，弹出栈顶的一个点，继续取栈内两个点与pi比较，直到pi在直线的左侧将pi入栈。
4、栈内所有的点集就是问题的解

我们用几张图来说明下：
生成以下点，进行求解

选取纵坐标最小的点（如果有多个，那么最左边的点）

将剩下的点以相对于P0进行极角排序，如果夹角相同，距离p0近的编号小

将P0,P1入栈

将P2入栈，计算P3是否在P1P2的左侧

经计算，P3不在左侧，则P2出栈，P3入栈。计算P4是否在P1P3的左侧

经计算，P4在左侧，则P4入栈。计算P5是否在P3P4的左侧

经计算，P5在左侧，则P5入栈。循环到P7结束

我们先解决一个问题：关于极角的问题，什么是极角？极角排序怎么排？

极角是高中数学极坐标里面的东西，我对于极角的理解，就是以P0建立直角坐标系，连接pi与x轴正方向的夹角。

而对于怎么求，网上有很多方法，我这里提供一个方法就是求斜率的方法：
java里面有一个Math.atan2（double y,double x），它是用来：返回以弧度表示的 y/x 的反正切。y 和 x 的值的符号决定了正确的象限。
然后我们拿到这个值x，然后进行180/Math.PI*x （Math.PI是java里面封装的圆周率pai）。这样就求出来极角了。然后对极角排序，排序方法有很多。我还是觉得比较器是最好用的。其他的就不分析了，直接上代码：

public static Point ch[];
	public static int num=0;
	public static void main(String[] args) {
   
		// TODO Auto-generated method stub
		Point p[]= new Point[8];
		p[0] = new Point(2,0);
        p[1] = new Point(0,2);
        p[2] = new Point(0,-2);
        p[3] = new Point(