1、 地面三維空間數據獲取方法 數字地形建模方法 野外獲取方法：1. 點方式： 天文測量、大地測量、工程測量、礦井測量、GPS技術、鉆孔勘探、物理勘探技術2. 面方式：攝影測量、遙感技術、激光掃描技術、集成傳感技術 3. 體方式：CT掃描、3D地震技術室內獲取方式：1.點方式：坐標量算、手扶數字化2.面方式：掃描數字化 1. 2D(x,y)： 天文測量、大地測量、工程測量、地圖數字化、遙感2. 地表3D(x,y,z) 與地上3D(x,y,z) ：大地測量、工程測量、 GPS技術、地圖數字化、攝影測量、激光掃描技術 、SAR/InSAR、集成傳感技術、 CT掃描 3. 地下3D(x,y,z) ：礦井

2、測量、鉆孔勘探、物理勘探技術、CT掃描、3D地震技術地形圖覆蓋面廣，可獲取性強現勢性存儲介質精度：比例尺、綜合程度地形圖地形曲面幾何特征DEM數據采樣策略與采樣方法采樣的布點原則合成孔徑雷達干涉測量數據采集方法機載激光掃描數據采集基于聲波、超聲波的DEM數據采集實例地形圖數據獲取 已有數據：地形地質圖（mapgis工程，里面包含等高線線數據，線數據里面不包含屬性值） 步驟 1. 給等高線加屬性數據2. 打開“MapGIS 6.7”“圖形處理”“輸入編輯”，打開工程，將等高線另存為”等高線.wl”，同時把圖上非等高線的元素刪除；3. 提取等高線上的點：打開“MapGIS 6.7”“空間分析”“D

3、TM分析”，“文件”“打開數據文件”“線數據文件”，打開”等高線.wl”文件。如果區域內看不到圖，鼠標右鍵選擇“復位窗口”；6. 再打開主菜單“圖形處理”“輸入編輯”，打開“抽稀點.wt”，刪除多余的圖元，保存；7. 打開主菜單“圖形處理”“文件轉換”，“文件”“裝入點”，如果區域內看不到圖，鼠標右鍵選擇“復位窗口”；8. “輸出”“輸出MAPGIS明碼格式”，保存為“抽稀點.wat”；10.打開主菜單“庫管理”“屬性庫管理”， “文件“導出”，在打開的對話框中，內部數據打開“抽稀點.wt”，數據源選擇“Excel file”，點擊旁邊的“+”，“用戶DSN”，選擇“Excel file”，點

4、擊“配置”，選擇工作簿，打開已有的excel文件，兩次“確定”后，輸入表格名稱“高程”，點擊“導出”；地下地下地表地表地上 DEM，(Digital Elevation Models)，是國家基礎，是國家基礎空間數據的重要組成部分，它表示地表區域上地空間數據的重要組成部分，它表示地表區域上地形的形的三維向量三維向量的的有限有限序列，即地表單元上序列，即地表單元上高程的高程的集合集合，數學表達為：，數學表達為：z=f(x，y)。 DTM：當：當z為其它二維表面上為其它二維表面上連續變化連續變化的的地理特地理特征征，如地面溫度、降雨、地球磁力、重力、土地，如地面溫度、降雨、地球磁力、重力、土地利用

5、、土壤類型等其他地面諸特征，此時的利用、土壤類型等其他地面諸特征，此時的DEM成為成為DTM(Digital Terrain Models)。數字高程模型數字高程模型( (Digital Elevation Digital Elevation ModelModel，DEMDEM) )：研究地面起伏。：研究地面起伏。數字地形模型數字地形模型( (Digital Terrain Digital Terrain ModelModel，DTMDTM) )：含有地面起伏和屬：含有地面起伏和屬性性( (如坡度、坡向等如坡度、坡向等) )等含義，是等含義，是DEMDEM的的進一步分析。進一步分析。1.物理模

6、擬：沙盤模型、橡皮模型2.數字模擬 1）數學描述：全局函數、傅里葉級數、多項式函數；局部函數、規則分塊函數、非規則分塊函數2）圖形描述 點方式：TIN、Grid、特征點線方式：等高線、特征線、剖面線面方式：影像、透視圖地面DTM從散點到地形統計表面 地形的空間分布特征 分片模擬 各向異性 自相似性 數學特征 分片的曲面模型 單值性 連續而不光滑DEM質量評價標準 保凸性 逼近面與實際曲面的波動次數相等或接近，而且兩者對應的脊線、谷線位置和走向基本一致，這保凸性好，反之保凸差； 逼真性 逼近面和實際地形曲面對應點之間滿足關系式： 光滑性 光滑性和平順性DEM建立的一般步驟與方法 采用合適的空間模

