工學(xué)不規(guī)則三角網(wǎng)TIN的建立PPT教案

1、會計學(xué)1工學(xué)不規(guī)則三角網(wǎng)工學(xué)不規(guī)則三角網(wǎng)TIN的建立的建立2022-7-22第1頁/共58頁2022-7-235.1 TIN概述概述 5.2 TIN的建立的建立 5.3 TIN建立過程中的幾個問題建立過程中的幾個問題 第2頁/共58頁2022-7-24 TIN的理解的理解 TIN的三角剖分準(zhǔn)則的三角剖分準(zhǔn)則 三角剖分算法分類與特點(diǎn)三角剖分算法分類與特點(diǎn) 第3頁/共58頁2022-7-25 不規(guī)則三角網(wǎng)不規(guī)則三角網(wǎng)（Triangulated Irregular Network 簡稱簡稱TIN）：是用一系列互不交叉、互不重疊的連接在一起）：是用一系列互不交叉、互不重疊的連接在一起的三角形來表示地形

2、表面。的三角形來表示地形表面。TIN既是矢量結(jié)構(gòu)又有柵格既是矢量結(jié)構(gòu)又有柵格的空間鋪蓋特征，能很好地描述和維護(hù)空間關(guān)系。的空間鋪蓋特征，能很好地描述和維護(hù)空間關(guān)系。5.1 TIN概述 第4頁/共58頁2022-7-26T：三角化（三角化（ Triangulated ）是離散數(shù)據(jù)的三角剖分過）是離散數(shù)據(jù)的三角剖分過程，也是程，也是TIN的建立過程。位于三角形內(nèi)的任意一點(diǎn)的建立過程。位于三角形內(nèi)的任意一點(diǎn)的高程值均可以通過三角形平面方程唯一確定。的高程值均可以通過三角形平面方程唯一確定。I：不規(guī)則性（不規(guī)則性（ Irregular ），指用來構(gòu)建），指用來構(gòu)建TIN的采樣點(diǎn)的采樣點(diǎn)的分布形式。的分

3、布形式。TIN具有可變分辨率，比格網(wǎng)具有可變分辨率，比格網(wǎng)DEM能更能更好反映地形起伏。好反映地形起伏。N：網(wǎng)（網(wǎng)（ Network ），表達(dá)整個區(qū)域的三角形分布形），表達(dá)整個區(qū)域的三角形分布形態(tài)，即三角形之間不能交叉和重疊。三角形之間的拓態(tài)，即三角形之間不能交叉和重疊。三角形之間的拓?fù)潢P(guān)系隱含其中。撲關(guān)系隱含其中。第5頁/共58頁2022-7-27TIN的基本元素的基本元素l節(jié)點(diǎn)（節(jié)點(diǎn)（Node）：）：是相鄰三角形的公共頂點(diǎn)，也是用來是相鄰三角形的公共頂點(diǎn)，也是用來構(gòu)建構(gòu)建TIN的采樣數(shù)據(jù)；的采樣數(shù)據(jù)；l邊（邊（Edge）：）：指兩個三角形的公共邊界，是指兩個三角形的公共邊界，是TIN不光不

4、光滑性的具體反映。邊同時還包含特征線、斷裂線以及區(qū)域滑性的具體反映。邊同時還包含特征線、斷裂線以及區(qū)域邊界。邊界。l面（面（Face）：）：由最近的三個節(jié)點(diǎn)所組成的三角形面，是由最近的三個節(jié)點(diǎn)所組成的三角形面，是TIN描述地形表面的基本單元。描述地形表面的基本單元。TIN中的每一個三角形都中的每一個三角形都描述了局部地形傾斜狀態(tài)，具有唯一的坡度值。三角形在描述了局部地形傾斜狀態(tài)，具有唯一的坡度值。三角形在公共節(jié)點(diǎn)和邊上是無縫的，或者說三角形不能交叉和重疊公共節(jié)點(diǎn)和邊上是無縫的，或者說三角形不能交叉和重疊。5.1 TIN概述 第6頁/共58頁2022-7-28z節(jié)點(diǎn)節(jié)點(diǎn)x邊邊面面yTIN的基本元

