金字塔凸壳算法的研究与实现_学位论文.doc

《金字塔凸壳算法的研究与实现_学位论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、（此页为外封面，由专业复印室制作）分类号：密级：UDC：中国地质大学硕士学位论文金字塔凸壳算法的研究与实现硕士生：张忠武学科专业：计算机软件与理论指导教师：吴信才所在学院：信息工程学院二○一○年五月学校代码：10491研究生学号：120070899中国地质大学硕士学位论文金字塔凸壳算法的研究与实现硕士生：张忠武学科专业：计算机软件与理论指导教师：吴信才教授二○一○年五月ADissertationSubmittedtoChinaUniversityofGeosciencesfortheMasterDegreeofEngineeringResearchonandReali

2、zationofPyramidAlgorithmforConvexHullMasterCandidate：ZhangZhongwuMajor：ComputerSoftwareandTheorySupervisor：PorefssorWuXincaiChinaUniversityofGeosciencesWuhan430074P.R.China中国地质大学（武汉）研究生学位论文原创性声明本人郑重声明：本人所呈交的硕士学位论文《金字塔凸壳算法的研究与实现》，是本人在导师的指导下，在中国地质大学（武汉）攻读硕士学位期间独立进行研究工作所取得的成果。论文中除已注明部分外不包含

3、他人已发表或撰写过的研究成果，对论文的完成提供过帮助的有关人员已在文中说明并致以谢意。本人所呈交的硕士学位论文没有违反学术道德和学术规范，没有侵权行为，并愿意承担由此而产生的法律责任和法律后果。学位论文作者（签字）：日期：　　年　　月　　日作者简介张忠武，男，汉族，中共党员，1976年9月生，黑龙江省佳木斯市人。2007年9月至2010年6月就读于中国地质大学(武汉)研究生院攻读硕士学位，专业为计算机软件与理论，师从吴信才教授。硕士研究生期间完成高级计算机体系结构、计算机应用数学、算法设计与分析、计算几何及现代图形学等学位课程10门，空间数据库、地理信息系统技术与方法

4、、科学方法论等选修课程5门，共修29个学分，总平成绩82分。先后获得校级优秀研究生、校级学术活动先进个人、优秀高等教育科学研究成果奖等奖项。攻读硕士期间主持的研究课题1.研究生学术探索与创新基金立项“大型GIS中平面海量散乱点集的新凸壳算法研究”(项目编号:CUGYJS0808)。课题类别：校级2.佳木斯大学科学技术研究项目“金字塔凸壳算法的研究与实现”(项目编号:L2009-141)。课题类别：校级攻读硕士期间参加的研究课题1．黑龙江省教育厅基金资助项目“煤矿安全监测支持系统研究”(项目编号:11511408)。课题类别：省级攻读硕士学位期间发表论文及书籍：△张忠武

5、,吴信才.平面海量散乱点集凸壳算法[J].计算机工程,2009,35(9):43-45,48.△张忠武,吴信才.煤矿许用炸药检测中配气专家系统设计[J].微计算机信息,2009,25(6):38-40.△张忠武,史庆军.回溯算法在煤矿检验决策过程的应用[J].微计算机信息,2009,25(30):49-51.△参加撰写《面向对象程序设计（C++）》教材。副主编金字塔凸壳算法的研究与实现硕士生：张忠武导师：吴信才教授摘要计算几何是计算机算法研究领域中一个重要部分，而凸壳是计算几何中最普遍、最基本的一种结构，它被广泛地应用在模式识别、图象处理、图形学和人工智能等方面，在实

6、际应用过程中，许多问题都可以转化成凸壳问题来加以解决。作为多年来计算机研究领域的热点问题，目前已有不少凸壳算法，但随着实际问题所涉及的信息量不断增长，并且传统凸壳算法在处理海量数据方面不能满足用户的需要，因此本文将寻求一种新的基于海量数据的凸壳算法。作为解决各领域问题的基本方法，凸壳算法为高性能应用系统的研究与实现提供了稳健的基础算法。基本算法是研究问题的基础，基本算法的优劣直接关系整个应用程序运行效率。不同的算法有不同的应用环境，常用的传统凸壳基本算法总的来说都不适合海量数据情况下使用，为此提出了一个易于实现的新凸壳算法－金字塔算法。快速优化算法是高性能凸壳算法的核

7、心技术，旨在通过剔除海量数据中的更多无需参加遍历运算的内点，来提高海量数据的凸壳求取处理能力。目前国内外凸壳基本算法的研究主要集中在预先对数据进行排序的凸壳算法方面，而对基于无序海量数据的凸壳算法研究较少，将快速优化算法应用于无序的凸壳算法研究就更少，使得这方面研究进展一直微乎其微。而本文正是着眼于海量数据凸壳算法的研究，其目标是从海量数据自身特征及实际运算应用需求出发，提出一套海量数据凸壳基本算法和在此基础上的快速优化运算策略及应用机制，以实现在无序的平面点集环境下海量数据凸壳的高效求取。本文按照算法分析理论原则，对金字塔算法及其三种快速优化算法进