第一節概述1.1TIN的基本概念

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