5、的基本元素素第7頁/共58頁2022-7-29數(shù)據(jù)和數(shù)據(jù)和TIN的類型的類型l用來進(jìn)行用來進(jìn)行TIN構(gòu)建的原始數(shù)據(jù)根據(jù)數(shù)據(jù)點(diǎn)之間的約構(gòu)建的原始數(shù)據(jù)根據(jù)數(shù)據(jù)點(diǎn)之間的約束條件可分為束條件可分為無約束數(shù)據(jù)域無約束數(shù)據(jù)域和和約束數(shù)據(jù)域約束數(shù)據(jù)域兩種類型。兩種類型。 l無約束數(shù)據(jù)域無約束數(shù)據(jù)域是指數(shù)據(jù)點(diǎn)之間不存在任何關(guān)系，即是指數(shù)據(jù)點(diǎn)之間不存在任何關(guān)系，即數(shù)據(jù)分布完全呈離散狀態(tài)，數(shù)據(jù)點(diǎn)之間在物理上相互數(shù)據(jù)分布完全呈離散狀態(tài)，數(shù)據(jù)點(diǎn)之間在物理上相互獨(dú)立。獨(dú)立。l約束數(shù)據(jù)約束數(shù)據(jù)域域則是部分?jǐn)?shù)據(jù)點(diǎn)之間存在著某種聯(lián)系，則是部分?jǐn)?shù)據(jù)點(diǎn)之間存在著某種聯(lián)系，這種聯(lián)系一般通過線性特征來維護(hù)，如地形數(shù)據(jù)中的這種聯(lián)系一般

6、通過線性特征來維護(hù)，如地形數(shù)據(jù)中的山脊線、山谷線上的點(diǎn)等。山脊線、山谷線上的點(diǎn)等。 5.1 TIN概述 第8頁/共58頁2022-7-210TIN的體系結(jié)構(gòu)的體系結(jié)構(gòu) TIN對三角形的幾何形狀有嚴(yán)格的要求。對三角形的幾何形狀有嚴(yán)格的要求。 TIN模型一般有三個基本要求：模型一般有三個基本要求：1）三角形的格網(wǎng)唯一；）三角形的格網(wǎng)唯一；2）最佳三角形形狀，盡量接近正三角形；）最佳三角形形狀，盡量接近正三角形；3）三角形邊長之和最小，保證最近的點(diǎn)形成）三角形邊長之和最小，保證最近的點(diǎn)形成 三角形。三角形。5.1 TIN概述 第9頁/共58頁2022-7-211TIN的體系結(jié)構(gòu)的體系結(jié)構(gòu) 良好的數(shù)據(jù)

7、結(jié)構(gòu)和三角形剖分準(zhǔn)則，必須良好的數(shù)據(jù)結(jié)構(gòu)和三角形剖分準(zhǔn)則，必須由高效的算法和程序?qū)崿F(xiàn)。由高效的算法和程序?qū)崿F(xiàn)。5.1 TIN概述 第10頁/共58頁2022-7-212l TIN的三角剖分準(zhǔn)則是指的三角剖分準(zhǔn)則是指TIN中三角形的中三角形的形成法則，它決定著三角形的幾何形狀和形成法則，它決定著三角形的幾何形狀和TIN的質(zhì)量。的質(zhì)量。l 目前，在目前，在GIS、計算機(jī)和圖形學(xué)領(lǐng)域常用、計算機(jī)和圖形學(xué)領(lǐng)域常用的三角剖分準(zhǔn)則有的三角剖分準(zhǔn)則有6種。種。5.1 TIN概述 第11頁/共58頁2022-7-2135.1 TIN概述 空外接圓準(zhǔn)則：空外接圓準(zhǔn)則：在在TIN中，過每個三角形的外接圓均不包含點(diǎn)

