文档介绍：螂凸包问题袂膈摘要:凸包问题是计算机几何中的一个经典问题,它要求将平面内的点集用最少的凸点将所有的顶点封闭。凸包问题的应用十分广泛,很多最优化问题经过抽象后可以发现它最终是凸包问题模型;它还可以用于人际关系网络的最小化搜索,薅通过人际关系,可以合理推断出某人的身份,职位等个人特征。目前求取凸包的常用算法有:穷举法,格雷厄姆扫描法(Graham),分治法,蛮力法和Jarris步进法。其中穷举法与蛮力法都是建立在穷举的算法思想上,它们的时间复杂度比较大,格雷厄姆扫描法采用几何方面的知识,降低了求解过程的时间复杂度。螅关键词:凸包问题;计算机几何;格雷厄姆扫描法羂蕿一、引言芇凸包问题的完整描述:令S是平面上的一个点集,封闭S中所有顶点的最小凸多边形,称为S的凸包,表示为CH(S)。如下图一所示,由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。薄羂图一羀凸包问题是计算机几何的一个经典问题,它可以解决很多优化模型,目前目前求取凸包的常用算法有:穷举法,格雷厄姆扫描法(Graham),分治法,蛮力法和Jarris步进法。本文主要讨论穷举法,蛮力法,以及格雷厄姆扫描法,通过算法思想的描述,计算出相应的时间复杂度,比较这几种算法的优劣。螅二、穷举法莃穷举法的思想很简单直接,它利用凸包性质—如果点集中的两个点的连线属于凸多边形的边,当且仅当点集中其余的点都在这两个点连线的同一侧。肂假设点集合S中有n个顶点,则这n个顶点共可以构成条边,对于任何一条边来讲,检查其余的n-2个点的相对于该直线段的正负性。如果它们有相同的正负性,说明该边是凸多边形的边,反之就不属于凸多边形,继续检查。算法流程图如下:莁蒆莆开始膂蒇膈从点集S中取出两个顶膄点u,v节袈蚆羃判断其余的n-2个点的相对于该直线段的正负性莂艿判断执行次数是否大于莈把u,v加入凸包 蚂蒂结束不相同 相同蚀螆螅薁袇薈蒄薁 N芈 Y羆芃 蚁图二:算法流程图袃羂上述算法(穷举法)需要执行n(n-1)/2次,再次检查n-2个点的正负性,故算法时间复杂性为=。显然这并非一个高效的算法凸包问题有许多更加有效的算法可以达到的渐近时间复杂度。薀三、蛮力法肅蛮力法求解凸包问题的基本思想:对于一个由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,因此,为了检验这些点是否位于这条直线的同一边,可以简单地把每个点代入方程ax+by=c,检验这些表达式的符号是否相同。此算法的时间复杂度同于穷举法,此算法的巧妙之处在于它对于判断剩余顶点是否在同一边的处理。由所有不同的点共组成了n(n-1)/2边,要对每条边都要对其他n-2个顶点求出在直线方程ax+by=c中的符号,所以,其时间复杂性是O(n3)。代码见附录一膅四:格雷厄姆扫描算法蚅格雷厄姆扫描法是利用平面上任