7、型構造空間結構； 采用合適的屬性域函數； 在空間結構中進行采樣，構造空間域函數； 有限性，可計算性 利用空間域函數進行分析規則DEM建立的基本思路DEM內插方法根據參考點上的高程求出其它待定點上的高程， u整體函數內插 u局部函數內插 u逐點內插法DEM內插數學模型逐點內插的步驟 定義內插點的鄰域范圍； 確定落在鄰域內的采樣點； 選定內插數學模型； 通過鄰域內的采樣點和內插計算模型計算內插點的高程?；诓灰巹t分布采樣點的DEM建立基于不規則分布采樣點的DEM建立內插函數模型1.整體內插法：趨勢面法、最小二乘法、傅里葉級數法、最小二乘樣條函數法、距離加權最小二乘法。2.局部內插法逐點內插法：移動

8、內插法、移動平均法、Voronoi圖法分塊內插法：克里格法、樣條函數法、多面函數法、線性內插法、有限元法內插函數模型采用了多個鄰近點之加權平均水平面移動擬合法內插： 基于規則格網分布采樣點的DEM建立基于規則格網分布采樣點的DEM建立基于等高線分布采樣點的DEM建立 等高線離散化法 等高線內插法 等高線構建TIN法不規則三角網TIN的基本概念TIN (Triangulated Irregular Network)不規則三角網TIN的基本元素 TIN的數據結構應包括結點的x,y,z坐標信息、邊和三角形及其拓撲關系，經典的LTL（Lawsons Triangle List）三角網表結構示例為： c

9、lass TriangleNet：public Object int NodeA;/ 三角形的頂點A的坐標索引 int NodeB;/ 三角形的頂點B的坐標索引 int NodeC;/ 三角形的頂點C的坐標索引 int AdjTriangleA;/ 三角形的頂點A的對邊相鄰的三角形 int AdjTriangleB;/ 三角形的頂點B的對邊相鄰的三角形 int AdjTriangleC;/ 三角形的頂點C的對邊相鄰的三角形 int index;/ 三角形的索引數據和TIN的類型 無約束數據域 約束數據域 無約束TIN 約束TIN 直接Delaunay三角剖分經典算法，根據其實現過程可分為 分治

10、算法 逐點插入算法 三角網生長法 1908年，G. Voronoi首先在數學上限定了每個離散點數據的有效作用范圍，定義了二維平面上的Voronoi圖；后來，A.H.Thiessen應用Voronoi圖進行了區域平均降水量研究。因此，Voronoi圖又叫泰森多邊形，由一組連續多邊形組成，多邊形的邊界由連接兩鄰點直線的垂直平分線組成。平面上的不同點，按最近鄰原則劃分平面：每個點與它的最近鄰區域相關聯。1934年，俄國數學家Delaunay提出了三角形最小內角最大的三角化準則，并證明了在沒有四點或四點以上共圓條件下的平面散亂點存在的一種三角化方式，使連成的三角形網中的三角形滿足這一條件，最接近等邊三

11、角形，通常稱這類三角形為Delaunay三角形。 圖Delaunay三角網與Voronoi圖 Delaunay三角形是由與相鄰Voronoi多邊形共享一條邊的相關點連接而成的三角形。Delaunay三角形的外接圓圓心是與三角形相關的Voronoi多邊形的一個頂點。Delaunay三角形是Voronoi圖的偶圖，簡稱D-三角形，如圖5-1所示。 研究證明，同Voronoi圖互為對偶圖的Delaunay三角剖分圖具有如下性質。 1）空外接圓性質。任何一個三角形的外接圓均不包含其它數據點； 2）最小內角最大性質。在所有可能形成的三角剖分中，Delaunay三角剖分中三角形的最小內角之和是最大的。 這

12、兩個特性保證了Delaunay三角剖分能夠盡可能地避免生成小內角的長薄單元，使三角形能夠最接近等角或等邊,這也是Delaunay三角剖分的算法依據。TIN的三角剖分準則 運用運用Delaunay 三角網的空外接圓性質三角網的空外接圓性質,對對由兩個有公共邊的三角形組成的四邊形進由兩個有公共邊的三角形組成的四邊形進行判斷，如果其中一個三角形的外接圓中行判斷，如果其中一個三角形的外接圓中含有第含有第4 個頂點個頂點,則交換由兩個三角形所構則交換由兩個三角形所構成的四邊形的對角線。這一調整過程稱為成的四邊形的對角線。這一調整過程稱為局部優化過程局部優化過程(LOP) 。 局部優化過程主要應用于不規則