8、集的中，過每個三角形的外接圓均不包含點(diǎn)集的其余任何點(diǎn)；其余任何點(diǎn)；最大最小角準(zhǔn)則：最大最小角準(zhǔn)則：在在TIN中的兩相鄰三角形形成的凸四邊形中，這中的兩相鄰三角形形成的凸四邊形中，這兩三角形中的最小內(nèi)角一定大于交換凸四邊形對角線后所形成的兩三兩三角形中的最小內(nèi)角一定大于交換凸四邊形對角線后所形成的兩三角形的最小內(nèi)角；角形的最小內(nèi)角；最短距離和準(zhǔn)則：最短距離和準(zhǔn)則：指一點(diǎn)到基邊的兩端的距離和為最小。指一點(diǎn)到基邊的兩端的距離和為最小。第12頁/共58頁2022-7-214張角最大準(zhǔn)則：張角最大準(zhǔn)則：一點(diǎn)到基邊的張角為最大。一點(diǎn)到基邊的張角為最大。面積比準(zhǔn)則：面積比準(zhǔn)則：三角形內(nèi)切圓面積與三角形面積或

9、三角形面積與周長三角形內(nèi)切圓面積與三角形面積或三角形面積與周長平方之比最小。平方之比最小。 對角線準(zhǔn)則：對角線準(zhǔn)則：兩三角形組成的凸四邊形的兩條對角線之比。這一準(zhǔn)兩三角形組成的凸四邊形的兩條對角線之比。這一準(zhǔn)則的比值限定值，須給定，即當(dāng)計算值超過限定值才進(jìn)行優(yōu)化。則的比值限定值，須給定，即當(dāng)計算值超過限定值才進(jìn)行優(yōu)化。的三角剖分準(zhǔn)則的三角剖分準(zhǔn)則 第13頁/共58頁2022-7-215l1）三角形準(zhǔn)則是建立三角形格網(wǎng)的基本原則，應(yīng)）三角形準(zhǔn)則是建立三角形格網(wǎng)的基本原則，應(yīng)用不同的準(zhǔn)則將會得到不同的三角網(wǎng)。用不同的準(zhǔn)則將會得到不同的三角網(wǎng)。l2）一般而言，應(yīng)盡量保持三角網(wǎng)的唯一性，即在）一般而言

10、，應(yīng)盡量保持三角網(wǎng)的唯一性，即在同一準(zhǔn)則下由不同的位置開始建立三角形格網(wǎng)，其同一準(zhǔn)則下由不同的位置開始建立三角形格網(wǎng)，其最終的形狀和結(jié)構(gòu)應(yīng)是相同的最終的形狀和結(jié)構(gòu)應(yīng)是相同的。l3）空外接圓準(zhǔn)則、最大最小角準(zhǔn)則下進(jìn)行的三角）空外接圓準(zhǔn)則、最大最小角準(zhǔn)則下進(jìn)行的三角剖分稱為剖分稱為Delaunay (譯為狄洛尼或德勞內(nèi)譯為狄洛尼或德勞內(nèi))三角剖分三角剖分（Triangulation），簡稱，簡稱DT。空外接圓準(zhǔn)則也叫?？胀饨訄A準(zhǔn)則也叫Delaunay法則。法則。第14頁/共58頁2022-7-2165.1 TIN概述 第15頁/共58頁2022-7-2175.1 TIN概述 第16頁/共58頁20

11、22-7-218 規(guī)則分布采樣數(shù)據(jù)三角剖分規(guī)則分布采樣數(shù)據(jù)三角剖分 基于等高線采樣數(shù)據(jù)三角剖分基于等高線采樣數(shù)據(jù)三角剖分 5.1 TIN概述 第17頁/共58頁2022-7-219不規(guī)則分布采樣數(shù)據(jù)三角剖分（不規(guī)則分布采樣數(shù)據(jù)三角剖分（P64-67） 在目前所有的三角化算法中，以在目前所有的三角化算法中，以Delaunay三角網(wǎng)的應(yīng)三角網(wǎng)的應(yīng)用最為廣泛。用最為廣泛。Delaunay 三角網(wǎng)為相互鄰接且互不重疊的三角形的三角網(wǎng)為相互鄰接且互不重疊的三角形的集合，每一個三角形的外接圓內(nèi)不包含其它的點(diǎn)。集合，每一個三角形的外接圓內(nèi)不包含其它的點(diǎn)。DT的主要特點(diǎn)是它能自動地避免狹長的三角形，保的主要特

