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

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

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

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