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

1、第一節(jié) 概述1.1 TIN的基本概念 基于不規(guī)則三角網(wǎng)的數(shù)字高程模型（Based on Triangulated Irregular Network DEM）就是用一系列互不交叉、互不重疊的連結(jié)在一起的三角形來表示地形表面。什么是TIN？TIN的基本要素用來描述TIN的基本要素有三個：節(jié)點、邊、面。 節(jié)點是相鄰三角形的公共頂點，也是用來構(gòu)建TIN的采樣數(shù)據(jù)。 邊是指兩個三角形的公共邊界，是TIN不光滑性的具體反映。邊同時還包含特征線、斷裂線及區(qū)域邊界。 面是由最近的三個頂點所組成的三角形面，是TIN描述地形表面的基本單元。TIN中的每一個三角形都描述了局部地形傾斜狀態(tài)，具有唯一的坡度值。數(shù)據(jù)和

2、TIN的類型 構(gòu)建TIN的原始數(shù)據(jù)根據(jù)數(shù)據(jù)點之間的約束條件可分為無約束數(shù)據(jù)域和約束數(shù)據(jù)域兩種類型。 無約束數(shù)據(jù)域是指數(shù)據(jù)點之間不存在任何關(guān)系，即數(shù)據(jù)分布完全呈離散狀態(tài)，數(shù)據(jù)點之間在物理上相互獨立。 約束數(shù)據(jù)域則指部分?jǐn)?shù)據(jù)點之間存在某種關(guān)系，這種關(guān)系一般通過線性特征來維護(hù)。 約束條件又可分為兩種：一種是邊界約束，指數(shù)據(jù)點被一多邊形所包圍，該多變形為邊界約束條件；另外一種為內(nèi)部約束條件，即數(shù)據(jù)點之間存在某種限制。TIN的體系結(jié)構(gòu)在TIN中，對三角形的幾何形狀有嚴(yán)格的要求。一般應(yīng)滿足以下三條原則：1、盡量接近正三角形2、保證最近的點形成三角形3、三角形網(wǎng)絡(luò)唯一 分析可知：TIN的數(shù)據(jù)組織、三角形劃分

3、準(zhǔn)則、算法和程序構(gòu)成了TIN的基本理論體系框架。1.2 TIN的三角剖分準(zhǔn)則第一節(jié) 概述 TIN的三角剖分準(zhǔn)則是指TIN中三角形的形成法則，它決定著三角形的幾何形狀和TIN的質(zhì)量。 目前在GIS、計算幾何和計算機(jī)圖形學(xué)領(lǐng)域常見的三角剖分準(zhǔn)則有以下6種：（1）空外接圓準(zhǔn)則：在TIN中，過每個三角形的外接圓均不包含點集的其余任何點。（2）最大最小角準(zhǔn)則：在兩相鄰三角形形成的凸四邊形中，這兩三角形中的最小內(nèi)角一定大于交換凸四邊形對角線后所形成的兩三角形的最小內(nèi)角。（3）最短距離和準(zhǔn)則：指一點到基邊兩端的距離和為最小。1.2 TIN的三角剖分準(zhǔn)則第一節(jié) 概述（4）張角最大準(zhǔn)則：一點到基邊的張角為最大。

4、（5）面積比準(zhǔn)則：三角形內(nèi)切圓面積與三角形面積或三角形面積與周長平方之比最小。（6）對角線準(zhǔn)則：兩三角形組成的凸四邊形的兩條對角線之比超過給定限定值時，對三角形進(jìn)行優(yōu)化。 通常將在空外接圓準(zhǔn)則、最大最小角準(zhǔn)則下進(jìn)行的三角剖分稱為Delaunay三角形，簡稱DT。 事實上，在任何三角剖分準(zhǔn)則下得到的TIN，只要通過LOP法則（局部優(yōu)化過程，Local optimal procedure,LOP）對其進(jìn)行優(yōu)化處理，就能得到唯一的DT三角網(wǎng)絡(luò)。 LOP法則的基本思想是運用DT三角網(wǎng)的空外接圓性質(zhì)對由兩個有公共邊的三角形組成的四邊形進(jìn)行判斷，如果一個三角形的外接圓中含有第四個頂點，則交換四邊形的對角線

5、。第一節(jié) 概述1.3 三角剖分算法分類與特點 TIN的三角剖分就是按照三角剖分準(zhǔn)則，將地形采樣點用互不相交的直線段連接起來，并按一定的結(jié)構(gòu)存儲?，F(xiàn)以地形采樣數(shù)據(jù)的分布情況為依據(jù)對TIN的三角剖分算法進(jìn)行歸類。TIN算法類型不規(guī)則分布數(shù)據(jù)分割合并算法空外接圓算法逐點插入算法三角形增長算法規(guī)則分布數(shù)據(jù)VIPs算法循環(huán)迭帶算法層次三角形算法沿等高線分布數(shù)據(jù)特征線算法探測優(yōu)化算法第二節(jié) TIN的建立5.2.1 無約束散點域的三角剖分算法與實現(xiàn) Tsai于1994年根據(jù)實現(xiàn)過程，把DT三角剖分分成三類：分割合并算法、三角網(wǎng)增長算法和逐點插入算法。分割合并算法 分割合并算法的思想很簡單，就是將復(fù)雜問題簡單