12、點(diǎn)是它能自動地避免狹長的三角形，保證了良好的三角形形狀。證了良好的三角形形狀。DT的兩個顯著特性的兩個顯著特性最大最小最大最小角特性角特性和和空外接圓特性空外接圓特性是構(gòu)成各種是構(gòu)成各種DT剖分的基礎(chǔ)。剖分的基礎(chǔ)。5.1 TIN概述 第18頁/共58頁2022-7-220 新插入點(diǎn)與已知三角網(wǎng)存在四種關(guān)系（新插入點(diǎn)與已知三角網(wǎng)存在四種關(guān)系（P66）：（a）在三角形內(nèi)）在三角形內(nèi)（b）在三角形外接圓內(nèi)）在三角形外接圓內(nèi)（c）在三角形外接圓上）在三角形外接圓上（d）在三角形外接圓外）在三角形外接圓外第19頁/共58頁2022-7-221局部幾何形狀最優(yōu)，采用局部幾何形狀最優(yōu)，采用LOP算法算法（局

13、部優(yōu)化過程，（局部優(yōu)化過程，Local Optimal Procedure）。）。其基本思想：其基本思想：運(yùn)用運(yùn)用DT三角網(wǎng)的三角網(wǎng)的空外接圓性質(zhì)對空外接圓性質(zhì)對兩個公共邊的三兩個公共邊的三角形組成的四邊角形組成的四邊形進(jìn)行判斷，如形進(jìn)行判斷，如果其中一個三角果其中一個三角形的外接圓中含形的外接圓中含有第四點(diǎn)，則交有第四點(diǎn)，則交換四邊形的對角換四邊形的對角線。線。 第20頁/共58頁2022-7-222 規(guī)則分布采樣數(shù)據(jù)三角剖分規(guī)則分布采樣數(shù)據(jù)三角剖分（P68-70） l規(guī)則數(shù)據(jù)生成規(guī)則數(shù)據(jù)生成TIN，一般有兩種方式：，一般有兩種方式：1）直接將格網(wǎng)分解組合即可得到三角網(wǎng)；）直接將格網(wǎng)分解組合

14、即可得到三角網(wǎng)； 2）通過一定法則，選擇）通過一定法則，選擇“重要重要”點(diǎn)點(diǎn)( very important points，VIPs )建立三角形。建立三角形。根據(jù)規(guī)則數(shù)據(jù)建成的三角形格網(wǎng)根據(jù)規(guī)則數(shù)據(jù)建成的三角形格網(wǎng)5.1 TIN概述 第21頁/共58頁2022-7-223 規(guī)則分布采樣數(shù)據(jù)三角剖分規(guī)則分布采樣數(shù)據(jù)三角剖分l 重要點(diǎn)法重要點(diǎn)法DEM建模有兩個關(guān)鍵步驟：建模有兩個關(guān)鍵步驟： 1）確定格網(wǎng)點(diǎn)的）確定格網(wǎng)點(diǎn)的“重要程度重要程度”：全局最重要或局：全局最重要或局部最重要；部最重要； 2）確定終止條件：達(dá)到預(yù)設(shè)的點(diǎn)數(shù)或預(yù)設(shè)的精度）確定終止條件：達(dá)到預(yù)設(shè)的點(diǎn)數(shù)或預(yù)設(shè)的精度、或兩者折中。、或

