基于約束的Delaunay三角剖分算法設計與實現

論文字數:16013,頁數:56

目錄
摘要 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

摘要
 基于約束的Delaunay三角剖分是建立高精度數字地面模型的基礎，在GIS、地學分析、計算幾何、多分辨率DTM等領域中有著廣泛的應用。本文簡要分析了現存的Delaunay三角剖分算法和約束算法的特點，并且詳細的描述了基于雙向連接邊表數據結構的分治算法和約束條件的插入算法。本文設計實現的基于約束的Delaunay三角剖分算法總體思想是屬于兩步法，就是先實現無約束的Delaunay三角剖分算法（初始三角網），然后再引入約束線段嵌入其中。同時設計實現了基于VC的算法圖形界面演示程序，達到可視化觀察算法的目的。最后通過實驗進行了加入約束條件前后的算法性能測試，結果表明該算法效果達到實際要求。

關鍵詞：Delaunay三角剖分，雙向鏈接邊表，分治法，約束數據域，兩步法

ABSTRACT
    The Delaunay triangulation of constrained data set is widely used in Geographic Information System (GIS), geo-science, computational geometry, multi-resolution and high precision DTM, et al. This paper briefly analyses some existing Delaunay triangulation algorithms and constrained algorithms, and a detailed description of data structure based on DCEL Divide and Conquer algorithm and Constraint insertion algorithm. This paper design and implementation of constrained Delaunay triangulation general idea is two-step system, first implementation of unconstraint Delaunay triangulation (Initial triangulation), and then embed them into Constrained Segments. Designed and implemented an algorithm GUI demo based on VC, to achieve the purpose of visual observation algorithm. Finally, by experiments adding constraints algorithm performance testing before and after, the results show that the algorithm performance to the actual requirements.

 Keywords: Delaunay triangulation, Doubly-Connected Edge List, Divide and conquer, Constrained data set, Two-step system.