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

1、2022-3-41馬仕航馬仕航14100402221410040222 TIN概述 5.1.1 TIN TIN的理解的理解5.1.25.1.2 TIN TIN的三角剖分準則的三角剖分準則 5.1.35.1.3 三角剖分算法分類與特三角剖分算法分類與特點點 2022-3-42 不規(guī)則三角網(wǎng)不規(guī)則三角網(wǎng)（Triangulated Irregular Network Triangulated Irregular Network 簡稱簡稱TINTIN）：是用一系列互不交叉、互不重疊的連接在一：是用一系列互不交叉、互不重疊的連接在一起的三角形來表示地形表面。起的三角形來表示地形表面。TINTIN既是矢量

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

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

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

5、邊面面y數(shù)據(jù)和數(shù)據(jù)和TINTIN的類型的類型l用來進行用來進行TINTIN構(gòu)建的原始數(shù)據(jù)根據(jù)數(shù)據(jù)點之間的約束構(gòu)建的原始數(shù)據(jù)根據(jù)數(shù)據(jù)點之間的約束條件可分為條件可分為無約束數(shù)據(jù)域無約束數(shù)據(jù)域和和約束數(shù)據(jù)域約束數(shù)據(jù)域兩種類型。兩種類型。 l無約束數(shù)據(jù)域無約束數(shù)據(jù)域是指數(shù)據(jù)點之間不存在任何關(guān)系，即是指數(shù)據(jù)點之間不存在任何關(guān)系，即數(shù)據(jù)分布完全呈離散狀態(tài)，數(shù)據(jù)點之間在物理上相互數(shù)據(jù)分布完全呈離散狀態(tài)，數(shù)據(jù)點之間在物理上相互獨立。獨立。l約束數(shù)據(jù)域約束數(shù)據(jù)域則是部分數(shù)據(jù)點之間存在著某種聯(lián)系，則是部分數(shù)據(jù)點之間存在著某種聯(lián)系，這種聯(lián)系一般通過線性特征來維護，如地形數(shù)據(jù)中的這種聯(lián)系一般通過線性特征來維護，如地形

6、數(shù)據(jù)中的山脊線、山谷線上的點等山脊線、山谷線上的點等。 2022-3-46TINTIN的體系結(jié)構(gòu)的體系結(jié)構(gòu) TINTIN對三角形的幾何形狀一般有三個基本要求：對三角形的幾何形狀一般有三個基本要求：1 1）三角形的格網(wǎng)唯一；）三角形的格網(wǎng)唯一；2 2）最佳三角形形狀，盡量接近正三角形；）最佳三角形形狀，盡量接近正三角形；3 3）三角形邊長之和最小，保證最近的點形成）三角形邊長之和最小，保證最近的點形成 三角形。三角形。2022-3-47 TIN的三角剖分準則的三角剖分準則 l TINTIN的三角剖分準則是指的三角剖分準則是指TINTIN中三角形的中三角形的形成法則，它決定著三角形的幾何形狀和形成

7、法則，它決定著三角形的幾何形狀和TINTIN的質(zhì)量。的質(zhì)量。l 目前，在目前，在GISGIS、計算機和圖形學領域常用、計算機和圖形學領域常用的三角剖分準則有的三角剖分準則有6 6種。種。2022-3-48空外接圓準則：空外接圓準則：在在TINTIN中，過每個三角形的外接圓均不包含點集的中，過每個三角形的外接圓均不包含點集的其余任何點；其余任何點；最大最小角準則：最大最小角準則：在在TINTIN中的兩相鄰三角形形成的凸四邊形中，這中的兩相鄰三角形形成的凸四邊形中，這兩三角形中的最小內(nèi)角一定大于交換凸四邊形對角線后所形成的兩三兩三角形中的最小內(nèi)角一定大于交換凸四邊形對角線后所形成的兩三角形的最小內(nèi)

8、角；角形的最小內(nèi)角；最短距離和準則：最短距離和準則：指一點到基邊的兩端的距離和為最小。指一點到基邊的兩端的距離和為最小。2022-3-49張角最大準則：張角最大準則：一點到基邊的張角為最大。一點到基邊的張角為最大。面積比準則：面積比準則：三角形內(nèi)切圓面積與三角形面積或三角形面積與周長三角形內(nèi)切圓面積與三角形面積或三角形面積與周長平方之比最小。平方之比最小。 對角線準則：對角線準則：兩三角形組成的凸四邊形的兩條對角線之比。這一準兩三角形組成的凸四邊形的兩條對角線之比。這一準則的比值限定值，須給定，即當計算值超過限定值才進行優(yōu)化。則的比值限定值，須給定，即當計算值超過限定值才進行優(yōu)化。2022-3

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