13、三角網局部優化過程主要應用于不規則三角網TIN建立過程中，生成建立過程中，生成Delaunay三角形時判斷三角形時判斷其是否符合其是否符合Delaunay的空圓特性，如不符的空圓特性，如不符合，則通過合，則通過LOP局部優化過程進行優化。局部優化過程進行優化。 其基本思想：運用其基本思想：運用Delaunay-TIN三角網的三角網的空外接圓性質對兩個公共邊的三角形組成空外接圓性質對兩個公共邊的三角形組成的四邊形進行判斷，如果其中一個三角形的四邊形進行判斷，如果其中一個三角形的外接圓中含有第四點，則交換四邊形的的外接圓中含有第四點，則交換四邊形的對角線。對角線。 局部優化過程，local opt

14、imal procedure ，LOP 熱點應用熱點應用-三角網數字地面模型快速構建算法研究三角網數字地面模型快速構建算法研究 LOP局部優化過程是基于具有公共邊的兩個三角形進行局部優化過程是基于具有公共邊的兩個三角形進行的，對每個三角形進行的，對每個三角形進行LOP時，要快速找出與處理三角時，要快速找出與處理三角形共邊的三角形，雖說可以通過拓撲關系快速找出共邊形共邊的三角形，雖說可以通過拓撲關系快速找出共邊的三角形，但由于逐點插入算法是一個動態過程，因而的三角形，但由于逐點插入算法是一個動態過程，因而如何在動態過程中創建和維護拓撲關系，直接影響到算如何在動態過程中創建和維護拓撲關系，直接影響

15、到算法的執行效率。法的執行效率。 對每一次對每一次LOP過程都需要進行空外接圓檢測，該過程在過程都需要進行空外接圓檢測，該過程在整個算法過程中的執行頻率極高，故空外接圓檢測方法整個算法過程中的執行頻率極高，故空外接圓檢測方法的好壞對程序效率影響很大?？胀饨訄A檢測過程是一個的好壞對程序效率影響很大?？胀饨訄A檢測過程是一個數值分析與計算過程，因而成在計算穩定可靠的前提下數值分析與計算過程，因而成在計算穩定可靠的前提下，盡量減少計算次數和較費時的函數計算，從而提高執，盡量減少計算次數和較費時的函數計算，從而提高執行效率。行效率。 在在Delaunay三角形中，每一個三角形都要經過空外接圓三角形中，每

16、一個三角形都要經過空外接圓檢測。在算法中，這一過程是恒定的，它具有累計性。檢測。在算法中，這一過程是恒定的，它具有累計性。當數據較大，它在整個程序執行中所占用的當數據較大，它在整個程序執行中所占用的CPU時間不時間不容忽視。目前常見的做法是計算分裂三角形的外接圓圓容忽視。目前常見的做法是計算分裂三角形的外接圓圓心及半徑，然后利用第四頂點到圓心距離和外接圓的半心及半徑，然后利用第四頂點到圓心距離和外接圓的半徑關系進行判定。這一過程中要多次執行三角函數、開徑關系進行判定。這一過程中要多次執行三角函數、開方、除法、平方等運算，而這些函數與加減乘除的執行方、除法、平方等運算，而這些函數與加減乘除的執行

17、效率相比，則是比較低的。因此有必要在保證計算精度效率相比，則是比較低的。因此有必要在保證計算精度和穩定性購前提下，簡化處理空外接圓檢測公式。和穩定性購前提下，簡化處理空外接圓檢測公式。 通過公式簡化，可使得其時間復雜度相應的減少，從而通過公式簡化，可使得其時間復雜度相應的減少，從而提高了執行效率。當數據量比較大時，整體算法與點數提高了執行效率。當數據量比較大時，整體算法與點數幾乎是線性的，即具有幾乎是線性的，即具有O（N）的復雜度，仍有研究空間）的復雜度，仍有研究空間。 三角網生長算法三角網生長算法 三角網生長算法就是從一個三角網生長算法就是從一個“源源”開始，逐步形成覆蓋整個開始，逐步形成覆

18、蓋整個數據區域的三角網。數據區域的三角網。 從生長過程角度，三角網生長算法分為收縮生長算法和擴從生長過程角度，三角網生長算法分為收縮生長算法和擴張生長算法兩類。張生長算法兩類。 收縮生長算法是先形成整個數據域的數據邊界（凸殼），收縮生長算法是先形成整個數據域的數據邊界（凸殼），并以此作為源頭，逐步縮小以形成整個三角網。并以此作為源頭，逐步縮小以形成整個三角網。 擴張生長算法與收縮算法過程剛好相反，是從一個三角形擴張生長算法與收縮算法過程剛好相反，是從一個三角形開始向外層層擴展，形成覆蓋整個區域的三角網。開始向外層層擴展，形成覆蓋整個區域的三角網。 三角網生長算法三角網生長算法-遞歸生長算法遞歸

