地理信息系統(tǒng)TIN

第1頁單擊此處編輯母版標題樣式第1頁單擊此處編輯母版文本樣式第二級第三級第四級不規(guī)則三角網(wǎng)的建立地科院空間系主要內(nèi)容TIN概述

TIN的建立TIN建立過程中的幾個問題TIN概述

TIN的理解TIN的三角剖分準則三角剖分算法分類與特點TIN的理解

TIN的基本概念

不規(guī)則三角網(wǎng)（TriangulatedIrregularNetwork簡稱TIN）：是用一系列互不交叉、互不重疊的連接在一起的三角形來表示地形表面。TIN既是矢量結(jié)構(gòu)又有柵格的空間鋪蓋特征，能很好地描述和維護空間關系。T：三角化（Triangulated）是離散數(shù)據(jù)的三角剖分過程，也是TIN的建立過程。位于三角形內(nèi)的任意一點的高程值均可以通過三角形平面方程唯一確定。I：不規(guī)則性（Irregular），指用來構(gòu)建TIN的采樣點的分布形式。TIN具有可變分辨率，比格網(wǎng)DEM能更好反映地形起伏。N：網(wǎng)（Network），表達整個區(qū)域的三角形分布形態(tài)，即三角形之間不能交叉和重疊。三角形之間的拓撲關系隱含其中。TIN的理解

TIN的理解

TIN的基本元素節(jié)點（Node）：是相鄰三角形的公共頂點，也是用來構(gòu)建TIN的采樣數(shù)據(jù)；邊（Edge）：指兩個三角形的公共邊界，是TIN不光滑性的具體反映。邊同時還包含特征線、斷裂線以及區(qū)域邊界。面（Face）：由最近的三個節(jié)點所組成的三角形面，是TIN描述地形表面的基本單元。TIN中的每一個三角形都描述了局部地形傾斜狀態(tài)，具有唯一的坡度值。三角形在公共節(jié)點和邊上是無縫的，或者說三角形不能交叉和重疊。TIN的理解

數(shù)據(jù)和TIN的類型用來進行TIN構(gòu)建的原始數(shù)據(jù)根據(jù)數(shù)據(jù)點之間的約束條件可分為無約束數(shù)據(jù)域和約束數(shù)據(jù)域兩種類型。

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

TIN的理解

TIN的體系結(jié)構(gòu)

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

TIN的三角剖分準則是指TIN中三角形的形成法則，它決定著三角形的幾何形狀和TIN的質(zhì)量。目前，在GIS、計算機和圖形學領域常用的三角剖分準則有6種。TIN的三角剖分準則

空外接圓準則：在TIN中，過每個三角形的外接圓均不包含點集的其余任何點；最大最小角準則：在TIN中的兩相鄰三角形形成的凸四邊形中，這兩三角形中的最小內(nèi)角一定大于交換凸四邊形對角線后所形成的兩三角形的最小內(nèi)角；最短距離和準則：指一點到基邊的兩端的距離和為最小。張角最大準則：一點到基邊的張角為最大。面積比準則：三角形內(nèi)切圓面積與三角形面積或三角形面積與周長平方之比最小。對角線準則：兩三角形組成的凸四邊形的兩條對角線之比。這一準則的比值限定值，須給定，即當計算值超過限定值才進行優(yōu)化。TIN的三角剖分準則

1）三角形準則是建立三角形格網(wǎng)的基本原則，應用不同的準則將會得到不同的三角網(wǎng)。2）一般而言，應盡量保持三角網(wǎng)的唯一性，即在同一準則下由不同的位置開始建立三角形格網(wǎng)，其最終的形狀和結(jié)構(gòu)應是相同的。3）空外接圓準則、最大最小角準則下進行的三角剖分稱為Delaunay

(譯為狄洛尼或德勞內(nèi))三角剖分（Triangulation），簡稱DT?？胀饨訄A準則也叫Delaunay法則。說明：1934年Delaunay提出了Voronoi圖的對稱圖，即Delaunay三角網(wǎng)（用直線段連接兩個相鄰多邊形內(nèi)的離散點而生成的三角網(wǎng)）。Delaunay三角網(wǎng)的特性：不存在四點共圓；每個三角形對應于一個Voronoi圖頂點；每個三角形邊對應于一個Voronoi圖邊；每個結(jié)點對應于一個Voronoi圖區(qū)域；Delaunay圖的邊界是一個凸殼；三角網(wǎng)中三角形的最小角最大。關于delaunay三角網(wǎng)三角剖分算法分類與特點