15、兩者折中。l目前這類算法主要有目前這類算法主要有地形骨架法、地形濾波地形骨架法、地形濾波法等法等。5.1 TIN概述 第22頁/共58頁2022-7-224第23頁/共58頁2022-7-225從混合數(shù)據(jù)生成三角網(wǎng)從混合數(shù)據(jù)生成三角網(wǎng)（P70） l 混合數(shù)據(jù)：是指鏈狀數(shù)據(jù)混合數(shù)據(jù)：是指鏈狀數(shù)據(jù)（如斷裂線、河流線等）與（如斷裂線、河流線等）與規(guī)則格網(wǎng)采樣數(shù)據(jù)結(jié)合形成規(guī)則格網(wǎng)采樣數(shù)據(jù)結(jié)合形成的一種數(shù)據(jù)。的一種數(shù)據(jù)。l 此種數(shù)據(jù)建立三角網(wǎng)的方此種數(shù)據(jù)建立三角網(wǎng)的方法：首先分解規(guī)則三角形，法：首先分解規(guī)則三角形，然后考慮特征線上的點(diǎn)，在然后考慮特征線上的點(diǎn)，在格網(wǎng)中生成不規(guī)則三角形。格網(wǎng)中生成不規(guī)則三

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

17、58頁2022-7-228l 目前散點(diǎn)域的三角剖分使用最為廣泛的算法是目前散點(diǎn)域的三角剖分使用最為廣泛的算法是Delaunay直接三角剖分算法。直接三角剖分算法。l 根據(jù)實現(xiàn)過程，把根據(jù)實現(xiàn)過程，把DT分成三類：分成三類：1）三角網(wǎng)生長）三角網(wǎng)生長算法算法2）逐點(diǎn)插入算法）逐點(diǎn)插入算法 3）分割合并算法分割合并算法5.2 TIN的建立 第27頁/共58頁2022-7-2291、三角網(wǎng)生長算法、三角網(wǎng)生長算法l 三角網(wǎng)生長算法就是從一個三角網(wǎng)生長算法就是從一個“源源”開始，逐步形成開始，逐步形成覆蓋整個數(shù)據(jù)區(qū)域的三角網(wǎng)。覆蓋整個數(shù)據(jù)區(qū)域的三角網(wǎng)。l 從生長過程角度，三角網(wǎng)生長算法分為從生長過程角

18、度，三角網(wǎng)生長算法分為收縮生長算收縮生長算法法和和擴(kuò)張生長算法擴(kuò)張生長算法兩類。兩類。l 收縮生長算法是先形成整個數(shù)據(jù)域的數(shù)據(jù)邊界（凸收縮生長算法是先形成整個數(shù)據(jù)域的數(shù)據(jù)邊界（凸殼），并以此作為源頭，逐步縮小以形成整個三角網(wǎng)殼），并以此作為源頭，逐步縮小以形成整個三角網(wǎng)。l 擴(kuò)張生長算法與收縮算法過程剛好相反，是從一個擴(kuò)張生長算法與收縮算法過程剛好相反，是從一個三角形開始向外層層擴(kuò)展，形成覆蓋整個區(qū)域的三角三角形開始向外層層擴(kuò)展，形成覆蓋整個區(qū)域的三角網(wǎng)。網(wǎng)。第28頁/共58頁2022-7-2301、三角網(wǎng)生長算法、三角網(wǎng)生長算法1）遞歸生長算法（）遞歸生長算法（P78）第29頁/共58頁20

19、22-7-23112121212遞歸生長算法遞歸生長算法5.2 TIN的建立 333第30頁/共58頁2022-7-2321、三角網(wǎng)生長算法、三角網(wǎng)生長算法l該算法的基本思路該算法的基本思路:首先找到包含數(shù)據(jù)區(qū)域的最小凸多首先找到包含數(shù)據(jù)區(qū)域的最小凸多邊形，并從該多邊形開始從外向里逐層形成三角形格邊形，并從該多邊形開始從外向里逐層形成三角形格網(wǎng)。網(wǎng)。l平面點(diǎn)平面點(diǎn)凸閉包凸閉包的定義是包含這些平面點(diǎn)的最小多邊形的定義是包含這些平面點(diǎn)的最小多邊形。l在凸閉包中，連接任意兩點(diǎn)的線段必須完全位于多邊在凸閉包中，連接任意兩點(diǎn)的線段必須完全位于多邊形內(nèi)。凸閉包是數(shù)據(jù)點(diǎn)的自然極限邊界，相當(dāng)于包圍形內(nèi)。凸閉包

