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

1、NanjingNormalUniversityADissertationSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofMasterofScienceMassiveParallelDelaunayTriangulationConstructionAlgorithmBasedOnTheNoncouplingRegionDecompositionCandidate：Zh

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

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

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

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

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