不規(guī)則三角網(wǎng)TIN的建立

2023/9/21第五章

不規(guī)則三角網(wǎng)(TIN)的建立數(shù)字高程模型2023/9/22本章主要內(nèi)容數(shù)字高程模型第5章不規(guī)則三角網(wǎng)(TIN)的建立5.1TIN概述

5.2TIN的建立5.3TIN建立過程中的幾個問題2023/9/235.1TIN概述

5.1.1TIN的理解5.1.2

TIN的三角剖分準(zhǔn)則5.1.3

三角剖分算法分類與特點第5章不規(guī)則三角網(wǎng)(TIN)的建立數(shù)字高程模型2023/9/245.1.1TIN的理解

TIN的基本概念

不規(guī)則三角網(wǎng)（TriangulatedIrregularNetwork簡稱TIN）：是用一系列互不交叉、互不重疊的連接在一起的三角形來表示地形表面。TIN既是矢量結(jié)構(gòu)又有柵格的空間鋪蓋特征，能很好地描述和維護空間關(guān)系。5.1TIN概述

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/25T：三角化（Triangulated）是離散數(shù)據(jù)的三角剖分過程，也是TIN的建立過程。位于三角形內(nèi)的任意一點的高程值均可以通過三角形平面方程唯一確定。I：不規(guī)則性（Irregular），指用來構(gòu)建TIN的采樣點的分布形式。TIN具有可變分辨率，比格網(wǎng)DEM能更好反映地形起伏。N：網(wǎng)（Network），表達(dá)整個區(qū)域的三角形分布形態(tài)，即三角形之間不能交叉和重疊。三角形之間的拓?fù)潢P(guān)系隱含其中。5.1TIN概述

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/265.1.1TIN的理解

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

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/27z節(jié)點x邊面yTIN的基本元素5.1TIN概述

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/285.1.1TIN的理解

數(shù)據(jù)和TIN的類型用來進行TIN構(gòu)建的原始數(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ù)點之間存在著某種聯(lián)系，這種聯(lián)系一般通過線性特征來維護，如地形數(shù)據(jù)中的山脊線、山谷線上的點等。

5.1TIN概述

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/295.1.1TIN的理解

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

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

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/2105.1.1TIN的理解

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

良好的數(shù)據(jù)結(jié)構(gòu)和三角形剖分準(zhǔn)則，必須由高效的算法和程序?qū)崿F(xiàn)。5.1TIN概述

第5章不規(guī)則三角網(wǎng)(TIN)的建立面結(jié)構(gòu)、點結(jié)構(gòu)、點面結(jié)構(gòu)、邊結(jié)構(gòu)、邊面結(jié)構(gòu)2023/9/2115.1.2TIN的三角剖分準(zhǔn)則

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

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/2125.1.2TIN的三角剖分準(zhǔn)則

5.1TIN概述

第5章不規(guī)則三角網(wǎng)(TIN)的建立空外接圓準(zhǔn)則：在TIN中，過每個三角形的外接圓均不包含點集的其余任何點；最大最小角準(zhǔn)則：在TIN中的兩相鄰三角形形成的凸四邊形中，這兩三角形中的最小內(nèi)角一定大于交換凸四邊形對角線后所形成的兩三角形的最小內(nèi)角；最短距離和準(zhǔn)則：指一點到基邊的兩端的距離和為最小。2023/9/213張角最大準(zhǔn)則：一點到基邊的張角為最大。面積比準(zhǔn)則：三角形內(nèi)切圓面積與三角形面積或三角形面積與周長平方之比最小。對角線準(zhǔn)則：兩三角形組成的凸四邊形的兩條對角線之比。這一準(zhǔn)則的比值限定值，須給定，即當(dāng)計算值超過限定值才進行優(yōu)化。5.1TIN概述

第5章不規(guī)則三角網(wǎng)(TIN)的建立5.1.2TIN的三角剖分準(zhǔn)則

