一、凸包定义
通俗的说就是：一组平面上的点，求一个包含所有点的最小凸多边形，这个最小凸多边形就是凸包。
二、Graham算法思想
概要：Graham算法的主要思想就是，最终形成的凸包，即包围所有点的凸多边形，假定多边形是按逆时针方向生成的，那么多边形内部包围的所有点与多边形每个有向边的关系都是：点在有向边的左边。依照此思想，只要找到一个出发点，然后依此出发点按逆时针方向构建多边形，并保证每加入一条有向边时，都要满足其余点都在该边的左边。
***点与线的关系
定义：平面上的三点P1(x1,y1),P2(x2,y2),P3(x3,y3)的面积量：
|x1 x2 x3|
S(P1,P2,P3) = |y1 y2 y3| = (x1-x3)*(y2-y3) - (y1-y3)*(x2-x3)
|1 1 1 |
当P1P2P3逆时针时S为正的，当P1P2P3顺时针时S为负的。
令矢量的起点为A，终点为B，判断的点为C，
如果S（A，B，C）为正数，则C在矢量AB的左侧；
如果S（A，B，C）为负数，则C在矢量AB的右侧；
如果S（A，B，C）为0，则C在直线AB上。
具体算法过程：
（1）输入：点集S={P}
（2）寻找基点P0：在所有点中找到y坐标最小的点，若找到多个，则选取其中X坐标最大的点作为基点，若只找到一个，则直接以这个点作为基点。
（3）排序：以基点为起点，以其余点为终点构成一个向量<P0,PK>，逐个计算每个向量与x轴正方向的夹角，并按夹角有小到大进行排序，得到一个排序的点S1={p0,p1,p2,p3…p(N-1)}；对于夹角相同的点，剔除掉离基点近的点，只保留离基点最远的那个点。
注意：由于计算角度复杂且耗时，在这里采用另外一种方式处理，根据上面的点线关系，从基点p0出发，依次遍历其它点，设为pk，p0和pk就构成一条有向向量，依次判断其它点（如pm）在向量的哪个方向，若在线段右边，则用其它点代替pk，构成一个新向量p0pm,继续判断剩余的点，这样一趟下来，就能找到最右边的点；依此道理判断其他点。如图：从向量p0p3（p3是任意选的，最终要将除p0外的所有点选到即可）开始，p1在向量p0p3左边，不变；p2在p0p3左边，向量不变；p4在p0p3右边，这时要将比较的向量变为p0p4；继续遍历p5，p5在p0p4右边，向量变为p0p5；继续遍历p6,p6在向量p0p5右边，向量变为p0p6；遍历p7，p7在向量p0p6右边，向量变为p0p7，这一趟下来就将p7这一个最右边的点找到了。同样的方法排序其他点，最后向量按与x轴正方向的顺序就是{p7,p6,p5,p4,p3,p2,p1},依次递增。
（4）构造凸包：
第一步：首先将基点p0入栈，p1和p2也依次入栈；
第二步：取栈顶的前两个点构成向量，即向量<p(k-1),pk>；
第三步：判断点p(k+1)是否在向量的左边；
第四步：
情况1:若在向量的左边，则将点p(k+1)入栈，重复第二步；
情况2：若在向量的右边，将点pk出栈，继续取下一个点，重复步骤二。
第五步：最后栈中存储的点就为凸包。
三、编程实现
1、判断点p3是否在p1p2左边函数。（注意计算机屏幕坐标系与数学直角坐标系，y轴方向相反）
int CMyMath::Isleft(Cpoint2D p1,Cpoint2D p2,Cpoint2D p3)
{
int s;
s = (p1.x-p3.x)*(p2.y-p3.y)-(p1.y-p3.y)*(p2.x-p3.x);
if (s<)
{
return ; //点在直线左侧（对屏幕坐标系）
}
else if (s>)
{
return ;//点在直线右侧
}
else
{
return ;//点在直线上
}
}
2、定义一个点类
class Cpoint2D
{
public:
Cpoint2D();
Cpoint2D(int x,int y);
virtual ~Cpoint2D();
public:
int id;
int x,y;
};
3、定义一个CGramhamCaclu类，用来生成凸包
class CGramhamCaclu
{
public:
CGramhamCaclu();
CGramhamCaclu(CGramhamCaclu& crah);
virtual ~CGramhamCaclu();
public:
CArray<Cpoint2D,Cpoint2D> InitialPoints;//保存最初点的集合
CArray<Cpoint2D,Cpoint2D> SortPoints; //保存排序后的点的集合
CArray<Cpoint2D,Cpoint2D> temparr;//用来起栈的作用，保存凸包中的点
int top1,top2;//栈顶前两项索引
int index; //基点的索引
public:
void DrawPoints(CDC* pDC);//画原始点
void DrawMinmumPolygon(CDC*pDC);//画凸包
void CaculTuBao();//计算凸包
protected:
void InitialSortPoints();
int FindBasePoint(CArray<Cpoint2D,Cpoint2D>& cp);//找基点
void Exchange(int index1,int index2);
bool Sort();//排序
void Stack();//构造凸包
};
4、CGramhamCaclu类详细代码
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
////////////////////////////////////////////////////////////////////// CGramhamCaclu::CGramhamCaclu()
{ }
CGramhamCaclu::CGramhamCaclu(CGramhamCaclu& crah)
{ }
CGramhamCaclu::~CGramhamCaclu()
{ }
///画原始点
void CGramhamCaclu::DrawPoints(CDC* pDC)
{
CPen * pen = new CPen(,,RGB(,,));
CPen * oldpen = pDC->SelectObject(pen);
int x,y;
for (int i=;i<InitialPoints.GetSize ();i++)
{
x = InitialPoints[i].x;
y = InitialPoints[i].y;
pDC->Ellipse(x-,y-,x+,y+);//画点
CString s;
s.Format("%d",i);
pDC->TextOut(x,y,s);//画序号
}
pDC->SelectObject(oldpen); }
//画凸包
void CGramhamCaclu::DrawMinmumPolygon(CDC* pDC)
{
CPen * pen = new CPen(,,RGB(,,));
CPen * pen1 = new CPen(,,RGB(,,)); int size = temparr.GetSize();
if (size>=)
{
CPen * oldpen = pDC->SelectObject(pen);
CString s("基点");
pDC->TextOut(InitialPoints[index].x,InitialPoints[index].y,s); //画每个点与基点构成的向量，可以不要
// for (int i1=1;i1<SortPoints.GetSize();i1++)
// {
// pDC->MoveTo(SortPoints[0].x,SortPoints[0].y);
// pDC->LineTo(SortPoints[i1].x,SortPoints[i1].y);
// }
pDC->SelectObject(oldpen); CPen * oldpen1 = pDC->SelectObject(pen1);
pDC->MoveTo(temparr[].x,temparr[].y);
for ( int i=;i<size;i++)
{
pDC->LineTo(temparr[i].x,temparr[i].y);
}
pDC->LineTo(temparr[].x,temparr[].y);
pDC->SelectObject(oldpen1);
} }
//凸包计算
void CGramhamCaclu::CaculTuBao()
{
if (InitialPoints.GetSize()>=)
{
InitialSortPoints();//初始化排序数组
CGramhamCaclu::index = FindBasePoint(SortPoints);//找基点
if (CGramhamCaclu::index>=)
{ Exchange(CGramhamCaclu::index,);
bool sort = Sort(); //排序
if (sort)
{
Stack();//栈操作
}
} }
}
//初始化排序数组
void CGramhamCaclu::InitialSortPoints()
{
if (InitialPoints.GetSize()>=)
{
for (int i=;i<InitialPoints.GetSize();i++)
{
SortPoints.Add (InitialPoints[i]);
}
}
} //找基点
int CGramhamCaclu::FindBasePoint(CArray<Cpoint2D,Cpoint2D>& cp)
{
Cpoint2D cpd;
int index =-;
CArray<int,int> carray;
if (cp.GetSize()>=)
{
index = ;
cpd = cp[];
//找一个y最大值
for (int i=;i<cp.GetSize();i++)
{
if (cpd.y<cp[i].y)
{
cpd = cp[i];
index = i;
}
}
//找所有y最大值
for (int j=;j<cp.GetSize();j++)
{
if (cp[j].y == cp[index].y)
{
carray.Add (j);
}
}
//找x最大值
if (carray.GetSize()>)
{
index = carray[];
for (i=;i<carray.GetSize();i++)
{
if (cp[index].x<cp[carray[i]].x)
{
index = carray[i];
}
}
} }
return index;
} //交换位置
void CGramhamCaclu::Exchange(int index1,int index2)
{
Cpoint2D temp;
temp = SortPoints[index1];
SortPoints[index1] = SortPoints[index2];
SortPoints[index2] = temp;
} //排序
bool CGramhamCaclu::Sort()
{
if (SortPoints.GetSize()<)
{
return false;
}
Cpoint2D basePoint = SortPoints[];
int isleft;
for (int i=;i<SortPoints.GetSize();i++)
{
for (int j=i+;j<SortPoints.GetSize();j++)
{
isleft = CMyMath::Isleft(basePoint,SortPoints[i],SortPoints[j]);
if (isleft==)
{
Exchange(i,j); } }
}
return true;
}
//构造凸包
void CGramhamCaclu::Stack()
{ if (SortPoints.GetSize()>=)
{
temparr.Add(SortPoints[]);
temparr.Add(SortPoints[]);
top1 = ;
top2 = ;
} int isleft;
for (int i=;i<SortPoints.GetSize();i++)
{
isleft = CMyMath::Isleft(temparr[top2],temparr[top1],SortPoints[i]);
if (isleft==)
{
temparr.Add(SortPoints[i]);
top1++;
top2++;
}
if (isleft==)
{
temparr.RemoveAt(top1,);
top1--;
top2--;
i--;
}
}
}
5、测试结果图
