您好,欢迎来到爱够旅游网。
搜索
您的当前位置:首页Graham扫描法解凸包问题

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(

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- igbc.cn 版权所有 湘ICP备2023023988号-5

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务