10、分（三角剖分（TriangulationTriangulation），簡稱，簡稱DTDT。空外接圓準則也叫空外接圓準則也叫DelaunayDelaunay法則。法則。2022-3-411關(guān)于關(guān)于delaunaydelaunay三角網(wǎng)三角網(wǎng)19341934年年DelaunayDelaunay提出了提出了VoronoiVoronoi圖的對稱圖，圖的對稱圖，即即DelaunayDelaunay三角網(wǎng)（用直線段連接兩個相鄰三角網(wǎng)（用直線段連接兩個相鄰多邊形內(nèi)的離散點而生成的三角網(wǎng)）。多邊形內(nèi)的離散點而生成的三角網(wǎng)）。DelaunayDelaunay三角網(wǎng)的特性：三角網(wǎng)的特性： 不存在四點共圓；不存在四

11、點共圓； 每個三角形對應于一個每個三角形對應于一個VoronoiVoronoi圖頂點；圖頂點； 每個三角形邊對應于一個每個三角形邊對應于一個VoronoiVoronoi圖邊；圖邊； 每個結(jié)點對應于一個每個結(jié)點對應于一個VoronoiVoronoi圖區(qū)域；圖區(qū)域； DelaunayDelaunay圖的邊界是一個凸殼；圖的邊界是一個凸殼； 三角網(wǎng)中三角形的最小角最大。三角網(wǎng)中三角形的最小角最大。2022-3-412 TIN的建立 2022-3-413無約束散點域的三角剖分算法與實現(xiàn)無約束散點域的三角剖分算法與實現(xiàn) l 目前散點域的三角剖分使用最為廣泛的算法是目前散點域的三角剖分使用最為廣泛的算法是

12、DelaunayDelaunay直接三角剖分算法。直接三角剖分算法。1 1）三角網(wǎng)生長算法）三角網(wǎng)生長算法2 2）逐點插入算法）逐點插入算法 3 3）分割合并算法）分割合并算法2022-3-4141 1、三角網(wǎng)生長算法、三角網(wǎng)生長算法l 三角網(wǎng)生長算法就是從一個三角網(wǎng)生長算法就是從一個“源源”開始，逐步形成開始，逐步形成覆蓋整個數(shù)據(jù)區(qū)域的三角網(wǎng)。覆蓋整個數(shù)據(jù)區(qū)域的三角網(wǎng)。l 從生長過程角度，三角網(wǎng)生長算法分為從生長過程角度，三角網(wǎng)生長算法分為收縮生長算收縮生長算法法和和擴張生長算法擴張生長算法兩類。兩類。l 收縮生長算法是先形成整個數(shù)據(jù)域的數(shù)據(jù)邊界（凸收縮生長算法是先形成整個數(shù)據(jù)域的數(shù)據(jù)邊界（

13、凸殼），并以此作為源頭，逐步縮小以形成整個三角網(wǎng)。殼），并以此作為源頭，逐步縮小以形成整個三角網(wǎng)。l 擴張生長算法與收縮算法過程剛好相反，是從一個擴張生長算法與收縮算法過程剛好相反，是從一個三角形開始向外層層擴展，形成覆蓋整個區(qū)域的三角三角形開始向外層層擴展，形成覆蓋整個區(qū)域的三角網(wǎng)。網(wǎng)。2022-3-4151 1、三角網(wǎng)生長算法、三角網(wǎng)生長算法1 1）遞歸生長算法）遞歸生長算法 算法過程如下：在數(shù)據(jù)集中任取一點，查找距離此點最近的點，相連后作為初始基線；在初始基線右邊應用Delaunay法則搜索第三點；生成Delaunay三角形，并以該三角形的兩條新邊作為新的基線；重復前面過程直至所有基線處

14、理完畢； 這種算法大量的時間花費在符合要求的鄰域點的搜索方面，為了減少搜索時間，許多學者提出了許多不同的方法，如將數(shù)據(jù)分塊并排列，以外接圓的方式限定其搜索范圍。2022-3-41612121212遞歸生長算法遞歸生長算法3332022-3-4171 1、三角網(wǎng)生長算法、三角網(wǎng)生長算法l 該算法的基本思路該算法的基本思路: :首先找到包含數(shù)據(jù)區(qū)域的最小凸多邊首先找到包含數(shù)據(jù)區(qū)域的最小凸多邊形，并從該多邊形開始從外向里逐層形成三角形格網(wǎng)。形，并從該多邊形開始從外向里逐層形成三角形格網(wǎng)。l 平面點平面點凸閉包凸閉包的定義是包含這些平面點的最小多邊形。的定義是包含這些平面點的最小多邊形。l 在凸閉包中