20、是數(shù)據(jù)點(diǎn)的自然極限邊界，相當(dāng)于包圍數(shù)據(jù)點(diǎn)的最短路徑。數(shù)據(jù)點(diǎn)的最短路徑。l凸閉包是數(shù)據(jù)集標(biāo)準(zhǔn)凸閉包是數(shù)據(jù)集標(biāo)準(zhǔn)Delaunay三角網(wǎng)的一部分。計算三角網(wǎng)的一部分。計算凸閉包是該算法的核心。凸閉包是該算法的核心。2）凸閉包收縮法）凸閉包收縮法第31頁/共58頁2022-7-2331）計算凸閉包的四個頂點(diǎn)；）計算凸閉包的四個頂點(diǎn)；2）以此四點(diǎn)作為基點(diǎn)，通過邊右邊最大偏移量搜索其他凸）以此四點(diǎn)作為基點(diǎn)，通過邊右邊最大偏移量搜索其他凸閉包頂點(diǎn)。閉包頂點(diǎn)。計算凸閉包的思路（計算凸閉包的思路（P79）：）：第32頁/共58頁2022-7-2341）將凸多邊形按逆時針保存記錄，以左下角點(diǎn)附近的頂點(diǎn)作為）將凸多

21、邊形按逆時針保存記錄，以左下角點(diǎn)附近的頂點(diǎn)作為起點(diǎn)；起點(diǎn)；2）確定第一條基邊；）確定第一條基邊；3）構(gòu)建第一個）構(gòu)建第一個Delaunay三角形；三角形；4）重復(fù)）重復(fù)(3)形成第一層形成第一層Delaunay三角形；三角形；5）重新確定起點(diǎn)，重復(fù)）重新確定起點(diǎn)，重復(fù)(2)(4)完成整個區(qū)域的三角網(wǎng)構(gòu)建。完成整個區(qū)域的三角網(wǎng)構(gòu)建。構(gòu)建三角網(wǎng)的具體算法構(gòu)建三角網(wǎng)的具體算法（P80）：）：第33頁/共58頁2022-7-2352、逐點(diǎn)插入算法、逐點(diǎn)插入算法 （P81）：）：第34頁/共58頁2022-7-236逐點(diǎn)插入算法逐點(diǎn)插入算法第35頁/共58頁2022-7-2373、分割合并算法、分割合并

22、算法 分割合并算法的思想很簡單，首先將數(shù)據(jù)點(diǎn)分割分割合并算法的思想很簡單，首先將數(shù)據(jù)點(diǎn)分割成易于進(jìn)行三角化的子集，然后對每個子集進(jìn)行三成易于進(jìn)行三角化的子集，然后對每個子集進(jìn)行三角剖分，并用角剖分，并用LOP算法保證三角剖分為算法保證三角剖分為Delaunay三三角網(wǎng)。當(dāng)每個子集剖分完成后，對每個子集的三角角網(wǎng)。當(dāng)每個子集剖分完成后，對每個子集的三角剖分進(jìn)行合并，形成最終的整體三角網(wǎng)。剖分進(jìn)行合并，形成最終的整體三角網(wǎng)。 第36頁/共58頁2022-7-238分割合并算法分割合并算法第37頁/共58頁2022-7-239 約束三角網(wǎng)（約束三角網(wǎng)（CDT）的含義）的含義 約束三角網(wǎng)（約束三角網(wǎng)（

