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

（此页为外封面，由专业复印室制作）
分类号： 密 级：
UDC：

中国地质大学
硕士学位论文

金字塔凸壳算法的研究与实现

硕士生：张忠武
学科专业：计算机软件与理论
指导教师：吴信才
所在学院：信息工程学院

二○一○年五月
学校代码：10491 研究生学号：120070899

中国地质大学
硕士学位论文

金字塔凸壳算法的研究与实现

硕 士 生：张忠武
学科专业：计算机软件与理论
指导教师：吴信才 教授

二○一○年五月

A Dissertation Submitted to China University
of Geosciences for the Master Degree of Engineering

Research on and Realization of Pyramid Algorithm for Convex Hull

Master Candidate：Zhang Zhongwu
Major：Computer Software and Theory
Supervisor：Porefssor Wu Xincai

China University of Geosciences
Wuhan 430074 P. R. China

中国地质大学（武汉）研究生学位论文原创性声明

本人郑重声明：本人所呈交的硕士学位论文《金字塔凸壳算法的研究与实现》，是本人在导师的指导下，在中国地质大学（武汉）攻读硕士学位期间独立进行研究工作所取得的成果。论文中除已注明部分外不包含他人已发表或撰写过的研究成果，对论文的完成提供过帮助的有关人员已在文中说明并致以谢意。
本人所呈交的硕士学位论文没有违反学术道德和学术规范，没有侵权行为，并愿意承担由此而产生的法律责任和法律后果。

学位论文作者（签字）： 日期：　　年　　月　　日

作者简介

张忠武，男，汉族，中共党员，1976年9月生，黑龙江省佳木斯市人。2007年9月至2010年6月就读于中国地质大学(武汉)研究生院攻读硕士学位，专业为计算机软件与理论，师从吴信才教授。硕士研究生期间完成高级计算机体系结构、计算机应用数学、算法设计与分析、计算几何及现代图形学等学位课程10门，空间数据库、地理信息系统技术与方法、科学方法论等选修课程5门，共修29个学分，总平成绩82分。先后获得校级优秀研究生、校级学术活动先进个人、优秀高等教育科学研究成果奖等奖项。
攻读硕士期间主持的研究课题
1. 研究生学术探索与创新基金立项 “大型GIS中平面海量散乱点集的新凸壳算法研究”(项目编号:CUGYJS0808) 。课题类别：校级
2. 佳木斯大学科学技术研究项目“金字塔凸壳算法的研究与实现”(项目编号: L2009-141)。 课题类别：校级
攻读硕士期间参加的研究课题
1． 黑龙江省教育厅基金资助项目“煤矿安全监测支持系统研究”(项目编号: 11511408)。课题类别：省级
攻读硕士学位期间发表论文及书籍：
△张忠武,吴信才.平面海量散乱点集凸壳算法[J].计算机工程,2009,35(9):43-45,48.
△张忠武,吴信才.煤矿许用炸药检测中配气专家系统设计[J].微计算机信息,2009, 25(6):38-40.
△张忠武,史庆军.回溯算法在煤矿检验决策过程的应用[J].微计算机信息,2009,25(30):49-51.
△参加撰写《面向对象程序设计（C++）》教材。副主编

金字塔凸壳算法的研究与实现

硕士生：张忠武 导师：吴信才 教授

