凸包问题
更新时间:2024-05-20 13:53:01 阅读量: 综合文库 文档下载
凸包问题
摘要:凸包问题是计算机几何中的一个经典问题,它要求将平面内的点集用最少的凸点将所有的顶点封闭。凸包问题的应用十分广泛,很多最优化问题经过抽象后可以发现它最终是凸包问题模型;它还可以用于人际关系网络的最小化搜索, 通过人际关系,可以合理推断出某人的身份,职位等个人特征。目前求取凸包的常用算法有:穷举法,格雷厄姆扫描法(Graham),分治法,蛮力法和Jarris 步进法。其中穷举法与蛮力法都是建立在穷举的算法思想上,它们的时间复杂度比较大,格雷厄姆扫描法采用几何方面的知识,降低了求解过程的时间复杂度。 关键词: 凸包问题 ;计算机几何 ;格雷厄姆扫描法
一、引言
凸包问题的完整描述:令S 是平面上的一个点集,封闭S 中所有顶点的最小凸多边形,称为S 的凸包,表示为CH(S)。如下图一所示,由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。
图一
凸包问题是计算机几何的一个经典问题,它可以解决很多优化模型,目前目前求取凸包的常用算法有:穷举法,格雷厄姆扫描法(Graham),分治法,蛮力法和Jarris 步进法。本文主要讨论穷举法,蛮力法,以及格雷厄姆扫描法,通过算法思想的描述,计算出相应的时间复杂度,比较这几种算法的优劣。
二、穷举法
穷举法的思想很简单直接,它利用凸包性质—如果点集中的两个点的连线属于凸多边形的边,当且仅当点集中其余的点都在这两个点连线的同一侧。
n(n?1)假设点集合S中有n个顶点,则这n个顶点共可以构成2条边,对于任何
一条边来讲,检查其余的n-2 个点的相对于该直线段的正负性。如果它们有相同的正负性,说明该边是凸多边形的边,反之就不属于凸多边形,继续检查。算法流程图如下:
开始
不相同 判断其余的n-2 个点的相对于该直线段的正负性 相同 从点集S中取出两个顶 点u,v 把u,v加入凸包 判断执行次数是否 n(n?1)大于
2 N Y
结束 图二:算法流程图
上述算法(穷举法)需要执行n(n-1)/2 次,再次检查n-2 个点的正负性,故算法
n2(n?1)时间复杂性为?=o(n3)。显然这并非一个高效的算法凸包问题有许多更
2加有效的算法可以达到nlogn的渐近时间复杂度。 三、蛮力法
蛮力法求解凸包问题的基本思想:对于一个由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),让我们判????????????断p1p3是位于p1p2的左方还是右方。判断方法,用叉积:
D?x3?x1,y3?y1x2?x1,y2?y1?(x3?x1)*(y2?y1)?(x2?x1)*(y3?y1)
????????????若D>0,则p1p3在p1p2右侧,即在顺时针方向; ????????????若D<0, 则p1p3在p1p2左侧,即在逆时针方向; ????????????若D=0,则p1p3与p1p2在同一条直线上。
算法
第一步:幅角排序。首先在点集中选取其中y坐标最小的那个点记为p0,连接p0到每个剩余点的线段,将这些线段按逆时针方向进行排序,第一条线段对应的另一顶点标为p1,后续的线段依次这样标记过程如下图:
图三
第二步:幅角扫描。堆栈初始化为CH(S)={pn-1,p0},其中p1 为栈顶元素。按极坐标的幅角,从p0 开始,到pn-1 为止进行扫描。假定在某一时刻,堆栈内容为:CH(S)={pn-1,p0,…, pi,pj,pk}其中,pk为栈顶元素,则栈中元素按顺序构
成一个半封闭的凸多边形。假设pl是正在扫描的点,如果pjpkpl构成的路径是
左转的,如下图三b所示,则由pkpl形成的边将是凸边,可以把作为半封闭的凸多边形中的一条边加入进来,因此把pl压入栈顶,把扫描线移到下一点;如果
pjpkpl构成的路径是右转的,则pk不可是凸包的极点,将弹出栈顶,而扫描线
仍然停留在pl上。如果构成的路径是右转的这样,在下一轮处理中,将由piplpj进行判断和作出处理。
图四
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 代码实现见附录二 p0,T[K]所构成的三角区符号D,若D ?0,则 sp++, CHS[sp]=T[k],k++,转步骤(6);否则,sp--转步骤(6) 四、算法比较 蛮力法和穷举法都是基于穷举思想的算法,它们的时间复杂度是解决凸包问题算法中最复杂的o(n3),它们易于理解,适用于解决规模较小的问题。而格雷厄 姆扫描算法的时间复杂度为o(nlogn),它是解决此类问题的一个比较高效的一个算法。 五、学习心得和体会 通过此次对凸包问题的研究与学习,我了解到了数学思维对于算法设计的重要性,同时也认识到计算机几何对于问题处理的简化。用几何知识来解决一些较难的题目,有时会起到意想不到的效果。用数学方法解决问题永远要比计算机高效,有很多比较难的ACM竞赛题,它考的更多的是数学方法与计算机技术相结合的综合能力,在学好算法的同时,我们更应当学会用数学思维出看待和处理问题。 参考文献: 杭电ACM课件-计算机几何讲解 刘东英 附录: 附录一:蛮力法代码 Void convex_hull() { int I,j,k,sign=0; double a=0,b=0,c=0; for(i=0;i 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) if (((sign==(MAX_NUM-2))||((sign==(2- MAX_NUM))) { printf(\my_point[i].flag=1; my_point[j].flag=1; } } printf(\ } 附录二: 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 for (i=1;i 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--; /* 否则,弹出栈顶元素*/ } } } 附录二: 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 for (i=1;i 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--; /* 否则,弹出栈顶元素*/ } }
正在阅读:
凸包问题05-20
浓浓的书香作文800字06-18
珍惜时间小学生作文02-04
清华大学电气专业研究生介绍03-19
平面设计 - 实习报告 加日志doc06-08
黄岩区流动人口管理局门户网站建设费用预算11-08
新北师大版三年级数学下5单元面积教学设计09-19
2019年春八年级数学下册:2.2.1 第2课时 平行四边形的对角线的性质03-16
和时间赛跑作文500字07-16
在山的那边教学实录 - 图文07-01
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 凸包
- 问题
- 柱塞气举生产操作规程
- 装卸器项目可行性研究报告(目录) - 图文
- 暨大版古代汉语练习及答案
- 全国法院第二十届学术讨论会获奖名单
- TD-LTE载波聚合CA开局指导书
- 孙氏族谱
- 2006年安全工程师考试真题及答案(安全生产法及相关法律知识)
- 湖北农垦经济与社会发展
- 汽车4S店会计科目设置和使用规定
- 品质管理基本常识
- 林毅夫对话:经济学方法论篇
- 公司法复习题(部分答案)
- 2012护理工作计划
- 人教版六年级下册品德与社会各单元复习题(2)有答案
- 中小企业绩效考核存在的问题和解决方法
- 平度市石墨资源情况介绍
- 一课一练
- 市场推广总监个人简历求职简历
- 西藏2016年下半年监理工程师合同管理:承担违约责任的条件和原则
- 广州人力资源和社会保障信访部门依法分类处理群众诉求清单