凸包问题
摘要：凸包问题是计算机几何中的一个经典问题，它要求将平面内的点集用最少的凸点将所有的顶点封闭。凸包问题的应用十分广泛，很多最优化问题经过抽象后可以发现它最终是凸包问题模型；它还可以用于人际关系网络的最小化搜索，通过人际关系，可以合理推断出某人的身份，职位等个人特征。目前求取凸包的常用算法有：穷举法，格雷厄姆扫描法（Graham），分治法，蛮力法和Jarris 步进法。其中穷举法与蛮力法都是建立在穷举的算法思想上，它们的时间复杂度比较大，格雷厄姆扫描法采用几何方面的知识，降低了求解过程的时间复杂度。关键词：凸包问题；计算机几何；格雷厄姆扫描法
一、引言
凸包问题的完整描述：令S 是平面上的一个点集，封闭S 中所有顶点的最小凸多边形，称为S 的凸包，表示为CH（S）。如下图一所示，由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。
图一
凸包问题是计算机几何的一个经典问题，它可以解决很多优化模型，目前目前求取凸包的常用算法有：穷举法，格雷厄姆扫描法（Graham），分治法，蛮力法和Jarris步进法。本文主要讨论穷举法，蛮力法，以及格雷厄姆扫描法，通过算法思想的描述，计算出相应的时间复杂度，比较这几种算法的优劣。
二、穷举法
穷举法的思想很简单直接，它利用凸包性质—如果点集中的两个点的连线属于凸多边形的边，当且仅当点集中其余的点都在这两个点连线的同一侧。
假设点集合S 中有n 个顶点，则这n 个顶点共可以构成(1)
2n n -条边，对于任何一条边来讲，检查其余的n-2 个点的相对于该直线段的正负性。如果它们有相同的正负性，说明该边是凸多边形的边，反之就不属于凸多边形，继续检查。算法流程图如下：
不相同 相同
N
Y
图二：算法流程图
上述算法（穷举法）需要执行n(n-1)/2 次，再次检查n-2 个点的正负性，故算法
时间复杂性为2(1)2
n n -∑=3()o n 。显然这并非一个高效的算法凸包问题有许多更加有效的算法可以达到log n n 的渐近时间复杂度。
三、蛮力法
开始
从点集S 中取出两个顶 点u ，v 判断其余的n-2 个点的相对于该直线段的正负性 判断执行次数是否
大于(1)2n n - 把u ，v 加入凸包
结束
蛮力法求解凸包问题的基本思想：对于一个由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),让我们判断13p p 是位于12p p 的左方还是右方。判断方法,用叉积：
31,31
(31)*(21)(21)*(31)
21,21x x y y D x x y y x x y y x x y y --==-------
若D>0,则13p p 在12p p 右侧，即在顺时针方向；
若D<0, 则13p p 在12p p 左侧，即在逆时针方向；
若D=0，则13p p 与12p p 在同一条直线上。
算法
第一步：幅角排序。首先在点集中选取其中y 坐标最小的那个点记为0p ，连接0p 到每个剩余点的线段，将这些线段按逆时针方向进行排序，第一条线段对应的另一顶点标为1p ，后续的线段依次这样标记过程如下图：
图三
第二步：幅角扫描。堆栈初始化为CH （S ）={pn-1,p0}，其中p1 为栈顶元素。按极坐标的幅角，从p0 开始，到pn-1 为止进行扫描。假定在某一时刻，堆栈内容为：CH （S ）={pn-1,p0,…, pi,pj,pk}其中，pk 为栈顶元素，则栈中元素按顺序构成一个半封闭的凸多边形。假设l p 是正在扫描的点，如果j k l p p p 构成的路径是
左转的，如下图三b 所示，则由k l p p 形成的边将是凸边，可以把作为半封闭的凸
多边形中的一条边加入进来，因此把l p 压入栈顶，把扫描线移到下一点；如果
j k l p p p 构成的路径是右转的，则k p 不可是凸包的极点，将弹出栈顶，而扫描线
仍然停留在l p 上。如果构成的路径是右转的这样，在下一轮处理中，将由i l j p p p 进行判断和作出处理。
图四
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 （7）计算CHS[sp-1]，chs[sp]= 0p ，T[K]所构成的三角区符号D ，若D 0,则 sp++， CHS[sp]=T[k]，k++，转步骤（6）；否则，sp--转步骤（6） 代码实现见附录二 四、算法比较 蛮力法和穷举法都是基于穷举思想的算法，它们的时间复杂度是解决凸包问题算法中最复杂的3()o n ，它们易于理解，适用于解决规模较小的问题。而格雷厄 姆扫描算法的时间复杂度为(log) o n n，它是解决此类问题的一个比较高效的一个算法。 五、学习心得和体会 通过此次对凸包问题的研究与学习，我了解到了数学思维对于算法设计的重要性，同时也认识到计算机几何对于问题处理的简化。用几何知识来解决一些较难的题目，有时会起到意想不到的效果。用数学方法解决问题永远要比计算机高效，有很多比较难的ACM竞赛题，它考的更多的是数学方法与计算机技术相结合的综合能力，在学好算法的同时，我们更应当学会用数学思维出看待和处理问题。 参考文献： 杭电ACM课件-计算机几何讲解刘东英 附录： 附录一:蛮力法代码 Void convex_hull() { int I,j,k,sign=0; double a=0,b=0,c=0; for(i=0;i for(j=j+1;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 { 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) --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"); } 附录二： Void convex_hull(POINT S[],POINT CHS[],int n,int &sp { int i,k; float D; SPOINT T[n]; for (i=1;i if ((S[i].y swap(S[i],S[0]); for (i=1;i 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 (k 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]压入栈顶，扫描线前移一点*/ else sp--; /* 否则，弹出栈顶元素*/ } } 第65讲凸集与凸包 本节主要内容是：凸集、凸包的概念以及用凸集凸包来解有关的题．凸集：平面上的点集，如果任何两点在这个点集内，则连这两点的线段上的所有的点也在此点集内，就说该点集是一个凸集． 线段、射线、直线、圆及带形、整个平面等都是凸集． 两个凸集的交集还是凸集；任意多个凸集的交集也仍是凸集． 凸包：每个平面点集都可用凸集去盖住它，所有盖住某个平面点集的凸集的交集就是这个平面点集的凸包． 或者可以形象地说：如果把平面上的点集的每个点都插上一根针，然后用一根橡皮筋套在这些针外，当橡皮筋收紧时橡皮筋围出的图形就是这个点集的凸包． 平面点集的直径平面点集中的任意两点距离的最大值称为这个平面点集的直径． 例如，圆的直径就是其直径，有无数条；线段的直径就是其本身；正三角形的三个顶点组成的点集的直径就是其边长，有三条；平行四边形的直径是其较长的对角线；…． A类例题 例1定理任何一个平面点集的凸包是存在且唯一的． 分析存在惟一性的证明，即证明满足某条件的集A存在且惟一存在．通常先证明存在性，即证明有满足条件的集合A．再用反证法证明惟一性，即若满足条件的集A不惟一，或说明会引出矛盾，或得出其余集均必需与A相等的结论． 证明由于全平面是一个凸集，故任何平面点集都可用全平面盖住，即能被凸集盖住，从而盖住该凸集的所有凸集的交集存在，即凸包存在．而如果某个凸集A有两个凸包M1与M2，则M1∩M2也能盖住凸集A，且M1∩M2?M1，但M1是A的凸包，故M1?M1∩M2，故M1∩M2＝M1．同理M1∩M2＝M2．即M1＝M2． 例2 定理 如果一个点集M 是由有限个点组成，且其中至少有三个点不共线，则M 的凸包是一个凸多边形． 分析 可以构造一个寻找凸包的方法，来说明命题的正确性． 证明 由于M 为有限点集，故存在一条直线l ，使M 中的一个或几个点在l 上，其余的点 都在l 同旁(这只要任画一条直线，如果点集M 中的点在直线l 的两旁，则让直线按与此直线垂直的方向平移，即可得到满足要求的直线)． 取l 上的两个方向中的一个方向为正向，此时，按此正向，不妨设M 中不在l 上的点都 在l 的左边．在l 上沿其正向找出M 中的最后一个点A 1，把l 绕A 1逆时针旋转，直到遇到M 中的另外的点，又找出此时l 上的M 中的最后一个点A 2，此时再让l 绕A 2逆时针旋转，依此类推，直到最后绕A k 旋转又遇到A 1为止(由于M 是有限点集，故这样的旋转不可能一起下去)．这时，凸多边形A 1A 2…A k 即为M 的凸包． 情景再现 1．证明圆面(圆及圆内所有的点组成的集合)是凸集． 2．平面上任意给定5个点，其中任三点不共线，则可选出4个点，这四点能构成一个凸四边形的四个顶点． B 类例题 例3 海莱定理： 定理(海莱定理) 对于若干个(个数n ≥3)凸集，如果任意三个凸集都有一个公共点，那么存在一个点同时属于每个凸集． 分析 先证明简单情况，再用数学归纳法证明本定理． 证明 对于n ＝3，显然成立． 当n ＞3时，先取4个这样的凸集．F 1，F 2，F 3，F 4． A A A A 123k l l 1 算法分析与设计习题集整理 第一章算法引论 一、填空题： 1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。 2、多项式10()m m A n a n a n a =+++L 的上界为O(n m )。 3、算法的基本特征：输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为： O(n 3) 。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; } 6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。 7、算法设计的基本要求：正确性 和 可读性。 8、计算下面算法的时间复杂度记为： O(n 2) 。 for （i ＝1；i 目录 1031 输油管道问题 (2) 解题思路 (2) 程序代码 (2) 1032 邮局选址 (5) 解题思路 (5) 程序源代码 (5) 1034 集合划分2 (7) 解题思路： (7) 程序源代码： (7) 1033 集合划分 (9) 解题思路 (9) 程序源代码 (9) 1031 输油管道问题 解题思路 本题目可以分为两个步骤： 1、找出主管道的位置； 2、根据主管道的位置，计算各个油井到主管道的长度之和。 根据题意，设主管道贯穿东西，与y 轴平行。而各个子油井则分布在主输油管道的上下两侧。如下图： 由上图，其实只需要确定主管道的y 坐标，而与各个子油井的x 坐标无关！根据猜测，易知：主管道的y 坐标就是所有子油井y 坐标的中位数。（可以用平面几何知识证明，略） 求中位数的方法可以用排序后取a[(left+right)/2]，当然更推荐用书上的线性时间选择算法解决。记求得的主管道为m y ，最后要输出的结果只需要计算：1||n i m i y y =-∑，输出即可。 另外要提醒的是本题多Case 。 程序代码 #include //本函数求arr[p:q]的一个划分i，使arr[p:i-1]都小于arr[i]，arr[i+1,q]都大于arr[i] int partition(int *arr,int p,int q) { int index = p-1,start = p,base = arr[q]; for(;start 把点集凸包化Granham-Scan算法（使用水平序） #include 概念 凸包(Convex Hull)是一个计算几何（图形学）中的概念。用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有点的。严谨的定义和相关概念参见维基百科：凸包。 这个算法是由数学大师葛立恒(Graham)发明的，他曾经是美国数学学会(AMS)主席、AT&T首席科学家以及国际杂技师协会(IJA)主席。（太汗了，这位大牛还会玩杂技~） 问题 给定平面上的二维点集，求解其凸包。 过程 1. 在所有点中选取y坐标最小的一点H，当作基点。如果存在多个点的y坐标都为最小值，则选取x坐标最小的一点。坐标相同的点应排除。然后按照其它各点p和基点构成的向量 与 #include 凸包成形 (1)高凸包成形方法： 在MB板等产品上经常可以看到一些高度较高的凸包，如图（A）所示。 (2). 成形方法 产品的凸包高度（H）比较高，在一次抽凸成形时容易拉破。为了避免发生拉破现象 保证产品成形以后的形状尺寸，一般要分两步成形。 第一步：抽弧形。如上图(B),注意以下几个重点： A. 产品抽弧成形后的c和d两点间的周长L1(由三段弧长相加)应稍大于产品要求的 断面中a和b两点间的周长L2（a和b参见图A），一般L1＝L2+(0.2~0.8)mm. B. 下模入子c和d两点间的直线距离等于产品要求的断面中a和b两点间的直线距离D5。 C. 闭模时保证图中半径为r1的圆弧与下模最小间隙为产品材料厚度的百分之六十（T＊60%）。 第二步：整形。 有两种不同的整形方法。如图(C)和图(D)，一般用图(C)方法，凸包外形要求不高 时用图(D) 方法 (3). 确定抽弧形时冲子尺寸的步骤和方法： A. 根据产品要求的形状和尺寸确定下模入子内孔的形状尺寸。如图（E） 注意：a.C和d点间的直线距离等于产品要求的断面中a和b两点的直线距离D5。 b.入子内孔中圆弧半径r1的大小一般在1~3mm之间（含1和3mm）,以0.5mm 为一阶。初步确定取r1等于产品断面中相应处的半径r. B. 初步产品抽弧形时的外形尺寸： a. 如图（f）所示，以3点（下与下模入子内孔两r1圆弧的切点及抽凸底部的中点（g）作圆。 b. 经过修剪如图（g）所示，测出点c和点d间三段圆弧的总长度L1。 c. 如果此三段弧总长L1小于产品要求的断面中a和b两点间的周长L2，则通过把抽凸底部中点g向下移动一段距离h（h可以0.5mm为一阶）后得出点h,重新过三点作圆，如图（h）所示。 d. 重复步骤3.2.2.2和步骤3.2.2.3，直到满足L1＝L2+（0.2~0.8）mm。通过此方法求出产品抽弧形时的外形尺寸 C. 确定抽弧形冲子端部球体半径的方法： a. 以第3.3.2步确定的产品抽弧形时的外形尺寸偏移一个材料厚度。如图(I) b. 以下模入子内孔中半径为r1的两圆弧偏移T＊0.6%。如图(I) c. 用三点作圆的方法画出与步骤3.3.3.1和步骤3.3.3.2中确定的三段弧相切的 圆，此圆的半径R就是抽弧形冲子端部球体的半径R（取小数点后一位小数，但标注尺寸时精确到小数点后两位）。如图（J） D. 确定抽弧形冲子身部直径 a. 如果(B)确定的圆球心在产品材料上表面(即上脱板与材料接触面)以上时，圆球与产品材料上平面相交，就得出抽弧形部子身部的断面。如图(K)所示，D9 就是所求的抽弧形冲子身部的直径。 b.如果(B)确定的圆球圆心在产品材料上表面(即上脱板与材料接触面)与下表面 之间，就取抽弧形冲子的身段直径D9等于圆球的直径(即D9=2*R)，抽弧形 冲子的端部形状就是一半球体。如图(I) c. 如果(B)确定的圆球圆心在产品材料下表面(即下模板与材料接触面)以下时，必须请主管决定。 大学算法分析与设计复习总结 第1章绪论 考点： 1、算法的5个重要特性。（P3） 答：输入、输出、有穷性、确定性、可行性 2、描述算法的四种方法分别是什么，有什么优缺点。（P4） 答： 1.自然语言优点：容易理解；缺点：容易出现二义性，并且算法都很冗长。 2.流程图优点：直观易懂；缺点：严密性不如程序语言，灵活性不如自然语言。 3.程序设计语言优点：用程序语言描述的算法能由计算机直接执行；缺点：抽象性差，是算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。 4.伪代码优点：表达能力强，抽象性强，容易理解 3、了解非递归算法的时间复杂性分析。(P13) 要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。 非递归算法分析的一般步骤是： （1）决定用哪个（或哪些）参数作为算法问题规模的度量。 （2）找出算法的基本语句。 （3）检查基本语句的执行次数是否只依赖问题规模。 （4）建立基本语句执行次数的求和表达式。 （5）用渐进符号表示这个求和表达式。 [例1.4]：求数组最小值算法 int ArrayMin(int a[ ], int n) { min=a[0]; for (i=1; i 通用分支递归式： 使用扩展递归技术求解下列递推关系式（1） （2） 凸包问题 摘要：凸包问题是计算机几何中的一个经典问题，它要求将平面内的点集用最少的凸点将所有的顶点封闭。凸包问题的应用十分广泛，很多最优化问题经过抽象后可以发现它最终是凸包问题模型；它还可以用于人际关系网络的最小化搜索，通过人际关系，可以合理推断出某人的身份，职位等个人特征。目前求取凸包的常用算法有：穷举法，格雷厄姆扫描法（Graham），分治法，蛮力法和Jarris 步进法。其中穷举法与蛮力法都是建立在穷举的算法思想上，它们的时间复杂度比较大，格雷厄姆扫描法采用几何方面的知识，降低了求解过程的时间复杂度。关键词：凸包问题；计算机几何；格雷厄姆扫描法 一、引言 凸包问题的完整描述：令S 是平面上的一个点集，封闭S 中所有顶点的最小凸多边形，称为S 的凸包，表示为CH（S）。如下图一所示，由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。 图一 凸包问题是计算机几何的一个经典问题，它可以解决很多优化模型，目前目前求取凸包的常用算法有：穷举法，格雷厄姆扫描法（Graham），分治法，蛮力法和Jarris步进法。本文主要讨论穷举法，蛮力法，以及格雷厄姆扫描法，通过算法思想的描述，计算出相应的时间复杂度，比较这几种算法的优劣。 二、穷举法 穷举法的思想很简单直接，它利用凸包性质—如果点集中的两个点的连线属于凸多边形的边，当且仅当点集中其余的点都在这两个点连线的同一侧。 假设点集合S 中有n 个顶点，则这n 个顶点共可以构成(1) 2n n -条边，对于任何一条边来讲，检查其余的n-2 个点的相对于该直线段的正负性。如果它们有相同的正负性，说明该边是凸多边形的边，反之就不属于凸多边形，继续检查。算法流程图如下： 不相同 相同 N Y 图二：算法流程图 上述算法（穷举法）需要执行n(n-1)/2 次，再次检查n-2 个点的正负性，故算法 时间复杂性为2(1)2 n n -∑=3()o n 。显然这并非一个高效的算法凸包问题有许多更加有效的算法可以达到log n n 的渐近时间复杂度。 三、蛮力法 开始 从点集S 中取出两个顶 点u ，v 判断其余的n-2 个点的相对于该直线段的正负性 判断执行次数是否 大于(1)2n n - 把u ，v 加入凸包 结束 //纯代码 #include { min=j; } } temp=P[i]; P[i]=P[min]; P[min]=temp; } //数组两端相同x按|y|排序 //前端排序 px=P[0].x; pxnum=1; while(P[pxnum].x==px) { pxnum++; } for(i=0;i<=pxnum-2;i++) { //max=i; min=i; for(j=i+1;j<=pxnum-1;j++) { if( P[j].y < P[min].y ) { min=j; } } temp=P[i]; P[i]=P[min]; P[min]=temp; } //后端排序 px=P[n-1].x; pxnum=1; while(P[n-1-pxnum].x==px) { pxnum++; } for(i=n-pxnum;i<=n-2;i++) { min=i; 计算几何之凸包(一) {卷包裹算法} { 半个寒假都在写凸包 这几篇文章整理一下 主要介绍二维凸包的求解算法 以及一个简单的应用 ｝ ================================================== ================== 一.凸集&凸包 (下文中所有的集合若不作特殊说明都是指欧氏空间上的集合) 凸集(Convex Set):任意两点的连线都在这个集合内的集合就是一个凸集. A set in Euclidean space is convex set if it contains all the line segm ents connecting any pair of its points. https://www.doczj.com/doc/a5449894.html,/Convex.html 凸包(Convex Hull):包含集合S的所有凸集的交集就是集合S的凸包. The convex hull of a set of points S in N dimensions is the intersection of all convex sets containing S. 我们经常关注一个点集的凸包这也是计算几何学的一个基本问题 我们现在已经有成熟的算法可以求出平面点集的凸包和空间点集的凸包 甚至有的算法可以方便的求出任意维度欧氏空间内的一个点集的凸包 凸包有着优美而实用的性质我们可以利用凸包把一个杂乱的点集所包含的信息进行有效的概括梳理 ================================================== ================== 二.平面点集的凸包的算法 (下文中所有凸包若不作特殊说明都是指平面点集的凸包) 有两种直观的理解凸包的方式 在木板上钉钉子用一个有弹性的橡皮筋去框住所有钉子 橡皮筋形成的图形就是这个钉子所构成的点集的凸包 算法分析与设计 课程设计 题目：凸包问题 所属专业：信息与计算科学 年级：1121102 学生姓名：江浩2011213361 学生姓名：张鸿2011213363 学生姓名：杨永涛2011213374 指导教师：于洪 评定成绩： 关于凸包问题的分析与求解 摘要 本文针对凸包问题进行分析和讨论，首先对凸包进行定义性描述并对其做具体分析，它要求将平面内的点集用最少的凸点来封闭，然后给出其具体模型，并对模型进行分析和求解，最后我们讨论几种求解算法（包括穷举法，蛮力法和分治法）的优劣性并给出问题的算法代码。 关键词：凸包问题穷举法分治法 一．引言 凸包（Convex Hull）是一个计算几何（图形学）中的概念。用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的多边形，它能包含点集中的所有点。 凸包问题的完整描述如下： 令S 是平面上的一个点集，封闭S 中所有顶点的最小凸多边形，称为S 的凸包，表示为CH（S）。如下图一所示，由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。 图一 凸包问题是计算机几何的一个经典问题，它可以解决很多优化模型，目前目前求取凸包的常用算法有：穷举法，格雷厄姆扫描法（Graham），分治法，蛮力法和Jarris步进法。本文主要讨论穷举法，蛮力法，以及格雷厄姆扫描法。 二．问题分析 根据前面的描述我们先分析以下几种算法的特点： 1.穷举法 穷举法的思想很简单直接，它利用凸包性质—如果点集中的两个点的连线属于凸多边形的边，当且仅当点集中其余的点都在这两个点连线的同一侧。 假设点集合S中有n个顶点，则这n个顶点共可以构成 (1) 2 n n- 条边，对于任何一条边来讲， 检查其余的n-2 个点的相对于该直线段的正负性。如果它们有相同的正负性，说明该边是凸多边形的边，反之就不属于凸多边形，继续检查。穷举法需要执行n(n-1)/2次，再次检查n-2 个点的正负性，故算法时间复杂性为 2(1) 2 n n- ∑=3() o n。显然这并非一个高效的算法凸包 问题有许多更加有效的算法可以达到log n n的渐近时间复杂度。 算法流程图如下： 动态凸包最优算法实现及 程序演示 计算几何大作业 2015-6-14 计研142班范典2014210896 计算机系高性能所杨珂2014310561 计算机系高性能所曾开胜2014210957 1.程序演示说明 程序设计思路 希望实现一个带界面交互的REALTIME CONVEX HULL算法演示程序，由用户输入待求凸包的点集，分别采用OPTIMAL及DYNAMIC算法计算凸包，并将运算的实时结果与运算过程中维护的平衡树在窗口中显示。 演示程序由前端和后端两个部分组成，前端采集用户的输入信息，通过接口调用后端程序得到反馈，并将运算过程中的每个步骤按照一定的顺序呈现在界面中。后端算法接受前端界面的调用，通过两种算法实时计算当前点集对应凸包并将重点步骤以SNAPSHOT的形式储存。 程序界面概览 图 1 一组点集及其对应凸包与当前平衡树 图 2 另一组点集及其对应凸包与当前平衡树 图 3 右键菜单支持功能概览 程序功能说明 前端分为左右两个部分，左半部分为用户输入区域，可以通过鼠标点击指定下一个顶点的位置。右半部分为平衡树显示区域，显示当前凸包上各顶点在平衡树上的位置。 程序提供了三种显示模式，REALTIME模式直接显示新生成的凸包及平衡树的形状，DYNAMIC模式和OPTIMAL模式逐步显示搜索过程中每个时刻的变化，三种模式可以在过程中随时相互切换。 程序还提供了一些附加功能，比如速度调节，可以更清晰的观察到搜索的具体步骤，还支持单步的重放以及整体的重绘，功能比较完整且鲁棒，可以用于凸包算法的教学演示。 特别地，演示程序实现了输入点集与平衡树显示的互不干扰。每个步骤中被检查的关键顶点予以高亮显示。每个点的颜色不同，边界点与内部点的形状不同，以此进行区分。平衡树高度可以自适应调整等。 程序后端实现了两种不同复杂度的动态凸包算法，具体内容将在第二节中进行详细的描述。 编程环境说明 演示程序使用C++编程。大部分后端程序在Linux环境调试，前端显示部分在WINDOWS下使用VS2012平台配合OPENGL3.7完成。 2.算法原理 静态二维凸包算法 凸包（Convex Hull）是一个计算几何（图形学）中的概念。一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题了。这可以形象地想成这样：在地上放置一些不可移动的木桩，用一根绳子把他们尽量紧地圈起来，并且为凸边形，这就是凸包了。在二维欧几里得空间中，凸包可想象为一条刚好包著所有点的橡皮圈。用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有点的（具体的例子如图一所示）。 计算几何 大作业 三维凸包算法的实现及其动画演示 实验报告 小组成员： 软件学院 2014213460 孙聪 软件学院 2014213517 高莹 目录 1 程序演示说明 (1) 1.1网页服务器配置及项目运行说明 (1) 1.2 项目使用操作说明 (2) 1.3 动画说明 (7) 2算法与数据结构 (13) 2.1 储存网格模型的数据结构 (13) 2.2 朴素的增量法构造凸包 (15) 2.3 礼品包装法构造凸包 (17) 2.4 冲突图法构造凸包 (19) 2.5 分治法构造凸包 (20) 3性能测试 (24) 4参考文献 (25) 1 程序演示说明 本次实验采用js和html编写。除了打开保存文件功能（需配置服务器方能正常执行）之外，其余功能均可通过直接使用浏览器打开convex_demo.html文件得以体现。 注：因使用webgl技术，所以请使用各主流浏览器的较新版本的浏览器浏览。否则，可能出现无法正常显示与执行的情况。经测试，在较新版本的IE及Chrome浏览器下表现正常。 无论实在透视投影还是正交投影下，鼠标左键拖动为旋转几何体；右键拖动为移动几何体；鼠标滚轮控制视点的远近。 1.1网页服务器配置及项目运行说明 本项目在不同操作系统下，只需正确安装启动及设置Web服务器后，所有功能均可正常运行。 1.软件安装 1）软件下载地址https://www.doczj.com/doc/a5449894.html,/ 2）服务器启动问题说明：安装完成后，打开xampp控制面板，启动Apache。 ①若因端口80占用启动失败，则点击Config，选择Apache(httpd.conf)打开，修改端口。 修改“Listen 80”为“Listen 8081”； 修改“ServerName localhost:80”为“ServerName localhost:8081”； ②若因端口443占用启动失败，在Apache配置文件httpd.conf中，去掉“Include "conf/extra/httpd-ssl.conf"” 或者将占用相应端口的进程杀死，则不用修改相应的配置文件。 2.项目运行说明 1）将工程目录放在xampp安装目录/htdocs中 2）启动Apache服务器。 3）打开较新版本的IE及Chrome浏览器浏览器 输入localhost:80/ConvexHull/src/convex_demo.html 注：若前面修改过服务器端口，则需将80替换为修改的端口号 1.2 项目使用操作说明 1.点集操作 点集控制部分可以初始化需要生成凸包的点。 凸包成形冲模设计https://www.doczj.com/doc/a5449894.html,/Sheetmatal/Article60603_2.htm l 产品形状 在钣金产品上经常可以看到一些高度较高的凸包，如图1所示。 2 成形方法 产品的凸包高度H比较高，在一次抽凸成形时容易拉破。为了避免发生拉破现象，保证产品成形以后的形状尺寸，一般要分两步成形。 第1步：抽弧形。如图2所示，注意以下几个重点。 (1)产品抽弧成形后的c和d两点间的周长L1。(由3段弧长相加)应稍大于产品要求的断面中a和b两点间的周长L2(a和b参见图1)，一般L1=L2+(0．2—0．8)mm。 (2)下模镶块c和d两点间的直线距离等于产品要求的断面中a和b两点间的直线距离 D5。 (3)闭模时保证图2中半径为r1的圆弧与下模最小间隙为产品材料厚度的60％(Tx60％)。 第2步：整形。 有两种不同的整形方法。如图3和图4，一般用图3方法，凸包外形要求不高时用图4方法。 3 确定抽弧形时凸模尺寸的步骤和方法 (1)根据产品要求的形状和尺寸确定下模镶块内孔的形状尺寸，如图5所示。 注意：①c和d点间的直线距离等于产品要求的断面中a和b两点的直线距离D5； ②镶块内孔中圆弧半径rl的大小一般在1～3mm之间(含1mm和3mm，以0．5mm为一阶)。初步确定取r1等于产品断面中相应处的半径。 (2)初步产品抽弧形时的外形尺寸： ①如图6所示，以3点(下与下模镶块内孔两r1圆弧的切点及抽凸底部的中点g作圆； ②经过修剪如图7所示，测出点c和点d间3段圆弧的总长度L1； ③如果此3段弧总长L1小于产品要求的断面中a和b两点间的周长L2，则通过把抽凸底部中点g向下移动一段距离h(h可以0．5mm为一阶)后得出点H，重新过3点作圆，如图8所示； ④重复以上两个步骤画弧，直到弧长满足Ll=L2+(0．2-0．8)mm。如此即可求出产品抽弧形时的外形尺寸。 #include j--; }while(array[j].x>array[p].x); swap(array,i,j); }while(i 分治算法 小组的汇报内容： 一、分治算法的基本概念 (2) 二、分治算法的基本思想及策略 (2) 三、分治法适用的情况 (3) 四、分治法的基本步骤 (3) 五、分治法的复杂性分析 (4) 六、快速傅里叶变换 (5) 七、可使用分治法求解的一些经典问题 (9) 八、依据分治法设计程序时的思维过程 (9) 九、分治法与其它常见算法的比较 (9) 小组的分工情况： 彭勇讲前五个部分，天西山讲第六个部分，胡化腾讲最后三个部分，吕璐负责汇报的资料收集，小组分工以及最后的资料整理。 三、分治法适用的情况 分治法所能解决的问题一般具有以下几个特征： 1) 该问题的规模缩小到一定的程度就可以容易地解决 2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。 3) 利用该问题分解出的子问题的解可以合并为该问题的解； 4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。 第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加； 第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、 第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。 第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。 四、分治法的基本步骤 分治法在每一层递归上都有三个步骤： step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题； step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题 1．最大子段和问题：给定整数序列 n a a a ,,,21 ，求该序列形如 j i k k a 的子段和 的最大值： j i k k n j i a 1max ,0max 1) 已知一个简单算法如下： int Maxsum(int n,int a,int& best i,int& bestj){ int sum = 0; for (int i=1;i<=n;i++){ int suma = 0; for (int j=i;j<=n;j++){ suma + = a[j]; if (suma > sum){ sum = suma; besti = i; bestj = j; } } } return sum; }试分析该算法的时间复杂性。 2) 试用分治算法解最大子段和问题，并分析算法的时间复杂性。 3) 试说明最大子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。 （提示：令1()max ,1,2,,j k i j n k i b j a j n L ） 解：1）分析按照第一章，列出步数统计表，计算可得)(2 n O 2）分治算法：将所给的序列a[1:n]分为两段a [1:n/2]、a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有三种可能： ①a[1:n]的最大子段和与a[1:n/2]的最大子段和相同； ②a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同； ③a[1:n]的最大子段和为两部分的字段和组成，即 j n j i l n i j a a a a a 122； intMaxSubSum ( int *a, int left , int right){ int sum =0; if( left==right) sum = a[left] > 0? a[ left]:0 ; else {int center = ( left + right) /2; int leftsum =MaxSubSum ( a, left , center) ; int rightsum =MaxSubSum ( a, center +1, right) ; int s_1 =0; int left_sum =0; for ( int i = center ; i >= left; i--){ left_sum + = a [ i ]; if( left_sum > s1) s1 = left_sum; } int s2 =0; int right_sum =0; for ( int i = center +1; i <= right ; i++){ right_sum + = a[ i]; if( right_sum > s2) s2 = right_sum; } sum = s1 + s2; if ( sum < leftsum) sum = leftsum; if ( sum < rightsum) sum = rightsum; } return sum; } int MaxSum2 (int n){ int a； returnMaxSubSum ( a, 1, n) ; } 该算法所需的计算时间T(n)满足典型的分治算法递归分式T(n)=2T(n/2)+O(n)，分治算法的时间复杂度为O(nlogn)第65讲 凸集与凸包(原)
算法分析与设计习题集整理
分治算法例题
把点集凸包化Granham-Scan算法(使用水平序)概要
求凸包算法详解
Graham算法求凸包完整程序代码
打凸包
大学算法分析与设计复习总结
凸包问题
分治法--凸包
计算几何之凸包(一) {卷包裹算法}
凸包
动态凸包最优算法实现及 程序演示
三维凸包算法的实现及其动画演示
凸包成形冲模设计
分治法解决凸包问题
算法分析——分治法
算法分析习题详细答案五
相关主题
文本预览