28181.基于非耦合區(qū)域分解的海量delaunay三角網并行構建算法研究

1、NanjingNormalUniversityADissertationSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofMasterofScienceMassiveParallelDelaunayTriangulationConstructionAlgorithmBasedOnTheNoncouplingRegionDecompositionCandidate：Zh

2、angYingSupervisor：ProfLvGuonianPhDZhouLiangchenCollege：SchoolofGeographicalScienceDiscipline：GeographySpeciality：CartologyandGISDataFinished：November17th，2014DateApproved：November23th，2014摘要摘要Delaunay三角網所具備的優(yōu)良特性，使其在地形建模、

3、地圖綜合、模式識別、有限元計算、GIS等諸多領域中有著極為重要的作用。關于Delaunay三角網的構建方法也一直是計算幾何中的重點內容，特別是隨著LIDAR、SAR等新技術的發(fā)展，海量的點集數據可以快捷方便地獲得，如何利用這些海量的點集數據快速高效地生成Delaunay三角網成為當前研究的熱點。本文以拓撲數學、計算幾何為理論基礎，針對Delaunay三角網高效、準確和穩(wěn)定的構網需求，在充分分析國內外學者所采用的各種DTIN構建方法的基礎

4、上，采用對比分析、系統(tǒng)開發(fā)、案例驗證等方法，研究基于非耦合區(qū)域分解的DTIN并行算法和面向海量點集數據的并行D—TIN生成方法，并基于本文提出的Delaunay三角網的生成算法，設計了海量點集數據構建DTIN的原型系統(tǒng)，對典型區(qū)域的海量點集數據生成DTIN進行測試和驗證。所取得的主要研究成果如下：(1)對比分析了分治法、逐點插入法和三角網生長法等常用Delaunay三角網的構建算法后，選取時空復雜度較為平衡且易于實現的逐點插入法作為基礎

5、構網算法，并根據逐點插入法的實現特點，在半邊結構的基礎上，構建一種特殊的雙向循環(huán)鏈表數據結構，實現了構網過程中的快速拓撲重構，從而進一步提高了逐點插入算法的執(zhí)行效率。(2)對比耦合式區(qū)域分解方法和非耦合式區(qū)域分解方法實現DTIN并行構建的優(yōu)缺點，利用Delaunay三角網的空圓特性，提出基于穩(wěn)定三角形條帶進行非耦合區(qū)域分解的并行Delaunay三角網構建算法，既避免了處理器之間的頻繁通信，又不需要復雜的縫合操作，具有較優(yōu)的并行程度和運行

6、效率。(3)研究針對海量數據進行構網的流計算模式，結合基于穩(wěn)定三角形條帶分割的并行Delaunay三角網構建算法，實現面向海量點集進行Delaunay三角網并行構建的算法，解決采用傳統(tǒng)構網算法時效率較低和內存不足的兩個難題。本文的研究內容立足于三維遙測技術的高速發(fā)展和主流的多核架構的計算機體系結構，為海量DTIN快速構建提供新的方案，從而更好地支持地理信息系統(tǒng)、空間數據基礎設施等的發(fā)展和建設。關鍵詞：Delaunay三角網，逐點插入法，