(凸包问题.docVIP

凸包问题 摘要：Graham），分治法，蛮力法和Jarris 步进法。其中穷举法与蛮力法都是建立在穷举的算法思想上，它们的时间复杂度比较大，格雷厄姆扫描法采用几何方面的知识，降低了求解过程的时间复杂度。 关键词：一、引言S 是平面上的一个点集，封闭S 中所有顶点的最小凸多边形，称为S 的凸包，表示为CH（S）。如下图一所示，由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。 图一 凸包问题是计算机几何的一个经典问题，它可以解决很多优化模型，目前目前求取凸包的常用算法有：穷举法，格雷厄姆扫描法（Graham），分治法，蛮力法和Jarris 步进法。本文主要讨论穷举法，蛮力法，以及格雷厄姆扫描法，通过算法思想的描述，计算出相应的时间复杂度，比较这几种算法的优劣。 二、 穷举法的思想很简单直接，它利用凸包性质—如果点集中的两个点的连线属于凸多边形的边，当且仅当点集中其余的点都在这两个点连线的同一侧。 假设点集合S中有n个顶点，则这n个顶点共可以构成条边，对于任何一条边来讲，检查其余的n-2 个点的相对于该直线段的正负性。如果它们有相同的正负性，说明该边是凸多边形的边，反之就不属于凸多边形，继续检查。算法流程图如下： 不相同 相同 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)。代码见附录一 四：格雷厄姆扫描算法 格雷厄姆扫描法是利用平面上任意3 点所构成的回路是左转还是右转的判别法来求平面点集的凸包。 三角区符号的计算：主要用于判断线段相对于基准线来讲，是位于基准线的左方还是右方。比如说平面上有3个点p1(x1,y1),p2(x2,y2),p3(x3,y3),让我们判断是位于的左方还是右方。判断方法,用叉积： 若D0,则在右侧，即在顺时针方向； 若D0, 则在左侧，即在逆时针方向； 若D=0，则与在同一条直线上。 算法 第一步：幅角排序。首先在点集中选取其中y坐标最小的那个点记为，连接到每个剩余点的线段，将这些线段按逆时针方向进行排序，第一条线段对应的另一顶点标为，后续的线段依次这样标记过程如下图：  图三 第二步：幅角扫描。堆栈初始化为CH（S）={pn-1,p0}p1 为栈顶元素。按极坐标的幅角，从p0 开始，到pn-1 为止进行扫描。假定在某一时刻，堆栈内容为：CH（S）={pn-1,p0,…, pi,pj,pk}是正在扫描的点，如果构成的路径是左转的，如下图三b所示，则由形成的边将是凸边，可以把作为半封闭的凸多边形中的一条边加入进来，因此把压入栈顶，把扫描线移到下一点；如果构成的路径是右转的，则不可是凸包的极点，将弹出栈顶，而扫描线仍然停留在上。如果构成的路径是右转的这样，在下一轮处理中，将由进行判断和作出处理。