1、DEM表示方法,數(shù)學(xué)方法,用數(shù)學(xué)方法來表達(dá)，可以采用整體擬合方法，即根據(jù)區(qū)域所有的高程點(diǎn)數(shù)據(jù)，用傅里葉級(jí)數(shù)和高次多項(xiàng)式擬合統(tǒng)一的地面高程曲面； 也可用局部擬合方法，將地表復(fù)雜表面分成正方形規(guī)劃區(qū)域或面積大致相等的不規(guī)則區(qū)域進(jìn)行分塊搜索，根據(jù)有限個(gè)點(diǎn)進(jìn)行擬合形成高程曲面,1,DEM表示方法,線模式：等高線是表示地形最常見的形式。其它的地形特征線也是表達(dá)地面高程的重要信息源，如山脊谷底線等； 點(diǎn)模式：用離散采樣數(shù)據(jù)點(diǎn)建立DEM是DEM建立常用方法之一。數(shù)據(jù)采樣可按規(guī)則格網(wǎng)采樣，可以是密度一致的或不一致的；可以是不規(guī)則采樣，如不規(guī)則三角網(wǎng)；也可以有選擇性地采樣，采集三峰、洼坑、邊界等重要特征點(diǎn)。,圖

2、形表示法,2,DEM表示方法,3,DEM主要表示模型,規(guī)則格網(wǎng)，通常是正方形，也可以是矩形、三角形等規(guī)則格網(wǎng)。規(guī)則格網(wǎng)將區(qū)域空間切分為規(guī)則的格網(wǎng)單元，每個(gè)格網(wǎng)單元對(duì)應(yīng)一個(gè)數(shù)值； 數(shù)學(xué)上可以表示為一個(gè)矩陣，在計(jì)算機(jī)實(shí)現(xiàn)中則是一個(gè)二維數(shù)組。每個(gè)格網(wǎng)單元或數(shù)組的一個(gè)元素，對(duì)應(yīng)一個(gè)高程值。,規(guī)則格網(wǎng)模型,4,DEM主要表示模型,規(guī)則格網(wǎng)的高程矩陣，可以很容易地用計(jì)算機(jī)進(jìn)行處理。它還可以很容易地計(jì)算等高線、坡度坡向、山坡陰影和自動(dòng)提取流域地形，使得它成為DEM最廣泛使用的格式； 格網(wǎng)DEM的缺點(diǎn)是不能準(zhǔn)確表示地形結(jié)構(gòu)和細(xì)部，為避免這些問題，可采用附加地形特征數(shù)據(jù)，如地形特征點(diǎn)、三脊線、谷底線、斷裂線，以

3、描述地形結(jié)構(gòu)。,5,DEM主要表示模型,格網(wǎng)DEM的另一個(gè)缺點(diǎn)是數(shù)據(jù)量過大，給數(shù)據(jù)管理帶來了不便，通常要進(jìn)行壓縮存儲(chǔ)； DEM數(shù)據(jù)的無損壓縮可以采用普通的柵格數(shù)據(jù)壓縮方式，如游程編碼、塊碼等； 但是由于DEM數(shù)據(jù)反映了地形的連續(xù)起伏變化，通常比較“破碎”，普通壓縮方式難以達(dá)到很好的效果，可以采用哈夫曼編碼。,6,DEM主要表示模型,等高線模型表示高程，高程值的集合是已知的，每一條等高線對(duì)應(yīng)一個(gè)已知的高程值，一系列等高線集合和它們的高程值一起就構(gòu)成了一種地面高程模型,等高線模型,7,DEM主要表示模型,等高線模型,等高線通常被存成一個(gè)有序的坐標(biāo)點(diǎn)對(duì)序列，可以認(rèn)為是一條帶有高程值屬性的簡單多邊形或

4、多邊形弧段； 由于等高線模型只表達(dá)了區(qū)域的部分高程值，往往需要一種插值方法來計(jì)算落在等高線外的其它點(diǎn)高程。,8,DEM主要表示模型,不規(guī)則三角網(wǎng)（Triangulated Irregular Network, TIN）,TIN模型具有三個(gè)基本要求 TIN是唯一的； 力求最佳的三角形幾何形狀，每個(gè)三角形盡量接近等邊形狀； 保證最鄰近的點(diǎn)構(gòu)成三角形，即三角形的邊長之和最小。,9,DEM主要表示模型,TIN模型根據(jù)區(qū)域有限個(gè)點(diǎn)集將區(qū)域劃分為相連的三角面網(wǎng)絡(luò)，區(qū)域中任意點(diǎn)落在三角面的頂點(diǎn)、邊上或三角形內(nèi)。如果點(diǎn)不在頂點(diǎn)上，該點(diǎn)的高程值通常通過線性插值的方法得到（在邊上用邊的兩個(gè)頂點(diǎn)高程，在三角形內(nèi)則用

