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 不規則三角網不規則三角網（Triangulated Irregular Network Triangulated Irregular Network 簡稱簡稱TINTIN）：是用一系列互不交叉、互不重疊的連接在一：是用一系列互不交叉、互不重疊的連接在一起的三角形來表示地形表面。起的三角形來表示地形表面。TINTIN既是矢量

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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