凸包算法

先理解下凸包

说凸包首先要说凸性的定义，简单点说就是平面邻域中任意两点所在的线段上的点都在该邻域中，则该邻域具有凸性。简单推敲一下，就可以发现如果邻域中存在一阶导数不连续的点一定无法被某点集线性表示出来。再往下的内容属于数学分析了，对我们的算法设计帮助不大，暂时先不管。

一般的计算几何问题都是处理的离散点集形成的平面域，所以我们感兴趣的是怎样找一个包含这个点集的面积最小的凸多边形，这就是凸包。作为常识也应该知道凸包上的顶点必然是该点集的子集，所以根据此性质我们就可以设计高效算法。

下面将介绍三种求平面点集凸包的方法，要特别注意求多边形的凸包和平面点集的凸包的联系，这样才有助于深入学习。

Gift wrapping method：这招我想还是不说了，因为我觉得应该不会有人会用，除了比较好理解外没什么好处。

Graham-Scan：这应该是最早的O(nlgn)算法了，实现也比较简单，其基本思想是维护一个凸曲线，因此它要求算法开始时必须至少知道一个必然在凸包上的点作为其始点（还好这比较简单）。它有个缺点就是直接用它去求一个给定多边形的凸包可能会导致错误（算法艺术上给了样例），因此算法开始前必须将点有序化。

Melkman：迄今为止最好的凸包算法了，我强烈推荐的算法。它的基本操作和Graham-Scan一样，只不过它在任意时候都求得当前已考察点所形成的凸包，所以它有一个无可比拟的优势就是它是一个在线算法（要想往点集中增加一个点不必重新计算）。对于给定一个多边形，它可以直接求其凸包而不用先有序化。而它还有个最大的好处是实现非常简单，所以特别适合比赛中使用。

虽说Melkman好，但是Graham_scan却是常用的

预备篇　点的排序与左转判定

点的排序

　　找给定点集的凸包，通常需要一些预处理过程，点的排序就是其中之一。下面给出一种将点按照一定规则排序的方法，这个预处理过程在很多凸包寻找算法中都扮演重要角色。

<?xml:namespace prefix = v ns = “urn:schemas-microsoft-com:vml” />

1.找一个必在凸包上的点（这很容易^_^，通常取横坐标或纵坐标最小的点），记为P0，

2.连结P0与其他点，分别计算这些线段与“竖直向下方向”的夹角，按照夹角由小到达的顺序将各线段的另一端（一端是P0）标号为P1、P2、P3……

左转判定

这是经典的计算几何学问题，判断向量p1=(x1,y1)到p2=(x2,y2)是否做左转，只需要判断x1*y2-x2*y1的正负，如果结果为正，则从p1到p2做左转。也就是向量的叉积。

Graham算法是这样的

1.将各点排序（请参看基础篇），为保证形成圈，把P0在次放在点表的尾部；

2.准备堆栈：建立堆栈S，栈指针设为t，将0、1、2三个点压入堆栈S；

3.对于下一个点i

　　　只要S[t-1]、S[t]、i不做左转

　　　　　就反复退栈；

　　　将i压入堆栈S

4.堆栈中的点即为所求凸包；

　　其核心用C语言表示，仅仅是下面一段：

t=-1;

s[++t]=0; s[++t]=1; s[++t]=2;

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

{

while (!left(s[t-1],s[t],i))

t–;

s[++t]=i;

}

比较完整的代码

int top;//凸包的顶点个数
struct point
{
int x,y;
}p[maxn],stack[maxn];

int max(int a,int b)
{
return a>b?a:b;
}

int dis(point p1,point p2)//两点的距离的平方
{
return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}

//叉积，结果小于表示向量p0p1的极角大于p0p2的极角，等于则两向量共线
int multi(point p1, point p2, point p0)
{

return (p1.x – p0.x) * (p2.y – p0.y) – (p2.x – p0.x) * (p1.y – p0.y);
}

int cmp(point a,point b)
{
if(multi(a,b,p[0])>0)
return 1;
if(multi(a,b,p[0])==0&&dis(a,p[0])<dis(b,p[0]))
return 1;
return 0;
}

//Graham_scan的精华
void Graham_scan(point p[],point stack[],int n)
{

int i,j,k=0;
top=2;
point temp;
//寻找最下且偏左的点
for(i=1;i<n;i++)
if(p[i].y<p[k].y||((p[i].y==p[k].y)&&(p[i].x<p[k].x)))
k=i;
//将该点指定为p【0】；
temp=p[0];
p[0]=p[k];
p[k]=temp;
//按极角从小到大，距离偏短进行排序

//以上是本质，如果按以上的写，可能会超时，还是用下面的sort
sort(p+1,p+n,cmp);
//核心
stack[0]=p[0],stack[1]=p[1],stack[2]=p[2];
for(i=3;i<n;i++)
{
  while(top>1&&multi(p[i],stack[top],stack[top-1])>=0)
   top–;
  stack[++top]=p[i];
}
}