5、三個(gè)頂點(diǎn)的高程）。,10,DEM主要表示模型,有許多種表達(dá)TIN拓?fù)浣Y(jié)構(gòu)的存儲(chǔ)方式，一般來講，對(duì)于每一個(gè)三角形、邊和節(jié)點(diǎn)都對(duì)應(yīng)一個(gè)記錄，三角形的記錄包括三個(gè)指向它三個(gè)邊的記錄的指針；邊的記錄有四個(gè)指針字段，包括兩個(gè)指向相鄰三角形記錄的指針和它的兩個(gè)頂點(diǎn)的記錄的指針；也可以直接對(duì)每個(gè)三角形記錄其頂點(diǎn)和相鄰三角形。,11,DEM主要表示模型,有許多種表達(dá)TIN拓?fù)浣Y(jié)構(gòu)的存儲(chǔ)方式，一般來講，對(duì)于每一個(gè)三角形、邊和節(jié)點(diǎn)都對(duì)應(yīng)一個(gè)記錄，三角形的記錄包括三個(gè)指向它三個(gè)邊的記錄的指針；邊的記錄有四個(gè)指針字段，包括兩個(gè)指向相鄰三角形記錄的指針和它的兩個(gè)頂點(diǎn)的記錄的指針；也可以直接對(duì)每個(gè)三角形記錄其頂點(diǎn)和相鄰三

6、角形。,12,DEM主要表示模型,空間數(shù)據(jù)模型通過空間數(shù)據(jù)組織和空間數(shù)據(jù)庫對(duì)空間對(duì)象及其關(guān)系進(jìn)行描述，對(duì)空間對(duì)象進(jìn)行提取?？臻g數(shù)據(jù)模型有兩種分類方法： （1）從認(rèn)知的的角度：分為基于對(duì)象（object based）的模型、基于網(wǎng)絡(luò)(network based) 的模型和基于場(chǎng)（field based）的模型； （2）從表達(dá)的方式上：分為矢量數(shù)據(jù)模型、鑲嵌數(shù)據(jù)模型和組合數(shù)據(jù)模型。,13,DEM主要表示模型,鑲嵌數(shù)據(jù)模型的基本思想是：可以用相互連接在一起的網(wǎng)絡(luò)來覆蓋和逼近空間對(duì)象。數(shù)字高程模型通常用于刻畫具有連續(xù)變化特征的空間對(duì)象，目前最典型的應(yīng)用就是通過連續(xù)網(wǎng)格單元來實(shí)現(xiàn)地形曲面的模擬，應(yīng)歸類于

7、基于場(chǎng)的鑲嵌數(shù)據(jù)模型.,14,DEM主要表示模型,當(dāng)?shù)匦螖?shù)據(jù)呈規(guī)則分布或由格網(wǎng)DEM向TIN轉(zhuǎn)換時(shí)，其三角剖分與不規(guī)則數(shù)據(jù)域的三角剖分有很大的差異。由于規(guī)則格網(wǎng)分布采樣數(shù)據(jù)的特性，對(duì)其進(jìn)行三角形剖分可以有兩類方法： （1）直接對(duì)角線連接三角化 （2）Delaunay三角剖分法,15,16,DEM主要表示模型,先來簡要了解一下與Delaunay三角網(wǎng)密切相關(guān)的Voronoi圖： Voronoi 圖又稱為Dirichlet 鑲嵌( tessellation) ，其概念由Dirichlet 于1850 年首先提出; 1907 年俄國數(shù)學(xué)家Voronoi 對(duì)此作了進(jìn)一步闡述，并提出高次方程化簡; 19

8、11年荷蘭氣候?qū)W家A.H.Thiessen為提高大面積氣象預(yù)報(bào)的準(zhǔn)確度，應(yīng)用Voronoi圖對(duì)氣象觀測(cè)站進(jìn)行了有效區(qū)域劃分。因此在二維空間中，Voronoi 圖也稱為泰森( Thiessen) 多邊形。Voronoi圖是Delaunay三角網(wǎng)的對(duì)偶，現(xiàn)在已經(jīng)成為計(jì)算幾何中的一種通用的基本幾何結(jié)構(gòu)。,Voronoi圖,17,18, 空外接圓準(zhǔn)則 Delaunay三角形外接圓內(nèi)部包含其它點(diǎn)的性質(zhì)被用作從一系列不重合的平面點(diǎn)建立Delaunay三角網(wǎng)的基本法則。Delaunay三角形由三個(gè)相鄰點(diǎn)連接組成，這三個(gè)相鄰點(diǎn)對(duì)應(yīng)的Voronoi多邊形有一個(gè)公共的頂點(diǎn)，這個(gè)頂點(diǎn)同時(shí)也是Delaunay三角形外

