快速三维凸包算法的研究与改进

摘要

本论文主要提出了一种改进的快速三维凸包构造新算法。在过去几十年凸包算法的研究取得了一系列的进步,如二维的Graham扫描算法,Javis卷包裹(wrapping)算法等等,基于排序的算法平均时间复杂度都是O(nlogn)。而在三维凸包算法领域里,则有经典的Clarkson和Shor算法,以及Quick Hull算法。本质上讲,这两个算法都基于随机增量算法,通过动态地添加外部点来逐步构造出完整的凸包,优点是易于理解操作,并且时间复杂度仍然是凸包构造的下限O(nlogn)。而根据大量的统计数据表明,对于任意一个充分大的点集而言,绝大部分点不是最终凸包的顶点。所以,本文在详细研究了这两个算法的随机性基础上,进一步引入了非随机的性质,加速了Quick Hull算法。
　　 全文主要内容为:
　　 1)提出了一种新的三维凸包的构造算法,这种改进的快速算法参考了QuickHull算法里面每轮迭代选取外部集合中的极值点来作为候选点,更新成新的凸包的思想,并在这个基础上改进为选用二次极值点来构造新凸包的方法,同时综合使用了一个二部图数据结构“冲突图”来记录外部点与当前的凸包的可见性关系,最终达到了排除内部点,迅速缩小构建的规模,实现了高效地构建凸包,本文的实验也说明了两者相比,新算法比QuickHull算法效率更高。
　　 2)采用Visual C++和OpcnGL语言为工具,设计了一个完整的实验平台,包括STLViewer.exe主程序和五个动态链接库。从数据生成,采集,加工,算法实现,到最后的结果显示,整个平台都是完全按照标准的CAD软件设计模式开发,使得这个平台具有了一定的实用性和可操作性。
　　 3)完成了实验数据的加工,比较,改进算法相对于QuickHull算法在效率上平均提升了20％。

目录

文摘

英文文摘

第一章 绪论

1 -1凸包问题的应用及研究现状

1 -1-1凸包的应用

1 -1-2凸包的综合研究现状

第二章 凸包的相关概念

2 -1凸包的概念

2 -1-1关于凸包的几个定义

2 -1-2三维凸包复杂度分析

2 -2凸包和半空间的交

2 -2-1凸包与对偶

2 -2-2凸包的转化

2 -2-3凸包与Voronoi图

2 -3构建三维凸包的关键命题

第三章 经典的三维凸包生成算法分析

3 -1 Clarkson和shor算法

3 -1-1随机算法框架

3 -1-2 Clarkson和Shor算法描述

3 -1-3 Clarkson和Shor算法复杂度

3 -2快速凸包算法

3 -2-1快速凸包算法介绍

3 -2-2快速凸包算法框架

3 -2-3算法描述

3 -2-4快速凸包算法的正确性以及复杂度分析

第四章 改进的三维凸包算法

4 -1改进的三维凸包算法框架

4 -1-1详细步骤

4 -1-2可见性

4 -1-3地平线

4 -2算法的数据结构

4 -2-1凸包空间结构

4 -2-2凸包中点和面的拓扑关系结构

4 -3算法的描述

4 -3-1算法的伪代码实现和流程图

4 -3-2算法的操作详解

4 -4算法的正确性分析

4 -5算法的复杂度分析

第五章 基于OPENGL的实验平台设计及实验分析

5 -1实验平台设计

5 -1-1动态链接库和openGL

5 -1-2总体模块设计

5 -1-3几何基本工具库Geomcalc.dll

5 -1-4几何内核库GeomKernal.dll

5 -1-5凸包生成工具库ConvexHull.dll

5 -2实验的效果

5 -3效率分析

第六章 总结与展望

6 -1总结

6 -2进一步工作

致谢

参考文献

攻读学位期间发表的学术论文