19、生長算法 在數據集中任取一點，查找距離此點最近的點，在數據集中任取一點，查找距離此點最近的點，相連后作為初始基線；相連后作為初始基線； 在初始基線右邊應用在初始基線右邊應用Delaunay法則搜索第三點法則搜索第三點； 生成生成Delaunay三角形，并以該三角形的兩條新三角形，并以該三角形的兩條新邊作為新的基線；邊作為新的基線； 重復前面過程直至所有基線處理完畢；重復前面過程直至所有基線處理完畢； 三角網生長算法三角網生長算法-遞歸遞歸生長算法生長算法 這種算法大量的時間花這種算法大量的時間花費在符合要求的鄰域點費在符合要求的鄰域點的搜索方面，為了減少的搜索方面，為了減少搜索時間，許多學者提

20、搜索時間，許多學者提出了許多不同的方法，出了許多不同的方法，如將數據分塊并排列，如將數據分塊并排列，以外接圓的方式限定其以外接圓的方式限定其搜索范圍。搜索范圍。 三角網生長算法三角網生長算法-凸閉包收縮法凸閉包收縮法 該算法的基本思路該算法的基本思路:首先找到包含數據區域的最小凸首先找到包含數據區域的最小凸多邊形，并從該多邊形開始從外向里逐層形成三角多邊形，并從該多邊形開始從外向里逐層形成三角形格網。形格網。 平面點凸閉包的定義是包含這些平面點的最小多邊平面點凸閉包的定義是包含這些平面點的最小多邊形。形。 在凸閉包中，連接任意兩點的線段必須完全位于多在凸閉包中，連接任意兩點的線段必須完全位于多

21、邊形內。凸閉包是數據點的自然極限邊界，相當于邊形內。凸閉包是數據點的自然極限邊界，相當于包圍數據點的最短路徑。包圍數據點的最短路徑。 凸閉包是數據集標準凸閉包是數據集標準Delaunay三角網的一部分。計三角網的一部分。計算凸閉包是該算法的核心。算凸閉包是該算法的核心。逐點插入算法逐點插入算法 1）定義包含所有數據點的最小外界矩形范圍，并以此作為最簡單的凸）定義包含所有數據點的最小外界矩形范圍，并以此作為最簡單的凸閉包。閉包。2）按一定規則將數據區域的矩形范圍進行格網劃分（如限定每個格網）按一定規則將數據區域的矩形范圍進行格網劃分（如限定每個格網單元的數據點數）。單元的數據點數）。3）剖分數據

22、區域的凸閉包形成兩個超三角形，所有數據點都一定在這）剖分數據區域的凸閉包形成兩個超三角形，所有數據點都一定在這兩個三角形范圍內。兩個三角形范圍內。4）對所有數據點進行循環，作如下工作（設當前處理的數據點為）對所有數據點進行循環，作如下工作（設當前處理的數據點為P）：）： 搜尋包含點P的三角形，將P與此三角形三個頂點相連，形成三個三角形； 由里到外優化整個三角網； 重復以上過程直到所有點處理完畢； 刪除所有包含一個或多個超三角形頂點的三角形。5）處理外圍三角形。）處理外圍三角形。 分治算法分治算法 把點集把點集V以橫坐標為主，縱坐標為輔按升序排序；以橫坐標為主，縱坐標為輔按升序排序； 把點集把點

23、集V分為近似相等的兩個子集分為近似相等的兩個子集VL和和VR； 在在VL和和VR中生成三角網；中生成三角網； 用用LOP算法優化所生成的三角網，使之成為算法優化所生成的三角網，使之成為Delaunay三三角網；找出連接角網；找出連接VL和和VR中兩個凸殼的底線和頂線由底線至中兩個凸殼的底線和頂線由底線至頂線合并頂線合并VL和和VR中兩個三角網；中兩個三角網； 遞歸執行步驟直至所有的所有點都已形成遞歸執行步驟直至所有的所有點都已形成Delaunay三角網。三角網。 逐點插入法雖然實現比較簡單，占用內存較小，但它的時間復雜度差，運行速度慢；從時間復雜度方面看，分治算法最好，但由于遞歸執行 ,它需要

24、較大內存空間。在較低檔的計算機平臺上，速度慢和占用大空間都是令人難以接受的。三角網生成算法的時間復雜度比較適中，并且生成的三角網形狀較好。 用VB編寫TIN的數據結構的代碼如下：Public Type TIN_Struct ID As Integer 表示該三角形的編號 F_ID As Integer 表示該三角形的第一頂點的編號S_ID As Integer 表示該三角形的第二頂點的編號T_ID As Integer 表示該三角形的第三頂點的編號FT_ID As Integer 表示該三角形的第一條邊上鄰接三角形的編號ST_ID As Integer 表示該三角形的第二條邊上鄰接三角形的編號TT_ID As Integer 表示該三角形的第三條邊上鄰接三角形的編號End Type圖