9、接圓的圓心。在進(jìn)行Delaunay三角形剖分的過程中，每一個(gè)三角形都要經(jīng)過空外接圓檢測(cè)，目前常用的計(jì)算方法是計(jì)算三角形外接圓的圓心和半徑，然后計(jì)算圓心和其他點(diǎn)的距離，通過距離和外接圓半徑的比較進(jìn)行判斷，這種判斷方法的計(jì)算包含了開方、除法、平方等復(fù)雜的運(yùn)算。,Delaunay三角網(wǎng),19, 最小角最大準(zhǔn)則 有很多種方法可以對(duì)三角形進(jìn)行剖分，無論怎樣進(jìn)行三角剖分，采樣點(diǎn)的高程值都是最準(zhǔn)確的。就這個(gè)層面來看，無論怎樣剖分效果差別都不大，但是就其外觀的自然性而言，還是能比較出相對(duì)較好的一種效果。,Delaunay三角網(wǎng),20,21,22,23,地形的模擬方法有多種，可以區(qū)分為物理模擬和數(shù)字模擬兩大類。

10、數(shù)字模擬又分為數(shù)學(xué)描述和圖形描述兩類，其中不規(guī)則三角網(wǎng)（TIN）、規(guī)則格網(wǎng)（Grid）和等高線地形圖是三種典型的圖形描述方法。 隨著計(jì)算機(jī)技術(shù)和計(jì)算機(jī)圖形學(xué)的發(fā)展，人們處理大量地形數(shù)據(jù)和進(jìn)行真實(shí)表達(dá)的能力得以提高，Grid和TIN因其直觀易用、更新方便而逐漸成為主流的數(shù)字地形模擬方法，本節(jié)將重點(diǎn)研究如何應(yīng)用Grid型DEM數(shù)據(jù)進(jìn)行Delaunay三角剖分。,24,D-TIN的生成算法,25,分割合并算法,分割合并算法又稱分而治之算法，Shamos和Hoey于1975年最早提出了這種算法，他們將該算法應(yīng)用到了Vorinoi圖的生成中。三年后Lewis和Robinson又將該算法應(yīng)用到了D-TIN

11、的構(gòu)建中，隨后Lee和Schachter、Dwyer等相繼對(duì)Lewis和Robinson的算法進(jìn)行了改進(jìn)，Lee和Schachter的改進(jìn)使其可以適用于無約束數(shù)據(jù)域的三角剖分，而Dwyer的改進(jìn)則能處理帶約束條件的數(shù)據(jù)。 分割合并算法的基本思想是：首先將各數(shù)據(jù)點(diǎn)分割成易于進(jìn)行三角剖分的子集，然后對(duì)各子集進(jìn)行D-TIN剖分并進(jìn)行LOP優(yōu)化，最后將各個(gè)自己建立的D-TIN進(jìn)行合并生成最終的整體三角網(wǎng)。,26,分割合并算法的基本步驟為： 第一步：把所有數(shù)據(jù)點(diǎn)的集合按升序排列。 第二步：將數(shù)據(jù)集分割成點(diǎn)個(gè)數(shù)大致相等的左右兩個(gè)子集，并對(duì)每一個(gè)子集進(jìn)行如下操作： 計(jì)算子集的凸殼 以凸殼為數(shù)據(jù)邊界，對(duì)每一個(gè)

12、子集分別進(jìn)行D-TIN三角剖分并進(jìn)行優(yōu)化 找到左右兩個(gè)子集的凸殼的底線和頂線，并由底線到頂線進(jìn)行三角網(wǎng)合并。 第三步：如果數(shù)據(jù)集中的數(shù)據(jù)個(gè)數(shù)小于給定的閾值，則直接輸出三角剖分結(jié)果。,27,三角網(wǎng)生長算法,從生長過程的角度，三角網(wǎng)生長算法分為收縮生長算法和擴(kuò)張生長算法。收縮生長算法是先形成整個(gè)數(shù)據(jù)域的數(shù)據(jù)邊界（凸殼），并以此開始逐步縮小直至形成整個(gè)三角網(wǎng)。收縮生長算法與數(shù)據(jù)點(diǎn)的分布密度有關(guān)，實(shí)際情況往往比較復(fù)雜，例如當(dāng)邊界收縮后一個(gè)完整的區(qū)域可能會(huì)分解成若干個(gè)互相獨(dú)立的子區(qū)域，這就增加了三角剖分的復(fù)雜性。擴(kuò)張生長算法與收縮算法過程剛好相反，該算法是從一個(gè)三角形開始向外層層擴(kuò)展，最終形成覆蓋整個(gè)區(qū)