15、，連接任意兩點的線段必須完全位于多邊形在凸閉包中，連接任意兩點的線段必須完全位于多邊形內(nèi)。凸閉包是數(shù)據(jù)點的自然極限邊界，相當于包圍數(shù)據(jù)內(nèi)。凸閉包是數(shù)據(jù)點的自然極限邊界，相當于包圍數(shù)據(jù)點的最短路徑。點的最短路徑。l 凸閉包是數(shù)據(jù)集標準凸閉包是數(shù)據(jù)集標準DelaunayDelaunay三角網(wǎng)的一部分。計算凸三角網(wǎng)的一部分。計算凸閉包是該算法的核心。閉包是該算法的核心。2 2）凸閉包收縮法）凸閉包收縮法2022-3-4181 1）計算凸閉包的四個頂點；）計算凸閉包的四個頂點；2 2）以此四點作為基點，通過邊右邊最大偏移量搜索其他凸）以此四點作為基點，通過邊右邊最大偏移量搜索其他凸閉包頂點閉包頂點。計

16、算凸閉包的思路（計算凸閉包的思路（P79P79）：）：2022-3-4191 1）將凸多邊形按逆時針保存記錄，以左下角點附近的頂點作為）將凸多邊形按逆時針保存記錄，以左下角點附近的頂點作為起點；起點；2 2）確定第一條基邊；）確定第一條基邊；3 3）構(gòu)建第一個）構(gòu)建第一個DelaunayDelaunay三角形；三角形；4 4）重復）重復(3)(3)形成第一層形成第一層DelaunayDelaunay三角形；三角形；5 5）重新確定起點，重復）重新確定起點，重復(2)(4)(2)(4)完成整個區(qū)域的三角網(wǎng)構(gòu)建。完成整個區(qū)域的三角網(wǎng)構(gòu)建。構(gòu)建三角網(wǎng)的具體算法構(gòu)建三角網(wǎng)的具體算法2022-3-420

17、2 2、逐點插入算法、逐點插入算法 ： 1 1）定義包含所有數(shù)據(jù)點的最小外界矩形范圍，并以此作）定義包含所有數(shù)據(jù)點的最小外界矩形范圍，并以此作為最簡單的凸閉包。為最簡單的凸閉包。 2 2）按一定規(guī)則將數(shù)據(jù)區(qū)域的矩形范圍進行格網(wǎng)劃分（如）按一定規(guī)則將數(shù)據(jù)區(qū)域的矩形范圍進行格網(wǎng)劃分（如限定每個格網(wǎng)單元的數(shù)據(jù)點數(shù)）。限定每個格網(wǎng)單元的數(shù)據(jù)點數(shù)）。 3 3）剖分數(shù)據(jù)區(qū)域的凸閉包形成兩個超三角形，所有數(shù)據(jù)）剖分數(shù)據(jù)區(qū)域的凸閉包形成兩個超三角形，所有數(shù)據(jù)點都一定在這兩個三角形范圍內(nèi)。點都一定在這兩個三角形范圍內(nèi)。 4 4）對所有數(shù)據(jù)點進行循環(huán)，作如下工作（設當前處理的）對所有數(shù)據(jù)點進行循環(huán)，作如下工作（設

18、當前處理的數(shù)據(jù)點為數(shù)據(jù)點為P P）：）：搜尋包含點P的三角形，將P與此三角形三個頂點相連，形成三個三角形；由里到外優(yōu)化整個三角網(wǎng)；重復以上過程直到所有點處理完畢；刪除所有包含一個或多個超三角形頂點的三角形。 5 5）處理外圍三角形。）處理外圍三角形。2022-3-421逐點插入算法逐點插入算法2022-3-4223 3、分割合并算法、分割合并算法 分割合并算法的思想很簡單，首先將數(shù)據(jù)點分割分割合并算法的思想很簡單，首先將數(shù)據(jù)點分割成易于進行三角化的子集，然后對每個子集進行三成易于進行三角化的子集，然后對每個子集進行三角剖分，并用角剖分，并用LOPLOP算法保證三角剖分為算法保證三角剖分為DelaunayDelaunay三三角網(wǎng)。當每個子集剖分完成后，對每個子集的三角角網(wǎng)。當每個子集剖分完成后，對每個子集的三角剖分進行合并，形成最終的整體三角網(wǎng)。剖分進行合并，形成最終的整體三角網(wǎng)。 2022-3-423分割合并算法分割合并算法2022-3-4243 基于等高線數(shù)據(jù)的基于等高線數(shù)據(jù)的TIN的建立的建立 等高線離散點直接生成等高線離散點直接生成TINTIN； 將等高線作為特征線的方法；將等高線作為特征線的方法； 自動增加特征點及優(yōu)化自動增加特征點及優(yōu)化TINTIN的方法。的方法。202