摘 要
计算几何是计算机算法研究领域中一个重要部分，而凸壳是计算几何中最普遍、最基本的一种结构，它被广泛地应用在模式识别、图象处理、图形学和人工智能等方面，在实际应用过程中，许多问题都可以转化成凸壳问题来加以解决。作为多年来计算机研究领域的热点问题，目前已有不少凸壳算法， 但随着实际问题所涉及的信息量不断增长，并且传统凸壳算法在处理海量数据方面不能满足用户的需要，因此本文将寻求一种新的基于海量数据的凸壳算法。
作为解决各领域问题的基本方法，凸壳算法为高性能应用系统的研究与实现提供了稳健的基础算法。基本算法是研究问题的基础，基本算法的优劣直接关系整个应用程序运行效率。不同的算法有不同的应用环境，常用的传统凸壳基本算法总的来说都不适合海量数据情况下使用，为此提出了一个易于实现的新凸壳算法－金字塔算法。快速优化算法是高性能凸壳算法的核心技术，旨在通过剔除海量数据中的更多无需参加遍历运算的内点，来提高海量数据的凸壳求取处理能力。目前国内外凸壳基本算法的研究主要集中在预先对数据进行排序的凸壳算法方面，而对基于无序海量数据的凸壳算法研究较少，将快速优化算法应用于无序的凸壳算法研究就更少，使得这方面研究进展一直微乎其微。而本文正是着眼于海量数据凸壳算法的研究，其目标是从海量数据自身特征及实际运算应用需求出发，提出一套海量数据凸壳基本算法和在此基础上的快速优化运算策略及应用机制，以实现在无序的平面点集环境下海量数据凸壳的高效求取。
本文按照算法分析理论原则，对金字塔算法及其三种快速优化算法进行了详细的阐述与理论分析。首先从算法的构建基础、算法的基本思想和算法的正确性分析，再到算法实现步骤的设计，最后结合实际运行数据，讨论算法的时间复杂度以及与其它凸壳算法执行效率的对比分析。本文工作主要从以下四个方面展开：
(1) 金字塔算法的提出
经典格雷厄姆扫描法在凸壳生成过程中不断有回溯过程出现，这是该算法在实际运行中的重要瓶颈。为了避免回溯过程的出现，可以通过回溯法的逆算法，分枝-限界方法来加以解决，进而提出一种新凸壳算法。该算法首先找出点集S中的最左最右的2个凸壳顶点，然后分别沿着顺时针和逆时针方向找出斜率最大和最小点。寻找到的这2个点必是凸壳顶点，再以这2点为起点循环下去，好像搭建金字塔一样，一层一层构建出点集S的凸壳边界BCH(S)。
(2) 应用动态塔尖快速遍历算法对新算法的改进
金字塔凸壳算法每次查找新顶点都要进行n次遍历，如果预先删除不可能是凸壳顶点的内点，则将大幅度提高算法运行效率。应用金字塔算法建立凸壳时，每次将生成两个新凸壳顶点，通过证明可以知道位于这两个点连线下方的点必定是凸包内点，可将其剔除。下一次在生成新凸包顶点时，就不必再进行n次比较，只需在剩余点中判断即可，从而减少搜索新顶点时点判定次数。这种算法实现比较简单，只需计算一个行列式即可剔除不可能成为凸包顶点的内点。
(3) 与以往的快速优化算法的结合
通过对金字塔凸壳算法的分析可知，要提高算法的时间效率，可从两方面入手：一是减少单次点集遍历次数n；二是减少凸包顶点个数h。传统快速凸壳求取算法是使用一种简单的方法找到一个凸包的边界，而被这个边界所包围的点不可能成为最终凸包的顶点，这样就可将这部分内点剔除出去，来达到减少单次点集遍历次数n的目的，进而提高基本算法执行效率。本文结合金字塔算法自身特点，将上述的传统快速凸壳算法改造成适应本算法的初始近似凸壳算法。点集分组算法则是从减少凸包顶点个数h角度提高执行效率的，将其与金字塔算法相结合，同样可以达到进一步优化金字塔算法的目的。通过与这两种快速算的结合，金字塔算法的时间效率提高了25~43倍。
(4) 金字塔算法与传统算法时间复杂度的比对分析
根据金字塔算法的基本原理和实现步骤可知，每找到一个顶点都需要遍历n次，若顶点个数为h则算法的时间复杂度为O(hn)。根据凸壳顶点与内点关系定理可知，实际应用当中凸壳顶点个数远远小于内点个数，所以在平面海量数据的凸壳求解过程中执行时间主要取决于n的数值。与动态塔尖快速遍历算法结合后，金字塔算法的时间复杂度提升为O(1/4hn)。为了便于对比，本文介绍两种传统的凸壳算法，并且两者都是基于无序点集的，一种是卷包裹法，其时间复杂度为O(n2)，另一种是增点递推法，其时间复杂度为O(2hn)。本文通过大量的实验对比也证明金字塔算法的时间效率高于上述两种同是基于无序的凸壳算法。
论文中的算法取得了如下结果：
(1) 金字塔算法的思想比较简洁易于实现，并且容易与快速算法相结合，达到进一步提高运算效率的目的。
(2) 对动态塔尖快速遍历算法，只需在塔尖区域上的点集中进行凸壳顶点查找运算，大大减少了实际处理过程中参加运算点的个数，提高了算法执行速度。
(3) 利用行列式能确定点与线位置关系的性质，回避了通过计算斜率最值来确定凸包顶点，并且避免了生成不正确凸壳和有漏点现象的出现。
(4) 初始近似凸壳算法以往确定近似凸包的边界时极点越多优化效率越高，但与动态塔尖快速遍历算法相结合时，4个极值点组成的四边形作为初始凸壳效率最佳。