23、CDT）的性質(zhì)）的性質(zhì) 在已存在的在已存在的Delaunay三角網(wǎng)三角網(wǎng)中中 插入約束線段插入約束線段5.2 TIN的建立 第38頁/共58頁2022-7-240 約束三角網(wǎng)（約束三角網(wǎng)（CDT）的含義）的含義 有不相交的地形特征線、特殊邊界線等作為有不相交的地形特征線、特殊邊界線等作為預(yù)先定義的限制條件作用生成預(yù)先定義的限制條件作用生成TIN，則要考慮約，則要考慮約束條件的束條件的Delaunay三角網(wǎng)（三角網(wǎng)（Constrained Delaunay Triangulation ）。）。 5.2 TIN的建立 第39頁/共58頁2022-7-241 帶約束條件的帶約束條件的Delaunay

24、法則（法則（P83）u只有當(dāng)三角形外接圓內(nèi)不包含任何其他點(diǎn)，且只有當(dāng)三角形外接圓內(nèi)不包含任何其他點(diǎn)，且其三個頂點(diǎn)相互通視（其三個頂點(diǎn)相互通視（Mutually Visible）時，）時，此三角形才是一個帶約束條件的此三角形才是一個帶約束條件的Delaunay三角三角形。形。5.2 TIN的建立 第40頁/共58頁2022-7-242n重復(fù)以上步驟直到所有重復(fù)以上步驟直到所有約束線段約束線段都加都加入到三角網(wǎng)中。入到三角網(wǎng)中。約束散點(diǎn)數(shù)據(jù)域的三角剖分算法與實現(xiàn)約束散點(diǎn)數(shù)據(jù)域的三角剖分算法與實現(xiàn) 5.2 TIN的建立 約束約束線段插入（線段插入（P83-84）第41頁/共58頁2022-7-243

25、約束線段插入過程約束線段插入過程搜索約束線段的影響多邊形搜索約束線段的影響多邊形連接約束線段的起始連接約束線段的起始節(jié)點(diǎn)和影響多邊形的節(jié)點(diǎn)和影響多邊形的各個頂點(diǎn)各個頂點(diǎn)應(yīng)用帶約束條件的應(yīng)用帶約束條件的delaunay優(yōu)優(yōu)化法則，更新化法則，更新影響多邊形影響多邊形內(nèi)的內(nèi)的三角網(wǎng)，使約束邊成為三角網(wǎng)三角網(wǎng)，使約束邊成為三角網(wǎng)中的一邊中的一邊重復(fù)以上步驟直到重復(fù)以上步驟直到所有所有約束線段約束線段都加都加入到三角網(wǎng)中。入到三角網(wǎng)中。第42頁/共58頁2022-7-244 等高線離散點(diǎn)直接生成等高線離散點(diǎn)直接生成TIN； 將等高線作為特征線的方法；將等高線作為特征線的方法； 自動增加特征點(diǎn)及優(yōu)化自動

26、增加特征點(diǎn)及優(yōu)化TIN的方法。的方法。5.2 TIN的建立 第43頁/共58頁2022-7-245等高線離散點(diǎn)直接生成等高線離散點(diǎn)直接生成TIN方法方法 l 該方法直接將等高線離散化，然后利用常用該方法直接將等高線離散化，然后利用常用TIN的生的生成算法，該方法沒有考慮離散點(diǎn)間原有的連接關(guān)系，模成算法，該方法沒有考慮離散點(diǎn)間原有的連接關(guān)系，模擬的地形就會失真，具體表現(xiàn)為擬的地形就會失真，具體表現(xiàn)為三角形的邊穿越等高線三角形的邊穿越等高線和存在和存在平三角形平三角形的兩種情況。的兩種情況。 l 在實際應(yīng)用中該方法較少使用。在實際應(yīng)用中該方法較少使用。5.2 TIN的建立 第44頁/共58頁202

