不規(guī)則三角網(TIN)建立

不規(guī)則三角網(TIN)的建立算法數字高程模型2023/2/71馬仕航1410040222TIN概述

5.1.1

TIN的理解5.1.2

TIN的三角剖分準則5.1.3

三角剖分算法分類與特點

2023/2/72TIN的基本概念

不規(guī)則三角網（TriangulatedIrregularNetwork簡稱TIN）：是用一系列互不交叉、互不重疊的連接在一起的三角形來表示地形表面。TIN既是矢量結構又有柵格的空間鋪蓋特征，能很好地描述和維護空間關系。2023/2/73T：三角化（Triangulated）是離散數據的三角剖分過程，也是TIN的建立過程。位于三角形內的任意一點的高程值均可以通過三角形平面方程唯一確定。I：不規(guī)則性（Irregular），指用來構建TIN的采樣點的分布形式。TIN具有可變分辨率，比格網DEM能更好反映地形起伏。N：網（Network），表達整個區(qū)域的三角形分布形態(tài)，即三角形之間不能交叉和重疊。三角形之間的拓撲關系隱含其中。不規(guī)則三角網(TIN)的建立2023/2/74TIN的基本元素節(jié)點（Node）：是相鄰三角形的公共頂點，也是用來構建TIN的采樣數據；邊（Edge）：指兩個三角形的公共邊界，是TIN不光滑性的具體反映。邊同時還包含特征線、斷裂線以及區(qū)域邊界。面（Face）：由最近的三個節(jié)點所組成的三角形面，是TIN描述地形表面的基本單元。TIN中的每一個三角形都描述了局部地形傾斜狀態(tài)，具有唯一的坡度值。三角形在公共節(jié)點和邊上是無縫的，或者說三角形不能交叉和重疊。2023/2/75z節(jié)點x邊面y數據和TIN的類型用來進行TIN構建的原始數據根據數據點之間的約束條件可分為無約束數據域和約束數據域兩種類型。

無約束數據域是指數據點之間不存在任何關系，即數據分布完全呈離散狀態(tài)，數據點之間在物理上相互獨立。約束數據域則是部分數據點之間存在著某種聯系，這種聯系一般通過線性特征來維護，如地形數據中的山脊線、山谷線上的點等。

2023/2/76TIN的體系結構

TIN對三角形的幾何形狀一般有三個基本要求：1）三角形的格網唯一；2）最佳三角形形狀，盡量接近正三角形；3）三角形邊長之和最小，保證最近的點形成三角形。2023/2/77TIN的三角剖分準則

TIN的三角剖分準則是指TIN中三角形的形成法則，它決定著三角形的幾何形狀和TIN的質量。目前，在GIS、計算機和圖形學領域常用的三角剖分準則有6種。2023/2/78空外接圓準則：在TIN中，過每個三角形的外接圓均不包含點集的其余任何點；最大最小角準則：在TIN中的兩相鄰三角形形成的凸四邊形中，這兩三角形中的最小內角一定大于交換凸四邊形對角線后所形成的兩三角形的最小內角；最短距離和準則：指一點到基邊的兩端的距離和為最小。2023/2/79張角最大準則：一點到基邊的張角為最大。面積比準則：三角形內切圓面積與三角形面積或三角形面積與周長平方之比最小。對角線準則：兩三角形組成的凸四邊形的兩條對角線之比。這一準則的比值限定值，須給定，即當計算值超過限定值才進行優(yōu)化。2023/2/7101）三角形準則是建立三角形格網的基本原則，應用不同的準則將會得到不同的三角網。2）一般而言，應盡量保持三角網的唯一性，即在同一準則下由不同的位置開始建立三角形格網，其最終的形狀和結構應是相同的。3）空外接圓準則、最大最小角準則下進行的三角剖分稱為Delaunay(譯為狄洛尼或德勞內)三角剖分（Triangulation），簡稱DT?？胀饨訄A準則也叫Delaunay法則。說明：2023/2/711關于delaunay三角網1934年Delaunay提出了Voronoi圖的對稱圖，即Delaunay三角網（用直線段連接兩個相鄰多邊形內的離散點而生成的三角網）。Delaunay三角網的特性：不存在四點共圓；每個三角形對應于一個Voronoi圖頂點；每個三角形邊對應于一個Voronoi圖邊；每個結點對應于一個Voronoi圖區(qū)域；Delaunay圖的邊界是一個凸殼；三角網中三角形的最小角最大。2023/2/712TIN的建立