6、化，首先將數(shù)據(jù)點分割成易于進(jìn)行三角剖分的子集，然后對每個子集進(jìn)行三角剖分，并用LOP算法保證三角剖分為DT三角網(wǎng),最后對各子集根據(jù)一定規(guī)則進(jìn)行合并，進(jìn)而形成整體三角網(wǎng)。分割合并算法的基本步驟：第一步：把數(shù)據(jù)集以橫座標(biāo)為主，縱坐標(biāo)為輔按升序進(jìn)行排序。第二步：對數(shù)據(jù)集進(jìn)行分割，如果數(shù)據(jù)子集中的個數(shù)大于給定的閥值，把數(shù)據(jù)域劃分為采樣點個數(shù)近似相等的左右兩個子集，并對每一子集做如下工作：1 計算每一子集的凸殼2 以凸殼為數(shù)據(jù)邊界，對每一數(shù)據(jù)子集進(jìn)行三角剖分，并用LOP法則進(jìn)行優(yōu)化，使之成為DT三角剖分3找出連接左右子集兩個凸殼的底線和頂線4 由底線到頂線合并兩個子三角網(wǎng)。子集凸殼的生成 所謂凸殼是指數(shù)

7、據(jù)點的自然極限邊界，為包含所有數(shù)據(jù)點的最小凸多邊形。下面給大家介紹格雷厄姆凸殼生成算法，步驟如下：（1）找出點集中縱坐標(biāo)最小的點P1（2）將P1點和點集中其他各點用線段相連，并計算這些線段與水平線的夾角（3）按夾角大小對數(shù)據(jù)點進(jìn)行排序，如果夾角相同，則按距離排序。設(shè)得到的序列為P1、P2、Pn（4）依次連接所有點，得到一多邊形，根據(jù)凸多邊形原理，刪去邊界序列中的非凸殼頂點。最后，得到凸殼點集。子三角網(wǎng)合并 合并的方式是同層優(yōu)先，從下至上的遞歸方式進(jìn)行。合并時先找出兩個相鄰子三角網(wǎng)凸殼在上下的公切線，作為三角網(wǎng)的上下邊界。然后從下到上在兩子三角形中尋找與底線組成Delaunay三角形的第三點，選

8、其中外接圓半徑小的一個插入到三角網(wǎng)中，如此類推，完成子網(wǎng)合并。三角網(wǎng)生長算法 故名思議，三角網(wǎng)生長算法就是從一個“源”開始，逐步形成覆蓋整個區(qū)域的三角網(wǎng)。 以生長過程的角度不同為依據(jù)，三角網(wǎng)生長算法分為收縮生長算法和擴(kuò)張生長算法兩種。 收縮生長算法又稱凸閉包收縮法，是先形成整個數(shù)據(jù)域的數(shù)據(jù)邊界（凸殼），并以此作為源頭，逐步縮小以形成整個三角網(wǎng)。收縮生長算法與數(shù)據(jù)點的分布密度有關(guān)。 擴(kuò)張生長算法與收縮生長算法相反，該算法從一個三角形開始向外層層擴(kuò)展，最終形成覆蓋整個區(qū)域的三角網(wǎng)。擴(kuò)張生長算法具體步驟：1 生成初始三角形。2 擴(kuò)張形成三角網(wǎng)。該方法的主要工作是在大量數(shù)據(jù)點中搜尋第三點。其中一種比較

9、簡單的搜索方法是通過計算三角形的外接圓圓心和半徑來完成對鄰域點的搜索。擴(kuò)張生長算法具體步驟：1、在所采集的離散點中任意找一點，然后查找距此點最近的點，連接后作為初始線。、在所采集的離散點中任意找一點，然后查找距此點最近的點，連接后作為初始線。2 2、在初始基線右側(cè)運用在初始基線右側(cè)運用Delaunay法則搜尋第三點，具體的做法是：在初始基線右側(cè)的離法則搜尋第三點，具體的做法是：在初始基線右側(cè)的離散點中查找距此基線距離最短的點，做為第三點。散點中查找距此基線距離最短的點，做為第三點。3 3、生成生成Delaunay三角形，再以三角形的兩條新邊（從基線起始點到第三點以及第三點到三角形，再以三角形的

10、兩條新邊（從基線起始點到第三點以及第三點到基線終止點）作為新的基線?；€終止點）作為新的基線。重復(fù)步驟（2），（3）直至所有的基線處理完畢。收縮生長算法具體步驟： 一旦提取出數(shù)據(jù)區(qū)域的凸閉包，就可以從其中的一條邊開始逐層構(gòu)建三角網(wǎng)，具體算法如下： (1)將凸多邊形按逆時針順序存入鏈表結(jié)構(gòu)，左下角點附近的頂點排第一； (2)選擇第一個點作為起點，與其相鄰點的連線作為第一條基邊，如圖5.1.3(a)中的9-5； (3)從數(shù)據(jù)點中尋找與基邊最鄰近的點8作為三角形的頂點。這樣便形成了第一個DT三角形； (4)將起點9與頂點8的連線換做基邊，重復(fù)(3)即可形成第二個三角形； (5)重復(fù)第(4)步，直到三角形的頂點為另一個邊界點11。這樣，借助于一個起點9便形成了一層Delaunay三角形； (6)適當(dāng)修改邊界點序列，依次選取前一層三角網(wǎng)的頂點作為新起點，重復(fù)前面的處理，便可建立起連續(xù)的一層一層的三角網(wǎng)。逐點插入算法具體步驟：第一步：首先提取整個數(shù)據(jù)區(qū)域的最小外界矩形范圍，并以此作為最簡單的凸閉包。并對包容矩形進(jìn)行初始三角剖分。 第二步：對所有數(shù)據(jù)點進(jìn)行循環(huán)（設(shè)當(dāng)前處理的數(shù)據(jù)點為P）。在已存在的三角網(wǎng)中，查找包含P的三角形t。 p與t的三個頂點相連，形成t的三個初始三角剖分。利用LOP算法對初始三角剖分進(jìn)行優(yōu)化處理。第三步：處理外圍三角形。算法詳解：第一步：大家注意了，