




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
求最小凸包
——Graham算法——凸包概念凸包(ConvexHull)是一个计算几何(图形学)中的概念。用不严谨的话来讲,给定二维平面上的点集,凸包就是将最外层的点连接起来构成的凸多边型,它能包含点集中所有点的。
这个算法是由数学大师葛立恒(Graham)发明的,他曾经是美国数学学会主席,AT&T首席科学家以及国际杂技师协会主席。Graham算法是在某种意义上来说求解二维静态凸包的一种最优的算法,这种算法目前被广泛的应用于对各种以二维静态凸包为基础的ACM题目的求解。Graham算法的时间复杂度大约是nlogn,因此在求解二维平面上多个点构成的凸包时,消耗时间相对较少。Graham_scan算法1.在所有点中选取y坐标最小的一点H,当作基点。如果存在多个点的y坐标都为最小值,则选取x坐标最小的一点。坐标相同的点应排除。Graham_scan算法H2.然后按照其它各点p和基点构成的向量<H,p>与x轴的夹角进行排序,夹角由小到大进行逆时针扫描。并依次排序。Graham_scan算法H(P0)p10p8p9p7p6p4p3p2p1p14p13p12p11p53.将P0,P1,p2放入栈中。并将栈内的点依次排号并命名为Ai(i以0为起点),P0,P1必为凸包的两点Graham_scan算法H(P0)p10p8p9p7p6p4p3p2p1p14p13p12p11p0p1p2A0A1A2p53.以P1为基点,判断P1P2P3是否为逆时针方向,若是,P3进栈。再A2以为基点,判断A2A3P4。Graham_scan算法H(P0)p10p8p9p7p6p4p3p2p1p14p13p12p11p0p1p2A0A1A2p3A3p53.以A2为基点,判断A2A3P4是否为逆时针方向,若是,P4进栈,若不是,P3出栈,P4进栈。Graham_scan算法H(P0)p10p8p9p7p6P4P3p2p1p14p13p12p11p0p1p2A0A1A2P4(进)A3p5(出栈)(入栈)P3(出)3.继续以A2为基点,判断A2A3P5是否为逆时针方向。若是,P5进栈,若不是,P4出栈,P5进栈。Graham_scan算法H(P0)p10p8p9p7p6P4P3p2p1p14p13p12p11p0p1p2A0A1A2P5(进栈)A3P5P4(出栈)3.继续以A2为基点,判断A2A3P6,可知A2A3P6为逆时针方向,故A6进栈。Graham_scan算法H(P0)p10p8p9p7P6P4P3p2p1p14p13p12p11p0p1p2A0A1A2p5A3P5p6A4(保存)(进栈)4.以A3为基点,判断A3A4P7,按照前面的方法,可得保存P6,P7进栈;Graham_scan算法H(P0)p10p8p9p7P6(保存)P4P3p2p1p14p13p12p11p0p1p2A0A1A2p5A3P5p6A4p7A55.按照此方法,可得栈中的点依次为:Graham_scan算法H(P0)p10p8p9p7P6P4P3p2p1p14p13p12p11p0p1p2A0A1A2p5A3P5p6A4p10A5p11p12p14A6A7A8几何中心算法H(P0)p10p8p9p7P6P4P
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年医疗器械临床试验质量管理规范化与临床试验注册
- 矿山智能化开采中无人作业技术智能化数据分析与应用报告
- 企业集团账户管理办法
- 临时培训学员管理办法
- 保定爆竹烟花管理办法
- 2025年家具制造业个性化定制生产模式下的个性化设计软件应用报告
- 住宅新建项目管理办法
- 信息设备保密管理办法
- 云南花卉繁殖管理办法
- 临安社保征缴管理办法
- 哈尔滨市普通住宅小区物业服务等级指导标准
- 汉语文化传播研究:以中国语言文化为视角
- 电梯电气装置绝缘电阻检测记录
- 医疗机构消防安全管理
- 食堂食品安全应急处置方案
- 退出中华人民共和国国籍申请表
- 西方经济学(第二版)完整整套课件(马工程)
- 检验科安全管理制度汇总
- 英语音标拼读方法讲解
- MT 113-1995煤矿井下用聚合物制品阻燃抗静电性通用试验方法和判定规则
- GB/T 16841-2008能量为300 keV~25 MeV电子束辐射加工装置剂量学导则
评论
0/150
提交评论