logo资料库

凸包问题解决.doc

发布时间：2022-06-15 发布人：admin 分类：说明书 资料大小：0.13M 资料格式：doc 举报 版权申诉
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
资料共6页，全文预览结束
    凸包问题 摘要：凸包问题是计算机几何中的一个经典问题，它要求将平面内的点集用最少 的凸点将所有的顶点封闭。凸包问题的应用十分广泛，很多最优化问题经过抽象 后可以发现它最终是凸包问题模型；它还可以用于人际关系网络的最小化搜索， 通过人际关系，可以合理推断出某人的身份，职位等个人特征。目前求取凸包的 常用算法有：穷举法，格雷厄姆扫描法（Graham），分治法，蛮力法和Jarris 步 进法。其中穷举法与蛮力法都是建立在穷举的算法思想上，它们的时间复杂度比 较大，格雷厄姆扫描法采用几何方面的知识，降低了求解过程的时间复杂度。 关键词： 凸包问题 ；计算机几何 ；格雷厄姆扫描法 一、引言 凸包问题的完整描述：令S 是平面上的一个点集，封闭S 中所有顶点的最小 凸多边形，称为S 的凸包，表示为CH（S）。如下图一所示，由红色线段表示的 多边形就是点集Q={p0,p1,...p12}的凸包。 图一 凸包问题是计算机几何的一个经典问题，它可以解决很多优化模型，目前目前求 取凸包的常用算法有：穷举法，格雷厄姆扫描法（Graham），分治法，蛮力法和 Jarris 步进法。本文主要讨论穷举法，蛮力法，以及格雷厄姆扫描法，通过算法 思想的描述，计算出相应的时间复杂度，比较这几种算法的优劣。 二、穷举法 穷举法的思想很简单直接，它利用凸包性质—如果点集中的两个点的连线属 于凸多边形的边，当且仅当点集中其余的点都在这两个点连线的同一侧。 假设点集合S中有n个顶点，则这n个顶点共可以构成 条边，对于任何 一条边来讲，检查其余的n-2 个点的相对于该直线段的正负性。如果它们有相同 的正负性，说明该边是凸多边形的边，反之就不属于凸多边形，继续检查。算法 流程图如下： 1) ( n n  2
    开始 从点集 S 中取出两个顶 点 u，v 判断其余的 n-2 个 点的相对于该直线 段的正负性 不相同 相同 把 u，v 加入凸包 判断执行次数是否 大于 1) ( n n  2 N Y 结束 图二：算法流程图 上述算法（穷举法）需要执行n(n-1)/2 次，再次检查n-2 个点的正负性，故算法 时间复杂性为  1) 2( n n  2 = 3( o n 。显然这并非一个高效的算法凸包问题有许多更 ) 加有效的算法可以达到 logn n 的渐近时间复杂度。 三、蛮力法 蛮力法求解凸包问题的基本思想：对于一个由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),让我们判  断 1 3 p p 的左方还是右方。判断方法,用叉积：  是位于 1 2 p p   1, 3 x y 1, 2 x y   1 y 1 y  ( 3 x  x 1)*( 2 y  y 1)  ( 2 x  x 1)*( 3 y  y 1)  D 3 x 2 x  在 1 2 p p  在 1 2 p p  与 1 2 p p  若 D>0,则 1 3 p p  若 D<0, 则 1 3 p p  若 D=0，则 1 3 p p 右侧，即在顺时针方向； 左侧，即在逆时针方向； 在同一条直线上。 算法 第一步：幅角排序。首先在点集中选取其中y坐标最小的那个点记为 0p ，连接 0p 到每个剩余点的线段，将这些线段按逆时针方向进行排序，第一条线段对应的另 一顶点标为 1p ，后续的线段依次这样标记过程如下图： 图三 第二步：幅角扫描。堆栈初始化为 CH（S）={pn-1,p0}，其中 p1 为栈顶元素。 按极坐标的幅角，从 p0 开始，到 pn-1 为止进行扫描。假定在某一时刻，堆栈 内容为：CH（S）={pn-1,p0,…, pi,pj,pk}其中，pk 为栈顶元素，则栈中元素按顺序构 p p p 构成的路径是 成一个半封闭的凸多边形。假设 lp 是正在扫描的点，如果 j k l 左转的，如下图三 b 所示，则由 k lp p 形成的边将是凸边，可以把作为半封闭的凸
    多边形中的一条边加入进来，因此把 lp 压入栈顶，把扫描线移到下一点；如果 p p p 构成的路径是右转的，则 kp 不可是凸包的极点，将弹出栈顶，而扫描线 j k l 仍然停留在 lp 上。如果构成的路径是右转的这样，在下一轮处理中，将由 i p p p l j 进行判断和作出处理。 图四 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）如果k
    参考文献： 杭电 ACM 课件-计算机几何讲解 刘东英 附录： 附录一:蛮力法代码 Void convex_hull() { int I,j,k,sign=0; double a=0,b=0,c=0; for(i=0;ic) ++sign; if ((a * my_point[k].x + b*mypoint[k].y)
    swap(S[i],S[0]); for (i=1;i=0) CHS[++sp]=T[k+1]; /* 若 ,T[k]压入栈顶，扫描线前移一点*/ else sp--; /* 否则，弹出栈顶元素*/ } }
    分享到：
    赞 收藏

    相关推荐

    资料库

    后端

    共收录2142份资料，累计10个分类，关注成员有19位，主要包括：Perl,Docker,Delphi,VB,PHP,Java,C,C#,Python,C++

    热门标签

    Perl Docker Delphi VB PHP Java C C# Python C++

    最新资料