关键词：凸壳 点集 加速 计算几何 边界

Research on and Realization of Pyramid Algorithm for Convex Hull
Master Candidate：Zhang Zhongwu Supervisor：Professor Wu Xincai
ABSTRACT
Computational geometry has always been an important part of computational algorithm, and convex hull is the most common and the most basic structure of computational geometry. Convex hull has been largely applied to various aspects like pattern recognition, image processing, graphics, and artificial intelligence. In practical application, many problems can be solved in the way of convex hull. Since convex hull is a hot topic of computational research field, there have been a number of algorithms for convex hull. But with the increasing amount of information involved in practical problems, a new algorithm for convex hull algorithm based on massive data is needed.
As a fundamental way to problems of various fields, algorithm for convex hull provides a steady basic algorithm for research on and realization of high performance application system. The quality of a basic algorithm is directly related to the efficiency of the whole application program.Different algorithms are applied to different situations. The traditional common algorithms are not feasible for massive data. Therefore,this thesis proposes a new algorithm which can be easily realized (i.e. pyramid algorithm for convex hull).Fast optimization algorithm is a core technology of high performance algorithm for convex hull. It aims to improve the calculating and processing capability of convex hull by leaving out more interior points of the massive data which are not needed in the calculation. At present, researches on basic algorithm at home and abroad mainly focus on those which sort data in advance. Researches based on unordered collection of data are relatively few and those which apply fast optimization algorithm to unordered data algorithm for convex hull are much fewer. Therefore, this thesis focuses on algorithm for convex hull based on massive data. Starting from the features of the massive data and the practical need of application, it aims to propose a set of methods for massive data algorithm for convex hull, a calculation strategy of fast optimization as well as an application system so as to realize a high efficient calculation of massive data convex hull in unordered plane point sets.
Based on algorithmic analysis theory, this thesis makes a detail elaboration and theoretical analysis of pyramid algorithm and its three fast optimization algorithms. Firstly, it makes an analysis of the constructed basis, the basic idea, and the correctness of algorithm. Then it designs the steps of algorithm implementation. At last, combined with practical operating data, it discusses the time complexity of algorithm and makes a contrastive analysis of its execution efficiency with other types of algorithm.
This thesis covers the following four main aspects:
(1) The proposal of pyramid algorithm
In the generation of convex hull, the classical Graham algorithm constantly results in backtracking. And this is an important bottleneck in practical implementation. To avoid the backtracking, we can propose a new algorithm by using the inverse algorithm of acktracking algorithm and branch and bound algorithm.This algorithm first finds out the two convex hull vertexes at the far left and the far right of the point set S. Then it finds out the maximum point and the minimum point in the clockwise direction and the anti-clockwise direction respectively. These two points much be the convex hull vertexes. Starting from these two points, the cycle continues. It seems like building a pyramid, which constructs the BCH(S) of the point set S.
(2) The improvement of the new algorithm with the fast traversal algorithm of dynamic spire
A basic algorithm would traverse n times when searching for a new vertex. But it would greatly increase the efficiency of algorithm by deleting the interior points which cannot be the vertexes of convex hull.With the pyramid algorithm,two new convex hull vertexes can be generated each time.It can be proved that points under the line of the two vertexes must be interior points and thus can be deleted.In this way,we do not need to make comparisons for n times in the generation of the next vertexes.What we need to do is to decide among the rest points. Therefore, it can reduce the number of times for judging the points when searching for the new vertexes.Meanwhile,the realization of this algorithm is relatively easy.Only a determinant is needed for deleting the interior points which cannot be the vertexes of convex hull.
(3) The combination with the previous fast optimization algorithm
The analysis of pyramid convex hull algorithm reveals that the efficiency of algorithm can be increased from two aspects: one is to reduce the number of times of single point set traversal (n); and the other is to reduce the number of vertexes of convex hull (h). The traditional fast algorithm finds the boundary of a convex hull in a simple easy way. The points surrounded by the boundary cannot be the vertex of the final convex hull and thus can be deleted. In this way, the number of times of single point set traversal (n) can be reduced and the execution efficiency of a basic algorithm can be increased. Combined with the features of pyramid algorithm, this thesis transforms the above mentioned traditional fast convex hull algorithm to the initial approximate algorithm suited to this one. The point set block algorithm increases the execution efficiency by reducing the number of vertexes of convex hull (h). It can also optimize the pyramid algorithm. Combined with these two fast algorithms, the efficiency of the pyramid algorithm can be increased by 25 to 43 times.