27、2-7-246等高線作為特征線建立等高線作為特征線建立TIN l將等高線作為將等高線作為斷裂線或結(jié)構(gòu)線斷裂線或結(jié)構(gòu)線；l使用等高線上使用等高線上的特征點(diǎn)，并將的特征點(diǎn)，并將等高線段作為約等高線段作為約束線段處理。束線段處理。5.2 TIN的建立 第45頁/共58頁2022-7-247自動增加特征點(diǎn)及優(yōu)化自動增加特征點(diǎn)及優(yōu)化TIN的方法的方法l 該方法實質(zhì)仍將等高該方法實質(zhì)仍將等高線離散化建立線離散化建立TIN，但，但采用增加特征點(diǎn)的方式采用增加特征點(diǎn)的方式來消除來消除TIN中的平三角中的平三角形，并使用優(yōu)化形，并使用優(yōu)化TIN的的方式來消除不合理的三方式來消除不合理的三角化；角化；l特征點(diǎn)的增

28、加需要利特征點(diǎn)的增加需要利用一定的算法自動提取用一定的算法自動提取，這些算法原理大都基，這些算法原理大都基于原始等高線的拓?fù)潢P(guān)于原始等高線的拓?fù)潢P(guān)系。系。5.2 TIN的建立 第46頁/共58頁2022-7-248l 在柵格方式下，數(shù)學(xué)形態(tài)學(xué)方法生成三角網(wǎng)在柵格方式下，數(shù)學(xué)形態(tài)學(xué)方法生成三角網(wǎng) 是一種比較好的方法；是一種比較好的方法；l數(shù)學(xué)形態(tài)學(xué)（數(shù)學(xué)形態(tài)學(xué)（Mathematic Morphology）由法）由法國統(tǒng)計學(xué)家國統(tǒng)計學(xué)家Matheron和其學(xué)生和其學(xué)生Serra于于1965年創(chuàng)年創(chuàng)立，主要用于研究數(shù)字影像形態(tài)結(jié)構(gòu)特征與快立，主要用于研究數(shù)字影像形態(tài)結(jié)構(gòu)特征與快速并行處理方法；速并行

29、處理方法； l 數(shù)學(xué)形態(tài)學(xué)是基于集合論發(fā)展而來，通過目數(shù)學(xué)形態(tài)學(xué)是基于集合論發(fā)展而來，通過目標(biāo)影像進(jìn)行形態(tài)變換來實現(xiàn)影像分析與識別。標(biāo)影像進(jìn)行形態(tài)變換來實現(xiàn)影像分析與識別。5.2 TIN的建立 第47頁/共58頁2022-7-249數(shù)學(xué)形態(tài)學(xué)方法建立數(shù)學(xué)形態(tài)學(xué)方法建立TIN的一般過程的一般過程 1）建立最小分辨率影像）建立最小分辨率影像 取兩點(diǎn)間最小距離作為柵格基本單元，將所處理取兩點(diǎn)間最小距離作為柵格基本單元，將所處理區(qū)域轉(zhuǎn)為一幅二值圖像（參考點(diǎn)所在像素灰度值為區(qū)域轉(zhuǎn)為一幅二值圖像（參考點(diǎn)所在像素灰度值為1，其他像素灰度值為其他像素灰度值為0）。）。 5.2 TIN的建立 第48頁/共58頁2022-7-2502） 形成泰森多邊形形成泰森多邊形 設(shè)設(shè)X為參考點(diǎn)像素集合，則除去這些參考后的剩余為參考點(diǎn)像素集合，則除去這些參考后的剩余部分的骨架，即為建立部分的骨架，即為建立TIN的泰森多邊形；的泰森多邊形； 3） 形成形成TIN 設(shè)設(shè)X為參考點(diǎn)集，為參考點(diǎn)集，P是是X中任一參考點(diǎn)，將與中任一參考點(diǎn)，將與P所在的所在的泰森多邊形相鄰的泰森多邊形中的參考點(diǎn)與泰森多邊形相鄰的泰森多邊形中的參考點(diǎn)與P相連，即相連，即構(gòu)成以構(gòu)成以P為頂點(diǎn)的所有三角形的邊。為頂點(diǎn)的所有三角形的邊。 第49頁/共58頁2022-7-251數(shù)學(xué)形態(tài)學(xué)方法