Graham算法.doc

Graham算法与二维静态凸包的论述
Graham算法是在某种意义上来说求解二维静态凸包的一种最优的算法，这种算法目前被广泛的应用于对各种以二维静态凸包为基础的ACM题目的求解。Graham算法的时间复杂度大约是nlogn，因此在求解二维平面上几万个点构成的凸包时，消耗的时间相对较少。
知识点：极角排序、栈的使用和叉积的应用
算法描述：
这里描述的Graham算法是经过改进后的算法而不是原始算法，因为改进之后的算法更易于对算法进行编码。
1） 已知有n个点的平面点集p（p[0]~p[n-1]），找到二维平面中最下最左的点，即y坐标最小的点。若有多个y值最小的点，取其中x值最小的点。
2） 以这个最下最左的点作为基准点（即p[0]），对二维平面上的点进行极角排序。
3） 将p[0]、p[1]、p[2]三个点压入栈中（栈用st表示，top表示栈顶指针的位置）。并将p[0]的值赋给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]）。
注意：由于第三步中，将p[0]的值赋给了p[n]，此时栈顶元素st[top]和st[0]相同，因为最后入栈的点是p[n]。
由于Graham算法是基于极角排序的，对平面上所有点极角排序的时间复杂度是nlogn，而之后逐点扫描的过程的时间复杂度是n，因此整个Graham算法的时间复杂度接近nlogn。
实现细节的注意事项：
1） 极角大小问题：
实际实现Graham算法的极角排序并不是真正的按照极角大小排序，因为计算机在表示和计算浮点数时会有一定的误差。一般会利用叉积判断两个点的相对位置来实现极角排序的功能。假设以确定平面中最下最左的点（基准点）P，并已知平面上其它两个不同的点A B。若点A在向量PB的逆时针方向，那么我们认为A的极角大于B的极角，反之A的极角小于B的极角（具体实现应借助叉积）。
2） 极角相同点的处理：
在Graham算法中，经常会出现两个点极角相同的情况。对于具有相同极角的两个不同点A B，那么我们应该把A B两点的按照距离基准点距离的降序排列。而对于完全重合的两点，可以暂不做处理。
代码实现（计算凸包的模版，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中。通过这些点，我们可以通过这些点来计算出很多与凸包有关的问题。

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

HRBUST 集训队