凸包问题

凸包问题摘要：凸包问题是计算机几何中的一个经典问题，它要求将平面内的点集用最少的凸点将所有的顶点封闭。凸包问题的应用十分广泛，很多最优化问题经过抽象后可以发现它最终是凸包问题模型；它还可以用于人际关系网络的最小化搜索，通过人际关系，可以合理推断出某人的身份，职位等个人特征。目前求取凸包的常用算法有：穷举法，格雷厄姆扫描法（Graham），分治法，蛮力法和Jarris步进法。其中穷举法与蛮力法都是建立在穷举的算法思想上，它们的时间复杂度比较大，格雷厄姆扫描法采用几何方面的知识，降低了求解过程的时间复杂度。关键词：凸包问题；计算机几何；格雷厄姆扫描法一、引言凸包问题的完整描述：令S是平面上的一个点集，封闭S中所有顶点的最小凸多边形，称为S的凸包，表示为CH（S）。如下图一所示，由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。图一凸包问题是计算机几何的一个经典问题，它可以解决很多优化模型，目前目前求取凸包的常用算法有：穷举法，格雷厄姆扫描法（Graham），分治法，蛮力法和Jarris步进法。本文主要讨论穷举法，蛮力法，以及格雷厄姆扫描法，通过算法思想的描述，计算出相应的时间复杂度，比较这几种算法的优劣。二、穷举法穷举法的思想很简单直接，它利用凸包性质—如果点集中的两个点的连线属于凸多边形的边，当且仅当点集中其余的点都在这两个点连线的同一侧。假设点集合S中有n个顶点，则这n个顶点共可以构成(1)2nn条边，对于任何一条边来讲，检查其余的n-2个点的相对于该直线段的正负性。如果它们有相同的正负性，说明该边是凸多边形的边，反之就不属于凸多边形，继续检查。算法流程图如下：不相同相同NY图二：算法流程图上述算法（穷举法）需要执行n(n-1)/2次，再次检查n-2个点的正负性，故算法时间复杂性为2(1)2nn=3()on。显然这并非一个高效的算法凸包问题有许多更加有效的算法可以达到lognn的渐近时间复杂度。三、蛮力法蛮力法求解凸包问题的基本思想：对于一个由n个点构成的集合S中的两个点Pi和Pj，当且当该集合中的其他点都位于穿过这两点的直线的同一边时（假定不存在三点同线的情况），他们的连线是该集合凸包边界的一部分。对每一对顶点都检验一遍后，满足条件的线段构成了该凸包的边界。检验其余顶点是否同一边时，在平面上，穿过两个点(x1,y1)和(x2,y2)的直线是由下面的方程定义的：ax+by=c(其中a=y2-y1,b=x2-x1,c=x1y2-x2y1)这样一条直线把平面分成两个半平面：其中一个半平面中的点都满足ax+by＞c，另一个半平面中的点都满足ax+by＜c，因此，为了检验这些点是否位于这条直开始从点集S中取出两个顶点u，v判断其余的n-2个点的相对于该直线段的正负性判断执行次数是否大于(1)2nn把u，v加入凸包结束线的同一边，可以简单地把每个点代入方程ax+by=c，检验这些表达式的符号是否相同。此算法的时间复杂度同于穷举法，此算法的巧妙之处在于它对于判断剩余顶点是否在同一边的处理。由所有不同的点共组成了n(n-1)/2边，要对每条边都要对其他n-2个顶点求出在直线方程ax+by=c中的符号，所以，其时间复杂性是O(n3)。代码见附录一四：格雷厄姆扫描算法格雷厄姆扫描法是利用平面上任意3点所构成的回路是左转还是右转的判别法来求平面点集的凸包。三角区符号的计算：主要用于判断线段相对于基准线来讲，是位于基准线的左方还是右方。比如说平面上有3个点p1(x1,y1),p2(x2,y2),p3(x3,y3),让我们判断13pp是位于12pp的左方还是右方。判断方法,用叉积：31,31(31)*(21)(21)*(31)21,21xxyyDxxyyxxyyxxyy若D0,则13pp在12pp右侧，即在顺时针方向；若D0,则13pp在12pp左侧，即在逆时针方向；若D=0，则13pp与12pp在同一条直线上。算法第一步：幅角排序。首先在点集中选取其中y坐标最小的那个点记为0p，连接0p到每个剩余点的线段，将这些线段按逆时针方向进行排序，第一条线段对应的另一顶点标为1p，后续的线段依次这样标记过程如下图：图三第二步：幅角扫描。堆栈初始化为CH（S）={pn-1,p0}，其中p1为栈顶元素。按极坐标的幅角，从p0开始，到pn-1为止进行扫描。假定在某一时刻，堆栈内容为：CH（S）={pn-1,p0,…,pi,pj,pk}其中，pk为栈顶元素，则栈中元素按顺序构成一个半封闭的凸多边形。假设lp是正在扫描的点，如果jklppp构成的路径是左转的，如下图三b所示，则由klpp形成的边将是凸边，可以把作为半封闭的凸多边形中的一条边加入进来，因此把lp压入栈顶，把扫描线移到下一点；如果jklppp构成的路径是右转的，则kp不可是凸包的极点，将弹出栈顶，而扫描线仍然停留在lp上。如果构成的路径是右转的这样，在下一轮处理中，将由iljppp进行判断和作出处理。图四3．算法步骤：（1）求平面点集S中Y坐标最小的点p0。（2）以p0为源点，变换S-{p0}中所有点的坐标（3）以p0为源点，计算S-{p0}中所有点的幅角。（4）以幅角的非降排序S-{p0}中所有的点，令事件调度点T={p1,p2,…,pn-1}是排序过的数组。（5）初始化堆栈：令CHS[0]=pn-1，CHS[1]=p0；令堆栈指针sp=1，事件调度点数组T的下标k＝0。（6）如果kn-1，转步骤（7）；否则，算法结束。（7）计算CHS[sp-1]，chs[sp]=0p，T[K]所构成的三角区符号D，若D0,则sp++，CHS[sp]=T[k]，k++，转步骤（6）；否则，sp--转步骤（6）代码实现见附录二四、算法比较蛮力法和穷举法都是基于穷举思想的算法，它们的时间复杂度是解决凸包问题算法中最复杂的3()on，它们易于理解，适用于解决规模较小的问题。而格雷厄姆扫描算法的时间复杂度为(log)onn，它是解决此类问题的一个比较高效的一个算法。五、学习心得和体会通过此次对凸包问题的研究与学习，我了解到了数学思维对于算法设计的重要性，同时也认识到计算机几何对于问题处理的简化。用几何知识来解决一些较难的题目，有时会起到意想不到的效果。用数学方法解决问题永远要比计算机高效，有很多比较难的ACM竞赛题，它考的更多的是数学方法与计算机技术相结合的综合能力，在学好算法的同时，我们更应当学会用数学思维出看待和处理问题。参考文献：杭电ACM课件-计算机几何讲解刘东英附录：附录一:蛮力法代码Voidconvex_hull(){intI,j,k,sign=0;doublea=0,b=0,c=0;for(i=0;iMAXNUM;++i)for(j=j+1;jMAXNUM;++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;kMAX_NUM;k++){if((k==j)||(k==i))continue;if((a*my_point[k].x+b*mypoint[k].y)==c)exit(1);if((a*my_point[k].x+b*mypoint[k].y)c)++sign;if((a*my_point[k].x+b*mypoint[k].y)c)--sign;}if(((sign==(MAX_NUM-2))||((sign==(2-MAX_NUM))){printf(\n\n);my_point[i].flag=1;my_point[j].flag=1;}}printf(\n\n);}附录二：Voidconvex_hull(POINTS[],POINTCHS[],intn,int&sp{inti,k;floatD;SPOINTT[n];for(i=1;in;i++)/*s中Y坐标最小的点于S[0]*/if((S[i].yS[0].y)||((S[i].y=S[0].y)&&S[i].xS[0].x))swap(S[i],S[0]);for(i=1;in;i++){/*以S[0]为源点，变换S[i]的坐标于T[i-1]*/T[i-1].x=S[i].x-S[0].x;T[i-1].y=S[i].y-S[0].y;T[i-1].ang=atan(T[i-1].y,T[i-1].x);/*求T[i]的幅角*/}Sort(T,n-1);/*按T[i]幅角的非降顺序排序T[i]*/CHS[0].x=T[n-2].x;CHS[0].y=T[n-2].y;CHS[1].x=0;CHS[1].y=0;sp=1;k=0;While(kn-1){/*求栈顶两点及扫描线上一点构成的三角符号*/D=CHS[sp-1].x*CHS[sp].y+CHS[sp].x*T[k].y+T[k].x*CHS[sp-1].y-CHS[sp-1].y*CHS[sp].x-CHS[sp].y*T[k].x-T[k].y*CHS[sp-1].x;if(D=0)CHS[++sp]=T[k+1];/*若,T[k]压入栈顶，扫描线前移一点*/elsesp--;/*否则，弹出栈顶元素*/}}