注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

Graham算法与二维静态凸包的论述  

2014-04-12 23:10:38|  分类: 计算几何 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |



Graham算法与二维静态凸包的论述



Graham算法是在某种意义上来说求解二维静态凸包的一种最优的算法,这种算法目前被广泛的应用于对各种以二维静态凸包为基础的ACM题目的求解。Graham算法的时间复杂度大约是nlogn,因此在求解二维平面上几万个点构成的凸包时,消耗的时间相对较少。



"Times New Roman";" >知识点:"Times New Roman";" >极角排序、栈的使用和叉积的应用



"Times New Roman";" >算法描述:



这里描述的Graham算法是经过改进后的算法而不是原始算法,因为改进之后的算法更易于对算法进行编码。



1)已知有n个点的平面点集pp[0]~p[n-1]),找到二维平面中最下最左的点,即y坐标最小的点。若有多个y值最小的点,取其中x值最小的点。



2)以这个最下最左的点作为基准点(即p[0]),对二维平面上的点进行极角排序。



3)p[0]p[1]p[2]三个点压入栈中(栈用st表示,top表示栈顶指针的位置)。并将p[0]mso-hansi-font-family:"Times New Roman";color:red;" >的值赋给p[n]



4)循环遍历平面点集p[3]p[n]。对于每个p[i]3<=i<=n)若存在p[i]在向量st[top-1]st[top]的顺时针方(包括共线)向且栈顶元素不多于2个时,将栈顶元素出栈,直到p[i]在向量st[top-1]st[top]的逆时针方向或栈中元素个数小于3时将p[i]入栈。



5)循环结束后,栈st中存储的点正好就是凸包的所有顶点,且这些顶点以逆时针的顺序存储在栈中(st[0]~st[top-1])。



"Times New Roman";color:red;" >注意:由于第三步中,将p[0]的值赋给了p[n],此时栈顶元素st[top]st[0]相同,因为最后入栈的点是p[n]



由于Graham算法是基于极角排序的,对平面上所有点极角排序的时间复杂度是nlogn,而之后逐点扫描的过程的时间复杂度是n,因此整个Graham算法的时间复杂度接近nlogn



"Times New Roman";" >实现细节的注意事项mso-hansi-font-family:"Times New Roman";" >:



1)极角大小问题:



实际实现Graham算法的极角排序并不是真正的按照极角大小排序,因为计算机在表示和计算浮点数时会有一定的误差。一般会利用叉积判断两个点的相对位置来实现极角排序的功能。假设以确定平面中最下最左的点(基准点)P,并已知平面上其它两个不同的点A B。若点A在向量PB的逆时针方向,那么我们认为A的极角大于B的极角,反之A的极角小于B的极角(具体实现应借助叉积)。



2)极角相同点的处理:



    Graham算法中,经常会出现两个点极角相同的情况。对于具有相同极角的两个不同点A B,那么我们应该把A B两点的按照距离基准点距离的降序排列。而对于完全重合的两点,可以暂不做处理。



"Times New Roman";" >代码实现(计算凸包的模版,G++):



#include<stdio.h>



#include<math.h>



#include<algorithm>



using namespace std;



struct Point



{



   
double x,y,len;



}Pt[20000],Stack[20000],Point_A;



double Cross(Point a,Point b,Point c)



{



   
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);



}



double Dis(Point a,Point b)



{



   
return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));



}



void FindPoint(int n)



{



   
int i,tempNumber=0;



   
Point tempPoint;



   
Point_A=Pt[0];



   
for(i=1;i<n;i++)



    {



       
if(Pt[i].y<Point_A.y||Pt[i].y==Point_A.y&&Pt[i].x<Point_A.x)



       
{



           
tempNumber=i;



           
Point_A=Pt[i];



       
}



    }



   
tempPoint=Pt[0];



   
Pt[0]=Pt[tempNumber];



   
Pt[tempNumber]=tempPoint;



}



bool Cmp(Point a,Point b)



{



   
double k=Cross(Point_A,a,b);



   
if(k>0) return true;



   
if(k<0) return false;



   
a.len=Dis(Point_A,a);



   
b.len=Dis(Point_A,b);



   
return a.len>b.len;



}



void Graham(int n)



{



   
int i,top=2;



   
Pt[n]=Pt[0];



   
Stack[0]=Pt[0];



   
Stack[1]=Pt[1];



   
Stack[2]=Pt[2];



   
for(i=3;i<=n;i++)



    {



       
while(Cross(Stack[top-1],Stack[top],Pt[i])<=0&&top>1)
top--;



       
Stack[++top]=Pt[i];



    }



}



int main(void)



{



   
int i,Num;



   
while(scanf("%d",&Num)!=EOF)



    {



       
for(i=0;i<Num;i++)
scanf("%lf%lf",&Pt[i].x,&Pt[i].y);



        FindPoint(Num);



       
sort(Pt,Pt+Num,Cmp);



       
Graham(Num);



    }



   
return 0;



}



通过上面的代码,我们已经计算出凸包中所有的点以逆时针顺序存储到Stack中。通过这些点,我们可以通过这些点来计算出很多与凸包有关的问题。



 



"Times New Roman";" >总结:Grahammso-hansi-font-family:"Times New Roman";" >算法是一种从某种意义上来说是计算二维静态凸包的最优算法,也是ACMer们必备的算法之一。但是Graham算法也有弊端,就是无法像增量法那样扩展到三维凸包的求解。而且如果我们想要了计算维动态凸包的每一个状态,那么Graham算法显然是不及增量算法更省时间。



 




  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017