13、域的三角網(wǎng),28,對(duì)在直線Ax+By+C=0的同一側(cè)的所有點(diǎn)（x，y），實(shí)數(shù)Ax+By+C的正負(fù)相同,29,主要步驟為： 第一步，生成初始三角形。在數(shù)據(jù)點(diǎn)中任取一點(diǎn)A（該點(diǎn)一般是位于數(shù)據(jù)點(diǎn)的幾何中心附近），并尋找距離此點(diǎn)最近的點(diǎn)B，兩者相連形成初始基線AB，如圖2.7所示。利用空外接圓準(zhǔn)則或張角最大準(zhǔn)則，在數(shù)據(jù)域中尋找第三點(diǎn)C，從而形成第一個(gè)Delaunay三角形ABC。,30,第二步，擴(kuò)展形成三角網(wǎng)。以初始三角形的三條邊為初始基線，利用利用空外接圓準(zhǔn)則或張角最大準(zhǔn)則尋找能與該三條初始基線形成Delaunay三角形的D、E、F點(diǎn)。 在該過程中要注意： 初始邊界將整個(gè)區(qū)域分成兩個(gè)部分，搜尋第三點(diǎn)

14、一般是在初始三角形另一個(gè)頂點(diǎn)異側(cè)范圍內(nèi)進(jìn)行。例如若初始三角形為ABC，初始邊界為AB，第三個(gè)頂點(diǎn)為C，能與三角形ABC共用AB邊的另一個(gè)三角形為ABD，D點(diǎn)要位于AB邊的另一側(cè)，而不能與C同側(cè)。,31,第三步，重復(fù)第二步直到所有的數(shù)據(jù)處理完畢。 三角網(wǎng)生長算法最早由Green和Sibson在Voronoi圖中實(shí)現(xiàn)，Brassel和Reif后來也發(fā)表了類似的算法，McCullagh和Ross通過把點(diǎn)集分塊和排序來減少搜索時(shí)間。該算法思路清晰，算法簡單，但實(shí)現(xiàn)效率不高，在該算法基礎(chǔ)上有許多改進(jìn)算法，主要集中在第三點(diǎn)的搜索和三角形全等的判定上。,32,逐點(diǎn)插入算法 從構(gòu)網(wǎng)過程來看，分割合并算法和三角

15、網(wǎng)生長算法屬于靜態(tài)剖分過程，在整個(gè)三角網(wǎng)形成過程中，新點(diǎn)的介入并不會(huì)破壞已經(jīng)形成的三角網(wǎng)。而逐點(diǎn)插入算法則是一種動(dòng)態(tài)的構(gòu)網(wǎng)過程，新點(diǎn)的插入會(huì)導(dǎo)致已有的三角網(wǎng)進(jìn)行改變。該算法最早由Lawson在1977年提出，隨后LeeSchachter(1980)、Bowyer(1981)、Watson(1981)、Sloan(1987)、Macedonio和Pareschi(1991)、Floriani和Puppo(1992)、Tsai(1993)等人先后對(duì)其進(jìn)行了改進(jìn)。逐點(diǎn)插入算法的基本過程為：,33,第一步，定義包含所有數(shù)據(jù)點(diǎn)的初始包容盒，并對(duì)該包圍盒進(jìn)行初始三角剖分。形成矩形包容盒的方法是找出數(shù)據(jù)域的坐標(biāo)極值點(diǎn)，然后用這些點(diǎn)形成包容盒。 第二步，對(duì)所有數(shù)據(jù)點(diǎn)進(jìn)行循環(huán)（設(shè)當(dāng)前處理的數(shù)據(jù)點(diǎn)為P），在已經(jīng)存在的三角網(wǎng)中，查找包含P點(diǎn)的三角形t，將P與t的三個(gè)頂點(diǎn)相連，形成t的三個(gè)初始三角剖分，再用LOP算法對(duì)初始三角剖分進(jìn)行優(yōu)化處理。 第三步是對(duì)外圍三角形進(jìn)行處理。,3