2023/9/2141）三角形準(zhǔn)則是建立三角形格網(wǎng)的基本原則，應(yīng)用不同的準(zhǔn)則將會得到不同的三角網(wǎng)。2）一般而言，應(yīng)盡量保持三角網(wǎng)的唯一性，即在同一準(zhǔn)則下由不同的位置開始建立三角形格網(wǎng)，其最終的形狀和結(jié)構(gòu)應(yīng)是相同的。3）空外接圓準(zhǔn)則、最大最小角準(zhǔn)則下進行的三角剖分稱為Delaunay(譯為狄洛尼或德勞內(nèi))三角剖分（Triangulation），簡稱DT?？胀饨訄A準(zhǔn)則也叫Delaunay法則。說明：5.1TIN概述

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/215關(guān)于delaunay三角網(wǎng)Dirichlet（1850年）和Voronoi（1908年）最早討論空間散點的關(guān)系問題。Voronoi圖的定義（P105）Voronoi圖把平面分成N個區(qū)，每一個區(qū)包括一個點，該點所在的區(qū)域是距離該點最近的點的集合。5.1TIN概述

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/216關(guān)于delaunay三角網(wǎng)1934年Delaunay提出了Voronoi圖的對稱圖，即Delaunay三角網(wǎng)（用直線段連接兩個相鄰多邊形內(nèi)的離散點而生成的三角網(wǎng)）。Delaunay三角網(wǎng)的特性：不存在四點共圓；每個三角形對應(yīng)于一個Voronoi圖頂點；每個三角形邊對應(yīng)于一個Voronoi圖邊；每個結(jié)點對應(yīng)于一個Voronoi圖區(qū)域；Delaunay圖的邊界是一個凸殼；三角網(wǎng)中三角形的最小角最大。5.1TIN概述

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/2175.1.3三角剖分算法分類與特點

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

規(guī)則分布采樣數(shù)據(jù)三角剖分從混合數(shù)據(jù)生成三角網(wǎng)基于等高線采樣數(shù)據(jù)三角剖分5.1TIN概述

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/2185.1.3三角剖分算法分類與特點

不規(guī)則分布采樣數(shù)據(jù)三角剖分（P64-67）

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

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/219

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

規(guī)則分布采樣數(shù)據(jù)三角剖分（P68-70）

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

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/2225.1.3三角剖分算法分類與特點

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

重要點法DEM建模有兩個關(guān)鍵步驟：

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

2）確定終止條件：達(dá)到預(yù)設(shè)的點數(shù)或預(yù)設(shè)的精度、或兩者折中。目前這類算法主要有地形骨架法、地形濾波法等。5.1TIN概述

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/223地形骨架法：利用地形特征點、線建立地形的骨架模型，然后對其進行插點，達(dá)到預(yù)定的精度；地表濾波法：將格網(wǎng)DEM看作為一幅數(shù)字圖像，可使用空間高通濾波器對其濾波，保留圖像中的高頻信息，即為地形特征點，濾掉低頻信息也即對地形特征而言不重要的點，在此基礎(chǔ)上建立TIN模型。2023/9/2245.1.3三角剖分算法分類與特點

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

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

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/2255.1.3三角剖分算法分類與特點

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

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

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/2265.2TIN的建立

5.2.1

無約束散點域的三角剖分算法與實現(xiàn)5.2.2約束散點數(shù)據(jù)域的三角剖分算法與實現(xiàn)5.2.3基于等高線數(shù)據(jù)的TIN的建立5.2.4基于柵格數(shù)據(jù)的三角網(wǎng)建立第5章不規(guī)則三角網(wǎng)(TIN)的建立數(shù)字高程模型2023/9/2275.2.1無約束散點域的三角剖分算法與實現(xiàn)

目前散點域的三角剖分使用最為廣泛的算法是Delaunay直接三角剖分算法。根據(jù)實現(xiàn)過程，把DT分成三類：1）三角網(wǎng)生長算法2）逐點插入算法

3）分割合并算法5.2TIN的建立

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/2281、三角網(wǎng)生長算法

