數(shù)字地面模型中無約束離散點的Delaunay三角網(wǎng)建立案例分析目錄TOC\o"1-3"\h\u8711數(shù)字地面模型中無約束離散點的Delaunay三角網(wǎng)建立案例分析 1307731.1Delaunay三角網(wǎng) 1218801.1.1Voronoi圖 1247591.1.2Delaunay三角網(wǎng)性質(zhì) 3201181.2經(jīng)典Delaunay三角網(wǎng)生成算法 4112841.2.1三角網(wǎng)生長法 4236761.2.2分治算法 5302201.2.3逐點插入法 6227061.3建立TIN模型的方法比較 7不規(guī)則三角網(wǎng)可以很好的描述地形和高程信息，并且可以避免緩沖區(qū)溢出，因此成為一種關(guān)鍵的建模方法。作為一種標準的三角剖分算法，Delaunay三角剖分算法可以盡可能地避開細長的三角形。此外，它可以保證構(gòu)建的三角網(wǎng)的唯一性，促使許多專家學(xué)者將重點放在將Delaunay三角網(wǎng)算法轉(zhuǎn)化為Delaunay三角網(wǎng)算法的科學(xué)研究。1.1Delaunay三角網(wǎng)1.1.1Voronoi圖Voronoi圖，又叫做泰森多邊形，由連續(xù)的多邊形組成，這些多邊形之間相鄰點之間由其垂直平分線連接而成[18]。1908年，俄國學(xué)者G.Voronoi從數(shù)學(xué)上定義了每個觀點所能代表的空間范圍，并用Voronoi圖在二維平面上表示了它的幾何意義：假設(shè)P={p1，p2，...，pnd（p，q）=（則任意點pi的Voronoi圖定義為Vp（如圖3-1所示）：Vp泰勒多邊形為點線面之間進行生成，所以需要嚴格遵循[18]：多邊形內(nèi)通常都有一個生成元；多邊形內(nèi)的點到生成元的距離最短；邊界上的點到各此邊界點之間的距離相同；泰勒多邊形的特性為空間分析和模型提供了一個很好的方法，生成泰勒多邊形主要使用矢量法和柵格法[16]。相鄰Voronoi多邊形是指具有公共邊的Voronoi多邊形，而Delaunay三角網(wǎng)是全部的Voronoi多邊形的生長中心相互連接形成的三角網(wǎng)，它是由互不相同且相互不疊加、相互毗鄰的三角形拼合而成，和Voronoi圖是相互對偶的[16]。在形成的Delaunay三角網(wǎng)中，所有三角形的外接圓都不含有點集中的其他點，圖3-2表示Delaunay三角網(wǎng)和Voronoi圖的相互關(guān)系，關(guān)系圖中實線表示Voronoi圖，虛線表示Delaunay三角網(wǎng)。圖3-2Delaunay三角網(wǎng)和Voronoi圖1.1.2Delaunay三角網(wǎng)性質(zhì)Delaunay三角剖分具有非常關(guān)鍵的特性，即唯一性、空外接圓特性、最大最小內(nèi)角性以及局部性等[16]，如下：（1）唯一性隨機點集的Delaunay三角剖分是唯一存在的，即對于隨機點集，無論以哪一點作為起點和終點，最后的Delaunay三角剖分都是唯一存在的，如圖3-3所示。圖3-3三角剖分圖（2）空外接圓性Delaunay三角網(wǎng)中每個三角形的外接圓不包括點集中的所有其他點，這是Delaunay三角網(wǎng)的創(chuàng)建的基本原理，如圖3-4所示。圖3-4空外接圓（3）最大最小內(nèi)角性對于不規(guī)則三角網(wǎng)，根據(jù)兩個相鄰的三角形形成的凸四邊形，最小內(nèi)部這兩個相鄰三角形的角度必須大于替換直線后的角度。局部最優(yōu)法在背景下于1977年由Lawson提出，Lawson提出的局部最優(yōu)法的根據(jù)是通過替換凸四邊形的對角線，進而得到三角網(wǎng)。如圖所示。圖3-5LOP優(yōu)化（4）局部性在生成三角網(wǎng)的過程中，若對點進行插入或刪除等操作，Delaunay三角剖分也隨之發(fā)生區(qū)域性的變化，即點的插入或刪除等操作只會對部分區(qū)域有損害[16]。1.2經(jīng)典Delaunay三角網(wǎng)生成算法現(xiàn)今，以生成Delaunay三角網(wǎng)的過程不同為依據(jù)，生成三角網(wǎng)的算法主要包括有三角網(wǎng)生長法、分治法及其逐點插入法等。而分治法和逐點插入法以及兩種融合算法為當(dāng)前普遍使用的算法[16]。1.2.1三角網(wǎng)生長法三角網(wǎng)成長法主要是先進行隨機選取一個初始點，之后找到最近點，連接作為初始基準線[16]，從該直線找到最近的點從而獲得一個初始三角形，之后利用三條邊再按照之前的方法找取最近點構(gòu)成三角形，之后再進行不停重復(fù)，直到解析完所有的離散點。三角網(wǎng)生長法比較簡單，網(wǎng)絡(luò)建設(shè)的高效率較弱，現(xiàn)在已經(jīng)很少使用了。如今改進的三角網(wǎng)生長方法都在尋找第三點。圖3-6三角網(wǎng)生長算法步驟1.2.2分治算法分治算法是不斷的對數(shù)據(jù)進行對等分割，最終獲得的子三角網(wǎng)中點數(shù)不大于4之后進行合并獲得三角網(wǎng)的一種算法。該算法采用遞歸來實現(xiàn)，其概念相對簡單，運算速度快，所使用的時間基本上與離散點的數(shù)量成正比。但是在數(shù)據(jù)大時需要計算機有足夠的內(nèi)存。[19]。圖3-7分割合并算法圖解1.2.3逐點插入法Lawson在1977年提出建立一個大的邊界多邊形或者三角形來容納所有數(shù)據(jù)，之后進行逐點插入，利用局部優(yōu)化進行獲得三角網(wǎng)，這種算法叫做逐點插入法。這種算法對空間沒有要求，容易實現(xiàn)，但是時間效率比較低。[20]。其步驟如下：建立一個大的多邊形，可以將所有的點包含在內(nèi)；從離散點中選取一點，進行初始三角網(wǎng)的插入，并與三角形頂點相連，構(gòu)成三個新的小三角形[16]；（3）LOP優(yōu)化；（4）重復(fù)（2）、（3），直至插入完所有離散點。 圖3-8包含P的三角形和該三角形的初始三角剖分1．把包含P的三角形的三個鄰接三角形T1、T2、T31．把包含P的三角形的三個鄰接三角形T1、T2、T3放入堆棧中2．從堆棧中彈出三角形T33．檢查P點是否在T3外接圓中，如果在則交換對角線，反之彈出下一個三角形4．如果交換對角線，則把原來與T3相鄰的三角形T7、T8壓入堆棧5．重復(fù)2~4，直到堆棧為空，則P點的插入過程結(jié)束圖3-9逐點插入法圖解1.3建立TIN模型的方法比較上述三種建立TIN模型的方法及的比較見表3-1。表3-1建立TIN模型的方法及比較建模方法方法描述比較分治算法排序數(shù)據(jù)，分成兩個子集后分別建立三角網(wǎng)并合并。算法比較復(fù)雜并且對計算機的要求也比較高，較難實現(xiàn)。三角網(wǎng)生長算法先進行隨機選取一個初始點，之后找到最近點，連接作為初始基準]，從該直線找到最近的點從而獲得一個初始三角形，之后利用三條邊再按照之前的方法找取最近點構(gòu)成三角形，之后再進行不停重復(fù)，直到解析完所有的離散點。該算法的大部分時間花費在搜索符合要求的