第五章 不規(guī)則三角網(wǎng)TIN建立1

第一節(jié)概述1.1TIN的基本概念

基于不規(guī)則三角網(wǎng)的數(shù)字高程模型（BasedonTriangulatedIrregularNetworkDEM）就是用一系列互不交叉、互不重疊的連結(jié)在一起的三角形來表示地形表面。什么是TIN？？TIN的基本要素用來描述TIN的基本要素有三個(gè)：節(jié)點(diǎn)、邊、面。節(jié)點(diǎn)是相鄰三角形的公共頂點(diǎn)，也是用來構(gòu)建TIN的采樣數(shù)據(jù)。邊是指兩個(gè)三角形的公共邊界，是TIN不光滑性的具體反映。邊同時(shí)還包含特征線、斷裂線及區(qū)域邊界。面是由最近的三個(gè)頂點(diǎn)所組成的三角形面，是TIN描述地形表面的基本單元。TIN中的每一個(gè)三角形都描述了局部地形傾斜狀態(tài)，具有唯一的坡度值。數(shù)據(jù)和TIN的類型構(gòu)建TIN的原始數(shù)據(jù)根據(jù)數(shù)據(jù)點(diǎn)之間的約束條件可分為無約束數(shù)據(jù)域和約束數(shù)據(jù)域兩種類型。無約束數(shù)據(jù)域是指數(shù)據(jù)點(diǎn)之間不存在任何關(guān)系，即數(shù)據(jù)分布完全呈離散狀態(tài)，數(shù)據(jù)點(diǎn)之間在物理上相互獨(dú)立。約束數(shù)據(jù)域則指部分?jǐn)?shù)據(jù)點(diǎn)之間存在某種關(guān)系，這種關(guān)系一般通過線性特征來維護(hù)。約束條件又可分為兩種：一種是邊界約束，指數(shù)據(jù)點(diǎn)被一多邊形所包圍，該多變形為邊界約束條件；另外一種為內(nèi)部約束條件，即數(shù)據(jù)點(diǎn)之間存在某種限制。TIN的體系結(jié)構(gòu)在TIN中，對(duì)三角形的幾何形狀有嚴(yán)格的要求。一般應(yīng)滿足以下三條原則：1、盡量接近正三角形2、保證最近的點(diǎn)形成三角形3、三角形網(wǎng)絡(luò)唯一分析可知：TIN的數(shù)據(jù)組織、三角形劃分準(zhǔn)則、算法和程序構(gòu)成了TIN的基本理論體系框架。1.2TIN的三角剖分準(zhǔn)則第一節(jié)概述TIN的三角剖分準(zhǔn)則是指TIN中三角形的形成法則，它決定著三角形的幾何形狀和TIN的質(zhì)量。目前在GIS、計(jì)算幾何和計(jì)算機(jī)圖形學(xué)領(lǐng)域常見的三角剖分準(zhǔn)則有以下6種：（1）空外接圓準(zhǔn)則：在TIN中，過每個(gè)三角形的外接圓均不包含點(diǎn)集的其余任何點(diǎn)。（2）最大最小角準(zhǔn)則：在兩相鄰三角形形成的凸四邊形中，這兩三角形中的最小內(nèi)角一定大于交換凸四邊形對(duì)角線后所形成的兩三角形的最小內(nèi)角。（3）最短距離和準(zhǔn)則：指一點(diǎn)到基邊兩端的距離和為最小。1.2TIN的三角剖分準(zhǔn)則第一節(jié)概述（4）張角最大準(zhǔn)則：一點(diǎn)到基邊的張角為最大。（5）面積比準(zhǔn)則：三角形內(nèi)切圓面積與三角形面積或三角形面積與周長(zhǎng)平方之比最小。（6）對(duì)角線準(zhǔn)則：兩三角形組成的凸四邊形的兩條對(duì)角線之比超過給定限定值時(shí)，對(duì)三角形進(jìn)行優(yōu)化。通常將在空外接圓準(zhǔn)則、最大最小角準(zhǔn)則下進(jìn)行的三角剖分稱為Delaunay三角形，簡(jiǎn)稱DT。事實(shí)上，在任何三角剖分準(zhǔn)則下得到的TIN，只要通過LOP法則（局部?jī)?yōu)化過程，Localoptimalprocedure,LOP）對(duì)其進(jìn)行優(yōu)化處理，就能得到唯一的DT三角網(wǎng)絡(luò)。LOP法則的基本思想是運(yùn)用DT三角網(wǎng)的空外接圓性質(zhì)對(duì)由兩個(gè)有公共邊的三角形組成的四邊形進(jìn)行判斷，如果一個(gè)三角形的外接圓中含有第四個(gè)頂點(diǎn)，則交換四邊形的對(duì)角線。第一節(jié)概述1.3三角剖分算法分類與特點(diǎn)TIN的三角剖分就是按照三角剖分準(zhǔn)則，將地形采樣點(diǎn)用互不相交的直線段連接起來，并按一定的結(jié)構(gòu)存儲(chǔ)。現(xiàn)以地形采樣數(shù)據(jù)的分布情況為依據(jù)對(duì)TIN的三角剖分算法進(jìn)行歸類。TIN算法類型不規(guī)則分布數(shù)據(jù)分割合并算法空外接圓算法逐點(diǎn)插入算法三角形增長(zhǎng)算法規(guī)則分布數(shù)據(jù)VIPs算法循環(huán)迭帶算法層次三角形算法沿等高線分布數(shù)據(jù)特征線算法探測(cè)優(yōu)化算法第二節(jié)TIN的建立5.2.1無約束散點(diǎn)域的三角剖分算法與實(shí)現(xiàn)Tsai于1994年根據(jù)實(shí)現(xiàn)過程，把DT三角剖分分成三類：分割合并算法、三角網(wǎng)增長(zhǎng)算法和逐點(diǎn)插入算法。分割合并算法分割合并算法的思想很簡(jiǎn)單，就是將復(fù)雜問題簡(jiǎn)單化，首先將數(shù)據(jù)點(diǎn)分割成易于進(jìn)行三角剖分的子集，然后對(duì)每個(gè)子集進(jìn)行三角剖分，并用LOP算法保證三角剖分為DT三角網(wǎng),最后對(duì)各子集根據(jù)一定規(guī)則進(jìn)行合并，進(jìn)而形成整體三角網(wǎng)。分割合并算法的基本步驟：第一步：把數(shù)據(jù)集以橫座標(biāo)為主，縱坐標(biāo)為輔按升序進(jìn)行排序。第二步：對(duì)數(shù)據(jù)集進(jìn)行分割，如果數(shù)據(jù)子集中的個(gè)數(shù)大于給定的閥值，把數(shù)據(jù)域劃分為采樣點(diǎn)個(gè)數(shù)近似相等的左右兩個(gè)子集，并對(duì)每一子集做如下工作：1計(jì)算每一子集的凸殼2以凸殼為數(shù)據(jù)邊界，對(duì)每一數(shù)據(jù)子集進(jìn)行三角剖分，并用LOP法則進(jìn)行優(yōu)化，使之成為DT三角剖分3找出連接左右子集兩個(gè)凸殼的底線和頂線4由底線到頂線合并兩個(gè)子三角網(wǎng)。子集凸殼的生成所謂凸殼是指數(shù)據(jù)點(diǎn)的自然極限邊界，為包含所有數(shù)據(jù)點(diǎn)的最小凸多邊形。下面給大家介紹格雷厄姆凸殼生成算法，步驟如下：（1）找出點(diǎn)集中縱坐標(biāo)最小的點(diǎn)P1（2）將P1點(diǎn)和點(diǎn)集中其他各點(diǎn)用線段相連，并計(jì)算這些線段與水平線的夾角（3）按夾角大小對(duì)數(shù)據(jù)點(diǎn)進(jìn)行排序，如果夾角相同，則按距離排序。設(shè)得到的序列為P1、P2、…Pn（4）依次連接所有點(diǎn)，得到一多邊形，根據(jù)凸多邊形原理，刪去邊界序列中的非凸殼頂點(diǎn)。最后，得到凸殼點(diǎn)集。子三角網(wǎng)合并合并的方式是同層優(yōu)先，從下至上的遞歸方式進(jìn)行。合并時(shí)先找出兩個(gè)相鄰子三角網(wǎng)凸殼在上下的公切線，作為三角網(wǎng)的上下邊界。然后從下到上在兩子三角形中尋找與底線組成Delaunay三角形的第三點(diǎn)，選其中外接圓半徑小的一個(gè)插入到三角網(wǎng)中，如此類推，完成子網(wǎng)合并。三角網(wǎng)生長(zhǎng)算法故名思議，三角網(wǎng)生長(zhǎng)算法就是從一個(gè)“源”開始，逐步形成覆蓋整個(gè)區(qū)域的三角網(wǎng)。以生長(zhǎng)過程的角度不同為依據(jù)，三角網(wǎng)生長(zhǎng)算法分為收縮生長(zhǎng)算法和擴(kuò)張生長(zhǎng)算法兩種。收縮生長(zhǎng)算法又稱凸閉包收縮法，是先形成整個(gè)數(shù)據(jù)域的數(shù)據(jù)邊界（凸殼），并以此作為源頭，逐步縮小以形成整個(gè)三角網(wǎng)。收縮生長(zhǎng)算法與數(shù)據(jù)點(diǎn)的分布密度有關(guān)。擴(kuò)張生長(zhǎng)算法與收縮生長(zhǎng)算法相反，該算法從一個(gè)三角形開始向外層層擴(kuò)展，最終形成覆蓋整個(gè)區(qū)域的三角網(wǎng)。擴(kuò)張生長(zhǎng)算法具體步驟：1生成初始三角形。2擴(kuò)張形成三角網(wǎng)。該方法的主要工作是在大量數(shù)據(jù)點(diǎn)中搜尋第三點(diǎn)。其中一種比較簡(jiǎn)單的搜索方法是通過計(jì)算三角形的外接圓圓心和半徑來完成對(duì)鄰域點(diǎn)的搜索。擴(kuò)張生長(zhǎng)算法具體步驟：1、在所采集的離散點(diǎn)中任意找一點(diǎn)，然后查找距此點(diǎn)最近的點(diǎn)，連接后作為初始線。2、在初始基線右側(cè)運(yùn)用Delaunay法則搜尋第三點(diǎn)，具體的做法是：在初始基線右側(cè)的離散點(diǎn)中查找距此基線距離最短的點(diǎn)，做為第三點(diǎn)。3、生成Delaunay三角形，再以三角形的兩條新邊（從基線起始點(diǎn)到第三點(diǎn)以及第三點(diǎn)到基線終止點(diǎn)）作為新的基線。重復(fù)步驟（2），（3）直至所有的基線處理完畢。收縮生長(zhǎng)算法具體步驟：一旦提取出數(shù)據(jù)區(qū)域的凸閉包，就可以從其中的一條邊開始逐層構(gòu)建三角網(wǎng)，具體算法如下：(1)將凸多邊形按逆時(shí)針順序存入鏈表結(jié)構(gòu)，左下角點(diǎn)附近的頂點(diǎn)排第一；(2)選擇第一個(gè)點(diǎn)作為起點(diǎn)，與其相鄰點(diǎn)的連線作為第一條基邊，如圖5.1.3(a)中的9-5；(3)從數(shù)據(jù)點(diǎn)中尋找與基邊最鄰近的點(diǎn)8作為三角形的頂點(diǎn)。這樣便形成了第一個(gè)DT三角形；(4)將起點(diǎn)9與頂點(diǎn)8的連線換做基邊，重復(fù)(3)即可形成第二個(gè)三角形；(5)重復(fù)第(4)步，直到三角形的頂點(diǎn)為另一個(gè)邊界點(diǎn)11。這樣，借助于一個(gè)起點(diǎn)9便形成了一層Delaunay三角形；(6)適當(dāng)修改邊界點(diǎn)序列，依次選取前一層三角網(wǎng)的頂點(diǎn)作為新起點(diǎn)，重復(fù)前面的處理，便可建立起連續(xù)的一層一層的三角網(wǎng)。逐點(diǎn)插入算法具體步驟：第一步：首先提取整個(gè)數(shù)據(jù)區(qū)域的最小外界矩形范圍，并以此作為最簡(jiǎn)單的凸閉包。并對(duì)包容矩形進(jìn)行初始三角剖分。第二步：對(duì)所有數(shù)據(jù)點(diǎn)進(jìn)行循環(huán)（設(shè)當(dāng)前處理的數(shù)據(jù)點(diǎn)為P）。①在已存在的三角網(wǎng)中，查找包含P的三角形t。②p與t的三個(gè)頂點(diǎn)相連，形成t的三個(gè)初始三角剖分。③利用LOP算法對(duì)初始三角剖分進(jìn)行優(yōu)化處理。第三步：處理外圍三角形。算法詳解：第一步：大家注意