凸包算法设计

凸包问题算法设计制作者：地信******2014.05.10凸包概念1.点集Q的凸包（convexhull）是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。右图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。2.一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题了。这可以形象地想成这样：在地上放置一些不可移动的木桩，用一根绳子把他们尽量紧地圈起来，并且为凸边形，这就是凸包了。算法：增量式算法,包裹法（Jarvis步进法）,葛立恒（Graham）扫描法,单调链,分治法,快包法（Akl-Toussaint启发式）等。1.1分治法的概念

所谓分治法就是把问题划分成多个子问题来进行处理。这些子问题，在结构上与原来的问题一样，但在规模上比原来的小。如果得到的子问题相对来说还大，可以反复地使用分治策略，把这些子问题再划分成更小的、结构相同的子问题。这样就可以使用递归的方法，分别求解这些子问题，把这些子问题的解结合起来，从而获得原来问题的解。化整为零，各个击破。1.2问题分析图（PFD图）

原问题的规模是n子问题1的规模小于n子问题2的规模小于n子问题1的解子问题2的解原问题的解1.3过程描述一般来说，分治法的求解过程由以下三个阶段组成：（1）划分：把规模为n的原问题划分为k个规模较小且

规模大致相同的子问题。（2）求解子问题：使用递归方法分别求解子问题。（3）合并：把各子问题的解合并起来，合并的代价因情况而异，分治算法的有效性很大程度上依赖于合并的实现。1.4凸包问题的分治思想：第一步：把给定点集中的点在横坐标方向上按照大小排序。

如下图所示，p1和pn必定是凸多边形的两个顶点。第二步：在上凸包点集合s1中找到一个距离直线最远点pmax，如下

图所示。显然直线段p1pmax与直线段pmaxpn把点集s1分成了三个集合。由凸包的性质可知p1，pmax，pn三点围成的三角形中的点不可能作为凸包的顶点，所以只需考虑直线p1pmax左边的点s11以及直线pmaxpn右边的点s12。第三步：递归求解得到凸多边形的边。第四步：合并这些边即得所求凸包。1.5凸包问题的分治算法算法：convex_divide()findtwo(MIN_Y,MAX_Y);//查找Y值最小和最大的两个点，作为初始凸包顶点initialmain(leftList,rightList,side,MIN_Y,MAX_Y);//由这两点确定的线段side，将平面的点分成相互独立的两部分，左边区域内的散点放在leftList中，右边的散点放在rightList中dealwith(side,leftList,resultList);dealwith(side,rightList,resultList);write(resultList);//输出凸包的顶点dealwith(VARside,list，resultList)//处理某一条边side及其所属的离散点集list，并把找到的凸包顶点放到凸包顶点集resultList中ifnotisEmpty(list)then{node:=LongNode(side,list);//找出list中离这条边最远的点，并把它从List中删除insert(resultList,side,node);//该点肯定是凸包的顶点，把它放到凸包顶点集的相应位置，该位置就在该边起点的后面Triangle:=createTriangle(side,node);//该点和原先的边生成一个三角形while(notisEmpty(list))do{Node:=GetNextNode(list);//从list中取出一个点，进行归边处理IfinTriangle(node,Triangle)//如果点在三角形内，则抛弃then

delete(node)else//点在三角形外，则判断其所属的边

if(attachSide(node,Lside,Rside)=left)

then

insert(LeftList,node);//该点属于Lside边放入leftList散点集中

else

insert(RightList,node);//处理属于Rside边，放入rightList集中}//list中所有点处理完毕dealwith(Lside,Leftlist,resultList);//处理属于Lside边及其所属的点dealwith(rside,rightlist,resultList);//处理属于Rside边及其所属的点}2.1凸包问题蛮力算法蛮力法求解凸包问题的基本思想：

对于一个由n个点构成的集合S中的两个点Pi和Pj，当且仅当该集合中的其他点都位于穿过这两点的直线的同一边时（假定不存在三点同线的情况），他们的连线是该集合凸包边界的一部分。对每一对顶点都检验一遍后，满足条件的线段构成了该凸包的边界。2.2具体描述

在平面上，穿过两个点(x1,y1)和(x2,y2)的直线是由下面的方程定义的：

ax+by=c(其中,a=y2-y1,b=x1-x2,c=x1y2-y1x2)（由(y-y₁)/(y₂-y₁)=(x-x₁)/(x₂-x₁)（两点式）

交叉相乘得：(y-y₁)(x₂-x₁)=(y₂-y₁)(x-x₁)

去括号整理可得：（y₂-y₁)x+(x₁-x₂)y-x₁y₂+x₂y₁=0

∴a=y₂-y₁b=x₁-x₂c=x₁y₂-x₂y₁）

这样一条直线把平面分成两个半平面：其中一个半平面中的点都满足ax+by＞c，另一个半平面中的点都满足ax+by＜c.

因此，为了检验这些点是否位于这条直线的同一边，可以简单地把每个点代入方程ax+by=c，检验这些表达式的符号是否相同。2.3算法设计算法：Voidconvex_hull(){inti,j,k,sign=0;//sign用于记录满足条件的点doublea=0,b=0,c=0;for(i=0;i<MAXNUM;++i)//MAXNUM

for(j=i+1;j<MAXNUM;++j)

{a=my_point[j].y–my_point[i].y;b=my_point[j].x–my_point[i].x;c=(my_point[i].x*my_point[j].y)–(my_point[i].y*my_point[j].x)sign=0;for(k=0;k<MAX_NUM;k++)//区域内的每个点都作检查{

if((k==j)||(k==i))

continue;//如果是i点或j点，应该排除掉

if((a*my_point[k].x+b*mypoint[k].y)==c)continue;//如果在线上也不行，因为i,j已经是两个相邻的点

if((a*my_point[k].x+b*mypoint[k].y)>c)++sign;//当代入结果大于0时，记sign为正

if((a*my_point[k].x+b*mypoint[k].y)<c)

--sign;//当代入结果小于0时，记sign为负}//如果所有的点都检查