三角網(wǎng)生長算法就是從一個“源”開始，逐步形成覆蓋整個數(shù)據(jù)區(qū)域的三角網(wǎng)。從生長過程角度，三角網(wǎng)生長算法分為收縮生長算法和擴張生長算法兩類。收縮生長算法是先形成整個數(shù)據(jù)域的數(shù)據(jù)邊界（凸殼），并以此作為源頭，逐步縮小以形成整個三角網(wǎng)。擴張生長算法與收縮算法過程剛好相反，是從一個三角形開始向外層層擴展，形成覆蓋整個區(qū)域的三角網(wǎng)。5.2TIN的建立

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/2291、三角網(wǎng)生長算法1）遞歸生長算法（P78）5.2TIN的建立第5章不規(guī)則三角網(wǎng)(TIN)的建立算法過程如下：在數(shù)據(jù)集中任取一點，查找距離此點最近的點，相連后作為初始基線；在初始基線右邊應(yīng)用Delaunay法則搜索第三點；生成Delaunay三角形，并以該三角形的兩條新邊作為新的基線；重復(fù)前面過程直至所有基線處理完畢；這種算法大量的時間花費在符合要求的鄰域點的搜索方面，為了減少搜索時間，許多學(xué)者提出了許多不同的方法，如將數(shù)據(jù)分塊并排列，以外接圓的方式限定其搜索范圍。2023/9/23012121212遞歸生長算法5.2TIN的建立

第5章不規(guī)則三角網(wǎng)(TIN)的建立3332023/9/2311、三角網(wǎng)生長算法該算法的基本思路:首先找到包含數(shù)據(jù)區(qū)域的最小凸多邊形，并從該多邊形開始從外向里逐層形成三角形格網(wǎng)。平面點凸閉包的定義是包含這些平面點的最小多邊形。在凸閉包中，連接任意兩點的線段必須完全位于多邊形內(nèi)。凸閉包是數(shù)據(jù)點的自然極限邊界，相當(dāng)于包圍數(shù)據(jù)點的最短路徑。凸閉包是數(shù)據(jù)集標(biāo)準(zhǔn)Delaunay三角網(wǎng)的一部分。計算凸閉包是該算法的核心。2）凸閉包收縮法5.2TIN的建立

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/2321）計算凸閉包的四個頂點；2）以此四點作為基點，通過邊右邊最大偏移量搜索其他凸閉包頂點。計算凸閉包的思路（P79）：2023/9/2331）將凸多邊形按逆時針保存記錄，以左下角點附近的頂點作為起點；2）確定第一條基邊；3）構(gòu)建第一個Delaunay三角形；4）重復(fù)(3)形成第一層Delaunay三角形；5）重新確定起點，重復(fù)(2)~(4)完成整個區(qū)域的三角網(wǎng)構(gòu)建。構(gòu)建三角網(wǎng)的具體算法（P80）：2023/9/2342、逐點插入算法

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

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

5.2TIN的建立

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/237分割合并算法2023/9/2385.2.2約束散點數(shù)據(jù)域的三角剖分算法與實現(xiàn)

約束三角網(wǎng)（CDT）的含義

約束三角網(wǎng)（CDT）的性質(zhì)在已存在的Delaunay三角網(wǎng)中插入約束線段5.2TIN的建立

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/2395.2.2約束散點數(shù)據(jù)域的三角剖分算法與實現(xiàn)

約束三角網(wǎng)（CDT）的含義

有不相交的地形特征線、特殊邊界線等作為預(yù)先定義的限制條件作用生成TIN，則要考慮約束條件的Delaunay三角網(wǎng)（ConstrainedDelaunayTriangulation）。

5.2TIN的建立

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/2405.2.2約束散點數(shù)據(jù)域的三角剖分算法與實現(xiàn)

