基于约束的Delaunay三角剖分算法设计与实现

摘要

基于约束的Delaunay三角剖分是建立高精度数字地面模型的基础，在GIS、地学分析、计算几何、多分辨率DTM等领域中有着广泛的应用。本文简要分析了现存的Delaunay三角剖分算法和约束算法的特点，并且详细的描述了基于双向连接边表数据结构的分治算法和约束条件的插入算法。本文设计实现的基于约束的Delaunay三角剖分算法总体思想是属于两步法，就是先实现无约束的Delaunay三角剖分算法（初始三角网），然后再引入约束线段嵌入其中。同时设计实现了基于VC的算法图形界面演示程序，达到可视化观察算法的目的。最后通过实验进行了加入约束条件前后的算法性能测试，结果表明该算法效果达到实际要求。

关键词：Delaunay三角剖分，双向链接边表，分治法，约束数据域，两步法

 目录

摘要 I

ABSTRACT II

第1章 引言 1

1.1 背景 1

1.2 研究内容 1

第2章 基本概念和性质 3

2.1 三角剖分概念 3

2.2 DT基本概念 5

2.3 CDT基本概念 7

第3章 相关算法简要分析 9

3.1 Delaunay三角剖分算法 9

3.1.1 逐点插入算法 9

3.1.2 分治算法 10

3.1.3 三角网生长算法 11

3.2 约束Delaunay三角剖分算法 12

3.2.1 约束图法 12

3.2.2 分割-合并算法 12

3.2.3 加密算法 12

3.2.4 Shell三角化算法 13

3.2.5 两步法 13

第4章 DCEL数据结构 14

4.1 DCEL数据结构描述 14

4.2 关于DCEL几个重要函数操作说明 19

4.2.1 void splice（Edge* a， Edge* b） 19

4.2.2 Edge* connect（Edge* a， Edge* b） 20

4.2.3 void swap（Edge* e） 21

4.2.4 bool inCircle（ a，b，c，d） 22

4.2.5 Edge* locate（const Point2d& p， Edge* startEdge） 23

第5章 基于DCEL的分治法 24

5.1 主要步骤 24

5.2 算法详细说明 24

5.2.1 递归划分结束条件 24

5.2.2 递归返回的数据结构 25

5.2.3 下公共切线寻找算法 26

5.2.4 Merge具体步骤 26

5.3分治法的时间复杂度分析 29

第6章 约束线段嵌入的迭代算法 30

6.1 约束算法主要步骤 30

6.2 算法详细实现过程 30

6.2.1 约束线段插入函数 31

6.2.2 影响域多边形计算函数 32

6.2.3 多边形三角剖分函数 34

6.3 算法时间复杂度分析 38

第7章 算法图形界面演示程序设计 39

7.1 OpenGL介绍 39

7.2 图形界面程序的设计细节 41

7.2.1 程序的功能描述 41

7.2.2 视图放大功能 44

7.2.3 剖分结果的圆测试 45

第8章 算法性能测试 47

8.1 基于DCEL的分治法性能测试 47

8.2 约束性算法性能测试 48

第9章 结束语 49

致谢 50

参考文献 51