1

無約束散點域的三角剖分算法與實現2約束散點數據域的三角剖分算法與實現3基于等高線數據的TIN的建立4基于柵格數據的三角網建立2023/2/713無約束散點域的三角剖分算法與實現

目前散點域的三角剖分使用最為廣泛的算法是Delaunay直接三角剖分算法。1）三角網生長算法2）逐點插入算法

3）分割合并算法2023/2/7141、三角網生長算法

三角網生長算法就是從一個“源”開始，逐步形成覆蓋整個數據區(qū)域的三角網。從生長過程角度，三角網生長算法分為收縮生長算法和擴張生長算法兩類。收縮生長算法是先形成整個數據域的數據邊界（凸殼），并以此作為源頭，逐步縮小以形成整個三角網。擴張生長算法與收縮算法過程剛好相反，是從一個三角形開始向外層層擴展，形成覆蓋整個區(qū)域的三角網。2023/2/7151、三角網生長算法1）遞歸生長算法算法過程如下：在數據集中任取一點，查找距離此點最近的點，相連后作為初始基線；在初始基線右邊應用Delaunay法則搜索第三點；生成Delaunay三角形，并以該三角形的兩條新邊作為新的基線；重復前面過程直至所有基線處理完畢；這種算法大量的時間花費在符合要求的鄰域點的搜索方面，為了減少搜索時間，許多學者提出了許多不同的方法，如將數據分塊并排列，以外接圓的方式限定其搜索范圍。2023/2/71612121212遞歸生長算法3332023/2/7171、三角網生長算法該算法的基本思路:首先找到包含數據區(qū)域的最小凸多邊形，并從該多邊形開始從外向里逐層形成三角形格網。平面點凸閉包的定義是包含這些平面點的最小多邊形。在凸閉包中，連接任意兩點的線段必須完全位于多邊形內。凸閉包是數據點的自然極限邊界，相當于包圍數據點的最短路徑。凸閉包是數據集標準Delaunay三角網的一部分。計算凸閉包是該算法的核心。2）凸閉包收縮法2023/2/7181）計算凸閉包的四個頂點；2）以此四點作為基點，通過邊右邊最大偏移量搜索其他凸閉包頂點。計算凸閉包的思路（P79）：2023/2/7191）將凸多邊形按逆時針保存記錄，以左下角點附近的頂點作為起點；2）確定第一條基邊；3）構建第一個Delaunay三角形；4）重復(3)形成第一層Delaunay三角形；5）重新確定起點，重復(2)~(4)完成整個區(qū)域的三角網構建。構建三角網的具體算法2023/2/7202、逐點插入算法

：1）定義包含所有數據點的最小外界矩形范圍，并以此作為最簡單的凸閉包。2）按一定規(guī)則將數據區(qū)域的矩形范圍進行格網劃分（如限定每個格網單元的數據點數）。3）剖分數據區(qū)域的凸閉包形成兩個超三角形，所有數據點都一定在這兩個三角形范圍內。4）對所有數據點進行循環(huán)，作如下工作（設當前處理的數據點為P）：搜尋包含點P的三角形，將P與此三角形三個頂點相連，形成三個三角形；由里到外優(yōu)化整個三角網；重復以上過程直到所有點處理完畢；刪除所有包含一個或多個超三角形頂點的三角形。5）處理外圍三角形。2023/2/721逐點插入算法2023/2/7223、分割合并算法

分割合并算法的思想很簡單，首先將數據點分割成易于進行三角化的子集，然后對每個子集進行三角剖分，并用LOP算法保證三角剖分為Delaunay三角網。當每個子集剖分完成后，對每個子集的三角剖分進行合并，形成最終的整體三角網。

2023/2/723分割合并算法2023/2/7243基于等高線數據的TIN的建立

等高線離散點直接生成TIN；將等高線作為特征線的方法；自動增加特征點及優(yōu)化TIN的方法。2023/2/725等高線離散點直接生成TIN方法

該方法直接將等高線離散化，然后利用常用TIN的生成算法，該方法沒有考慮離散點間原有的連接關系，模擬的地形就會失真，具體表現為三角形的邊穿越等高線和存在平三角形的兩種情況。

在實際應用中該方法較少使用。2023/2/726等高線作為特征線建立TIN

將等