(4) A contrastive analysis of time complexity between pyramid algorithm and traditional algorithm
The basic principle of pyramid algorithm and its realization steps obviously reveal that each vertex needs n times of traversal. If the number of vertexes is h, the time complexity of algorithm is O(hn). According to the relation theorem between the vertex and the interior point, the number of vertexes is much fewer than that of interior points. Therefore, in the calculating process of convex hull based on massive spatial data, the time mainly depends on the value of n. After a combination with fast traversal algorithm of dynamic spire, the time complexity of pyramid algorithm has increased by O(1/4hn).For convenient contrast, this thesis introduces two traditional algorithms for convex hull, both of which are based on unordered point sets. One is Gift-Wrapping algorithm whose time complexity is O(n2), and the other is increasing point recurrence algorithm whose time complexity is O(2hn). With a large number of experiments, this thesis proves that the time efficiency of pyramid algorithm is higher than the above two algorithms based on unordered point sets.
The algorithm proposed in this thesis has made the following contributions:
（1）The idea of the algorithm is simple and easy to realize. Besides, it is easy to be combined with fast algorithm so as to attain the goal of increasing the efficiency of calculating.
（2）As to the fast traversal algorithm of dynamic spire, what one needs to do is only to search the points in the point set of the spire and then calculate. This algorithm largely reduces the number of points in practical treatment process and thus improves the execution efficiency of algorithm.
（3）The use of determinant can determine the relation between points and lines. In this way, it needn’t determine the vertexes of convex hull by calculating the maxima and the minima of the gradients.
（4）When applying the initial approximate algorithm for determining the boundary of approximate convex hulls, the more there are the poles, the higher the optimization efficiency is. However, after a combination with the fast traversal algorithm of dynamic spire, the efficiency will be the best if the quadrilateral formed by the four poles serves as the initial convex hull.

Key Words: convex hull, point set,acceleration, computational geometry, boundary

目 录

第一章 引 言 1
§1.1 研究的目的及意义 1
§1.2 凸包的研究现状及进展 2
§1.3 研究的主要内容 3
§1.4 本论文的内容安排 4
第二章 凸包的概念及定理 6
§2.1 凸包的基本概念 6
§2.2 凸包生成的相关定理 8
§2.3 本章小结 9
第三章 金字塔凸壳算法 10
§3.1 传统凸包经典算法 10
3.1.1 卷包裹算法 10
3.1.2 增点递推算法 12
§3.2 金字塔算法整体思路 14
3.2.1 新算法的构建基础 14
3.2.2 金字塔凸壳算法的基本思想 15
3.2.3 金字塔算法的正确性分析 17
§3.3 金字塔算法具体步骤 17
3.3.1 金字塔凸壳算法的算法步骤 17
3.3.2 获取斜率值最大或最小点的改进方法 19
3.3.3 改进后的金字塔凸壳算法步骤 21
3.3.4 金字塔算法时间效率分析 23
3.3.5 金字塔算法优缺点的分析 26
§3.4 本章小结 26
第四章 快速优化算法与金字塔算法的结合 28
§4.1 快速优化凸壳算法的思想 28
§4.2 动态塔尖快速遍历算法 29
4.2.1 动态塔尖快速遍历算法的基本思想 29
4.2.2 剔除内点的方法 30
4.2.3 与动态塔尖快速遍历算法结合的金字塔算法步骤 31
4.2.4 与动态塔尖快速遍历算法结合后的金字塔算法时间效率分析 33
4.2.5 动态塔尖快速遍历算法优缺点的分析 35
§4.3 初始近似凸壳算法 35
4.3.1 初始近似凸壳算法的工作原理 36
4.3.2 初始近似凸壳算法实现 36
4.3.3 初始近似凸壳算法的加速效果分析 37
§4.4 点集分组计算法 38
4.4.1 点集分组计算法的引入 38
4.4.2 点集分组计算法的优化效果分析 39
4.4.3 点集分组计算法对金字塔算法优化的实现 40
§4.5 本章小结 40
第五章 金字塔算法和加速算法的实现 42
§5.1 金字塔算法的编写实现 42
5.1.1 输入数据的产生 42
5.1.2 金字塔算法的实现 42
5.1.3 应用加速算法的金字塔算法实现 42
§5.2优化的金字塔算法运行结果及分析 43
5.2.1 均匀分布点集的运行结果 43
5.2.2 金字塔算法和三种优化算法相结合后运行效率的比较 43
§5.3 本章小结 44
第六章 总结与展望 45
§6.1 全文总结 45
§6.2 本文研究工作的特色及创新 46
§6.3 研究工作展望 46
致 谢 48
参考文献 49