帶約束條件的Delaunay法則（P83）只有當(dāng)三角形外接圓內(nèi)不包含任何其他點，且其三個頂點相互通視（MutuallyVisible）時，此三角形才是一個帶約束條件的Delaunay三角形。5.2TIN的建立

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/241在已存在的Delaunay三角網(wǎng)中插入約束線段；具體過程如下：確定邊界與約束線段相交的三角形，如果兩個這樣的三角形有公共邊，則將此公共邊刪除，最后形成約束線段的影響多邊形；將影響多邊形其他各頂點與約束線段的起始結(jié)點相連；應(yīng)用帶約束條件的Delaunay優(yōu)化法則，更新影響多邊形內(nèi)的三角網(wǎng)，使約束邊成為三角網(wǎng)中的一邊；重復(fù)以上步驟直到所有約束線段都加入到三角網(wǎng)中。5.2.2約束散點數(shù)據(jù)域的三角剖分算法與實現(xiàn)

5.2TIN的建立

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

約束線段插入（P83-84）2023/9/242約束線段插入過程搜索約束線段的影響多邊形連接約束線段的起始節(jié)點和影響多邊形的各個頂點應(yīng)用帶約束條件的delaunay優(yōu)化法則，更新影響多邊形內(nèi)的三角網(wǎng)，使約束邊成為三角網(wǎng)中的一邊重復(fù)以上步驟直到所有約束線段都加入到三角網(wǎng)中。2023/9/2435.2.3基于等高線數(shù)據(jù)的TIN的建立（P84-89）

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

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/2445.2.3基于等高線數(shù)據(jù)的TIN的建立等高線離散點直接生成TIN方法

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

在實際應(yīng)用中該方法較少使用。5.2TIN的建立

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/2455.2.3基于等高線數(shù)據(jù)的TIN的建立等高線作為特征線建立TIN將等高線作為斷裂線或結(jié)構(gòu)線；使用等高線上的特征點，并將等高線段作為約束線段處理。5.2TIN的建立

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/2465.2.3基于等高線數(shù)據(jù)的TIN的建立自動增加特征點及優(yōu)化TIN的方法

該方法實質(zhì)仍將等高線離散化建立TIN，但采用增加特征點的方式來消除TIN中的平三角形，并使用優(yōu)化TIN的方式來消除不合理的三角化；特征點的增加需要利用一定的算法自動提取，這些算法原理大都基于原始等高線的拓?fù)潢P(guān)系。5.2TIN的建立

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/2475.2.4基于柵格數(shù)據(jù)的三角網(wǎng)建立（P89-91）

在柵格方式下，數(shù)學(xué)形態(tài)學(xué)方法生成三角網(wǎng)是一種比較好的方法；數(shù)學(xué)形態(tài)學(xué)（MathematicMorphology）由法國統(tǒng)計學(xué)家Matheron和其學(xué)生Serra于1965年創(chuàng)立，主要用于研究數(shù)字影像形態(tài)結(jié)構(gòu)特征與快速并行處理方法；數(shù)學(xué)形態(tài)學(xué)是基于集合論發(fā)展而來，通過目標(biāo)影像進行形態(tài)變換來實現(xiàn)影像分析與識別。5.2TIN的建立

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/2485.2.4基于柵格數(shù)據(jù)的三角網(wǎng)建立數(shù)學(xué)形態(tài)學(xué)方法建立TIN的一般過程1）建立最小分辨率影像

取兩點間最小距離作為柵格基本單元，將所處理區(qū)域轉(zhuǎn)為一幅二值圖像（參考點所在像素灰度值為1，其他像素灰度值為0）。

5.2TIN的建立

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/2492）形成泰森多邊形設(shè)X為參考點像素集合，則除去這些參考后的剩余部分的骨架，即為建立TIN的泰森多邊形；

3）形成TIN

設(shè)X為參考點集，P是X中任一參考點，將與P所在的泰森多邊形相鄰的泰森多邊形中的參考點與P相連，即構(gòu)成以P為頂點的所有三角形的邊。5.2TIN的建立

第5章不規(guī)則三角網(wǎng)(TIN)的建立2023/9/250數(shù)學(xué)形態(tài)學(xué)方法用于TIN的生成參考點二值化去除參考點提取骨架