不規(guī)則分布采樣數(shù)據(jù)三角剖分

規(guī)則分布采樣數(shù)據(jù)三角剖分從混合數(shù)據(jù)生成三角網(wǎng)基于等高線采樣數(shù)據(jù)三角剖分三角剖分算法分類與特點

不規(guī)則分布采樣數(shù)據(jù)三角剖分在目前所有的三角化算法中，以Delaunay三角網(wǎng)的應用最為廣泛。Delaunay三角網(wǎng)為相互鄰接且互不重疊的三角形的集合，每一個三角形的外接圓內(nèi)不包含其它的點。DT的主要特點是它能自動地避免狹長的三角形，保證了良好的三角形形狀。DT的兩個顯著特性最大最小角特性和空外接圓特性是構(gòu)成各種DT剖分的基礎。

新插入點與已知三角網(wǎng)存在四種關系：（a）在三角形內(nèi)（b）在三角形外接圓內(nèi)（c）在三角形外接圓上（d）在三角形外接圓外局部幾何形狀最優(yōu)，采用LOP算法（局部優(yōu)化過程，LocalOptimalProcedure）。其基本思想：運用DT三角網(wǎng)的空外接圓性質(zhì)對兩個公共邊的三角形組成的四邊形進行判斷，如果其中一個三角形的外接圓中含有第四點，則交換四邊形的對角線。三角剖分算法分類與特點

規(guī)則分布采樣數(shù)據(jù)三角剖分規(guī)則數(shù)據(jù)生成TIN，一般有兩種方式：1）直接將格網(wǎng)分解組合即可得到三角網(wǎng)；2）通過一定法則，選擇“重要”點(veryimportantpoints，VIPs)建立三角形。根據(jù)規(guī)則數(shù)據(jù)建成的三角形格網(wǎng)三角剖分算法分類與特點

規(guī)則分布采樣數(shù)據(jù)三角剖分

重要點法DEM建模有兩個關鍵步驟：

1）確定格網(wǎng)點的“重要程度”：全局最重要或局部最重要；

2）確定終止條件：達到預設的點數(shù)或預設的精度、或兩者折中。目前這類算法主要有地形骨架法、地形濾波法等。地形骨架法：利用地形特征點、線建立地形的骨架模型，然后對其進行插點，達到預定的精度；地表濾波法：將格網(wǎng)DEM看作為一幅數(shù)字圖像，可使用空間高通濾波器對其濾波，保留圖像中的高頻信息，即為地形特征點，濾掉低頻信息也即對地形特征而言不重要的點，在此基礎上建立TIN模型。三角剖分算法分類與特點

從混合數(shù)據(jù)生成三角網(wǎng)

混合數(shù)據(jù)：是指鏈狀數(shù)據(jù)（如斷裂線、河流線等）與規(guī)則格網(wǎng)采樣數(shù)據(jù)結(jié)合形成的一種數(shù)據(jù)。此種數(shù)據(jù)建立三角網(wǎng)的方法：首先分解規(guī)則三角形，然后考慮特征線上的點，在格網(wǎng)中生成不規(guī)則三角形。三角剖分算法分類與特點

基于等高線采樣數(shù)據(jù)三角剖分

由于數(shù)據(jù)沿等高線分布，常會出現(xiàn)一些不希望的現(xiàn)象，如三角形三頂點在同一條等高線上（稱為平三角形）。對這類問題有兩種處理方案：一是把等高線數(shù)據(jù)當作特征線處理，按約束DT進行剖分，一是局部優(yōu)化內(nèi)插增加地形特征點。TIN的建立

1

無約束散點域的三角剖分算法與實現(xiàn)2約束散點數(shù)據(jù)域的三角剖分算法與實現(xiàn)3基于等高線數(shù)據(jù)的TIN的建立4基于柵格數(shù)據(jù)的三角網(wǎng)建立1、三角網(wǎng)生長算法

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

：TIN的建立1）定義包含所有數(shù)據(jù)點的最小外界矩形范圍，并以此作為最簡單的凸閉包。2）按一定規(guī)則將數(shù)據(jù)區(qū)