2010.5 中国地质大学硕士学位论文 51
第一章 引 言
凸壳问题是人们在实际应用中经常考虑和解决的问题之一，更为重要地是，它是求解许多实际应用问题和理论学术问题的重要工具。这使得凸壳问题尤其是平面点集凸壳的计算受到人们较高的重视，已对其进行了广泛的研究和应用。许多在图象处理、图形学、模式识别和人工智能以及材料切割和分配等方面的问题[1]都可以演变成凸壳问题之后对其加以解决。凸壳问题也广泛应用于地理信息系统当中，如进行区域剪裁；空间分析模型的有效计算区；建立多边形的最小外接圆[2]；不规则三角网(TIN)的生成[3，4]。在这样的情况下，这使得离散点集凸壳尤其是关于平面离散点集凸壳的研究，从上世纪60年代开始，引起了人们的浓厚兴趣，成为是国内外学者研究的主要热点问题之一。本文在这种大背景下选择该课题进行研究。
传统凸壳算法在离散点集个数较小的情况下，均具有较好的时间效率，但这些算法实现起来通常比较复杂，使其实际应用受到限制。另外当离散点集规模超过一定数量级时，其执行时间一般将无法满足用户的需要，而随着社会的发展，社会交往中的信息量将迅猛增加，对海量数据的处理已成必然，为解决传统凸壳算法这两方面给实际应用带来的不便。本课题将寻求一种实现起来比较简单，易于编写，时间效率可以满足海量数据情况的新凸壳算法－金字塔算法[5]。并在金字塔凸壳算法基础上提出几种快速优化算法。这对推进凸壳算法的研究开辟一条新思路，以适应当前数据日益庞大的需要。
§1.1 研究的目的及意义
随着信息获取技术的发展，带来日前信息资源的急剧膨胀，给社会生产生活的决策带来很大困难。为解决这个困难计算机起了很大作用，但这就需要人们编写高效的应用软件，来适应现在海量数据的要求。作为解决各类实际问题的基础算法，凸壳算法也同样应该适应数据膨胀发展的要求。传统的凸壳算法每个都有各自的优缺点，有不同的适应环境，但总的来说都不适应海量数据发展的需要。另一方面以往的凸壳算法研究主要集中在有序点集的基础上，使得算法设计思想比较复杂，不利于实际工作中的设计实现。设计一种思想简洁、易于实现，便于扩展的算法，是凸壳算法当前亟需应该解决的问题。
快速优化是目前解决实际生活中海量数据凸包问题需要用到的重要核心技术，一直引起国内、国际范围内广泛学者的关注，该技术旨在用最少的时间尽可能多地剔除海量数据中更多无需参加遍历运算的内点，来提高凸壳算法的执行速度。其关键技术涵盖了点线位置关系判定、点集的包含、海量数据分类、数据完整性和整体性管理与检验等。快速优化算法的研究与实践将大大提高凸壳算法对海量数据处理能力，从而为各类实际应用信息服务提供理论基础与技术储备。
本文的目标是设计并实现在平面海量数据模型下新的基本凸壳算法原型系统，充分发挥和利用平面海量数据的自身特点，在其上开发和编写凸壳算法，为各类海量信息服务的决策提供理论基础和设计思路，对平面海量数据凸壳算法的核心问题给出可行的解决方案，并在具体的实验环境中对所提出的基本算法与快速优化算法进行了验证和测试，并对所获取的大量实验结果进行分析评估，进而确定算法的时间复杂度。
论文的研究得到了中国地质大学（武汉）研究生学术创新与探索基金：“大型海量GIS中平面海量散乱点集的新凸壳算法研究”（项目编号：CUGYJS0808）的资助，其研究内容是结合大型地理信息系统计算环境，突破平面海量数据分析与凸壳算法的快速优化等一批关键技术和核心技术，提升各类信息服务系统平台的决策分析处理能力。作为课题核心技术的研发成果，着眼于平面海量数据凸壳算法的研究，其目标是从平面海量数据自身特征及实际运算应用需求出发，提出一套平面海量数据凸壳基本算法和在此基础上的快速优化运算策略及应用机制，以实现在无序平面点集环境下海量数据凸壳的高效求取。
§1.2 凸包的研究现状及进展
平面点集的凸壳问题是计算几何研究的重要子课题之一，与其它计算机问题研究一样，是社会信息服务发展的产物，其执行效率受制于信息数据的规模和计算机的计算能力。随着计算机算法分析理论与数据挖掘理论的日益完善