三維地學(xué)建模與可視化-數(shù)字地形建模

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

2、測量、鉆孔勘探、物理勘探技術(shù)、CT掃描、3D地震技術(shù)覆蓋面廣，可獲取性強(qiáng)現(xiàn)勢性存儲(chǔ)介質(zhì)精度：比例尺、綜合程度地形圖地形曲面幾何特征DEM數(shù)據(jù)采樣策略與采樣方法采樣的布點(diǎn)原則合成孔徑雷達(dá)干涉測量數(shù)據(jù)采集方法 已有數(shù)據(jù)：地形地質(zhì)圖（mapgis工程，里面包含等高線線數(shù)據(jù)，線數(shù)據(jù)里面不包含屬性值） 步驟 1. 給等高線加屬性數(shù)據(jù)2. 打開“MapGIS 6.7”“圖形處理”“輸入編輯”，打開工程，將等高線另存為”等高線.wl”，同時(shí)把圖上非等高線的元素刪除；3. 提取等高線上的點(diǎn)：打開“MapGIS 6.7”“空間分析”“DTM分析”，“文件”“打開數(shù)據(jù)文件”“線數(shù)據(jù)文件”，打開”等高線.wl”文件

3、。如果區(qū)域內(nèi)看不到圖，鼠標(biāo)右鍵選擇“復(fù)位窗口”；6. 再打開主菜單“圖形處理”“輸入編輯”，打開“抽稀點(diǎn).wt”，刪除多余的圖元，保存；7. 打開主菜單“圖形處理”“文件轉(zhuǎn)換”，“文件”“裝入點(diǎn)”，如果區(qū)域內(nèi)看不到圖，鼠標(biāo)右鍵選擇“復(fù)位窗口”；8. “輸出”“輸出MAPGIS明碼格式”，保存為“抽稀點(diǎn).wat”；10.打開主菜單“庫管理”“屬性庫管理”， “文件“導(dǎo)出”，在打開的對話框中，內(nèi)部數(shù)據(jù)打開“抽稀點(diǎn).wt”，數(shù)據(jù)源選擇“Excel file”，點(diǎn)擊旁邊的“+”，“用戶DSN”，選擇“Excel file”，點(diǎn)擊“配置”，選擇工作簿，打開已有的excel文件，兩次“確定”后，輸入表格名

4、稱“高程”，點(diǎn)擊“導(dǎo)出”；地下地下地表地表地上 DEM，(Digital Elevation Models)，是國家基礎(chǔ)，是國家基礎(chǔ)空間數(shù)據(jù)的重要組成部分，它表示地表區(qū)域上地空間數(shù)據(jù)的重要組成部分，它表示地表區(qū)域上地形的形的三維向量三維向量的的有限有限序列，即地表單元上序列，即地表單元上高程的高程的集合集合，數(shù)學(xué)表達(dá)為：，數(shù)學(xué)表達(dá)為：z=f(x，y)。 DTM：當(dāng)：當(dāng)z為其它二維表面上為其它二維表面上連續(xù)變化連續(xù)變化的的地理特地理特征征，如地面溫度、降雨、地球磁力、重力、土地，如地面溫度、降雨、地球磁力、重力、土地利用、土壤類型等其他地面諸特征，此時(shí)的利用、土壤類型等其他地面諸特征，此時(shí)的DE

5、M成為成為DTM(Digital Terrain Models)。數(shù)字高程模型數(shù)字高程模型( (Digital Elevation Digital Elevation ModelModel，DEMDEM) )：研究地面起伏。：研究地面起伏。數(shù)字地形模型數(shù)字地形模型( (Digital Terrain Digital Terrain ModelModel，DTMDTM) )：含有地面起伏和屬：含有地面起伏和屬性性( (如坡度、坡向等如坡度、坡向等) )等含義，是等含義，是DEMDEM的的進(jìn)一步分析。進(jìn)一步分析。1.物理模擬：沙盤模型、橡皮模型2.數(shù)字模擬 1）數(shù)學(xué)描述：全局函數(shù)、傅里葉級數(shù)、多項(xiàng)

6、式函數(shù)；局部函數(shù)、規(guī)則分塊函數(shù)、非規(guī)則分塊函數(shù)2）圖形描述 點(diǎn)方式：TIN、Grid、特征點(diǎn)線方式：等高線、特征線、剖面線面方式：影像、透視圖地面DTM從散點(diǎn)到地形統(tǒng)計(jì)表面 地形的空間分布特征 分片模擬 各向異性 自相似性 數(shù)學(xué)特征 分片的曲面模型 單值性 連續(xù)而不光滑DEM質(zhì)量評價(jià)標(biāo)準(zhǔn) 保凸性 逼近面與實(shí)際曲面的波動(dòng)次數(shù)相等或接近，而且兩者對應(yīng)的脊線、谷線位置和走向基本一致，這保凸性好，反之保凸差； 逼真性 逼近面和實(shí)際地形曲面對應(yīng)點(diǎn)之間滿足關(guān)系式： 光滑性 光滑性和平順性DEM建立的一般步驟與方法 采用合適的空間模型構(gòu)造空間結(jié)構(gòu)； 采用合適的屬性域函數(shù)； 在空間結(jié)構(gòu)中進(jìn)行采樣，構(gòu)造空間域函

7、數(shù)； 有限性，可計(jì)算性 利用空間域函數(shù)進(jìn)行分析規(guī)則DEM建立的基本思路DEM內(nèi)插方法根據(jù)參考點(diǎn)上的高程求出其它待定點(diǎn)上的高程， u整體函數(shù)內(nèi)插 u局部函數(shù)內(nèi)插 u逐點(diǎn)內(nèi)插法DEM內(nèi)插數(shù)學(xué)模型逐點(diǎn)內(nèi)插的步驟 定義內(nèi)插點(diǎn)的鄰域范圍； 確定落在鄰域內(nèi)的采樣點(diǎn)； 選定內(nèi)插數(shù)學(xué)模型； 通過鄰域內(nèi)的采樣點(diǎn)和內(nèi)插計(jì)算模型計(jì)算內(nèi)插點(diǎn)的高程。基于不規(guī)則分布采樣點(diǎn)的DEM建立基于不規(guī)則分布采樣點(diǎn)的DEM建立內(nèi)插函數(shù)模型1.整體內(nèi)插法：趨勢面法、最小二乘法、傅里葉級數(shù)法、最小二乘樣條函數(shù)法、距離加權(quán)最小二乘法。2.局部內(nèi)插法逐點(diǎn)內(nèi)插法：移動(dòng)內(nèi)插法、移動(dòng)平均法、Voronoi圖法分塊內(nèi)插法：克里格法、樣條函數(shù)法、多面

8、函數(shù)法、線性內(nèi)插法、有限元法內(nèi)插函數(shù)模型niiniiippZpZ11采用了多個(gè)鄰近點(diǎn)之加權(quán)平均水平面移動(dòng)擬合法內(nèi)插： 基于規(guī)則格網(wǎng)分布采樣點(diǎn)的DEM建立基于規(guī)則格網(wǎng)分布采樣點(diǎn)的DEM建立基于等高線分布采樣點(diǎn)的DEM建立 等高線離散化法 等高線內(nèi)插法 等高線構(gòu)建TIN法不規(guī)則三角網(wǎng)TIN的基本概念TIN (Triangulated Irregular Network)不規(guī)則三角網(wǎng)TIN的基本元素 TIN的數(shù)據(jù)結(jié)構(gòu)應(yīng)包括結(jié)點(diǎn)的x,y,z坐標(biāo)信息、邊和三角形及其拓?fù)潢P(guān)系，經(jīng)典的LTL（Lawsons Triangle List）三角網(wǎng)表結(jié)構(gòu)示例為： class TriangleNet：public

9、Object int NodeA;/ 三角形的頂點(diǎn)A的坐標(biāo)索引 int NodeB;/ 三角形的頂點(diǎn)B的坐標(biāo)索引 int NodeC;/ 三角形的頂點(diǎn)C的坐標(biāo)索引 int AdjTriangleA;/ 三角形的頂點(diǎn)A的對邊相鄰的三角形 int AdjTriangleB;/ 三角形的頂點(diǎn)B的對邊相鄰的三角形 int AdjTriangleC;/ 三角形的頂點(diǎn)C的對邊相鄰的三角形 int index;/ 三角形的索引數(shù)據(jù)和TIN的類型 無約束數(shù)據(jù)域 約束數(shù)據(jù)域 無約束TIN 約束TIN 直接Delaunay三角剖分經(jīng)典算法，根據(jù)其實(shí)現(xiàn)過程可分為 分治算法 逐點(diǎn)插入算法 三角網(wǎng)生長法 1908年，G

10、. Voronoi首先在數(shù)學(xué)上限定了每個(gè)離散點(diǎn)數(shù)據(jù)的有效作用范圍，定義了二維平面上的Voronoi圖；后來，A.H.Thiessen應(yīng)用Voronoi圖進(jìn)行了區(qū)域平均降水量研究。因此，Voronoi圖又叫泰森多邊形，由一組連續(xù)多邊形組成，多邊形的邊界由連接兩鄰點(diǎn)直線的垂直平分線組成。平面上的不同點(diǎn)，按最近鄰原則劃分平面：每個(gè)點(diǎn)與它的最近鄰區(qū)域相關(guān)聯(lián)。1934年，俄國數(shù)學(xué)家Delaunay提出了三角形最小內(nèi)角最大的三角化準(zhǔn)則，并證明了在沒有四點(diǎn)或四點(diǎn)以上共圓條件下的平面散亂點(diǎn)存在的一種三角化方式，使連成的三角形網(wǎng)中的三角形滿足這一條件，最接近等邊三角形，通常稱這類三角形為Delaunay三角形。

11、 圖Delaunay三角網(wǎng)與Voronoi圖 Delaunay三角形是由與相鄰Voronoi多邊形共享一條邊的相關(guān)點(diǎn)連接而成的三角形。Delaunay三角形的外接圓圓心是與三角形相關(guān)的Voronoi多邊形的一個(gè)頂點(diǎn)。Delaunay三角形是Voronoi圖的偶圖，簡稱D-三角形，如圖5-1所示。 研究證明，同Voronoi圖互為對偶圖的Delaunay三角剖分圖具有如下性質(zhì)。 1）空外接圓性質(zhì)。任何一個(gè)三角形的外接圓均不包含其它數(shù)據(jù)點(diǎn)； 2）最小內(nèi)角最大性質(zhì)。在所有可能形成的三角剖分中，Delaunay三角剖分中三角形的最小內(nèi)角之和是最大的。 這兩個(gè)特性保證了Delaunay三角剖分能夠盡可能

12、地避免生成小內(nèi)角的長薄單元，使三角形能夠最接近等角或等邊,這也是Delaunay三角剖分的算法依據(jù)。TIN的三角剖分準(zhǔn)則 運(yùn)用運(yùn)用Delaunay 三角網(wǎng)的空外接圓性質(zhì)三角網(wǎng)的空外接圓性質(zhì),對對由兩個(gè)有公共邊的三角形組成的四邊形進(jìn)由兩個(gè)有公共邊的三角形組成的四邊形進(jìn)行判斷，如果其中一個(gè)三角形的外接圓中行判斷，如果其中一個(gè)三角形的外接圓中含有第含有第4 個(gè)頂點(diǎn)個(gè)頂點(diǎn),則交換由兩個(gè)三角形所構(gòu)則交換由兩個(gè)三角形所構(gòu)成的四邊形的對角線。這一調(diào)整過程稱為成的四邊形的對角線。這一調(diào)整過程稱為局部優(yōu)化過程局部優(yōu)化過程(LOP) 。 局部優(yōu)化過程主要應(yīng)用于不規(guī)則三角網(wǎng)局部優(yōu)化過程主要應(yīng)用于不規(guī)則三角網(wǎng)TIN建

13、立過程中，生成建立過程中，生成Delaunay三角形時(shí)判斷三角形時(shí)判斷其是否符合其是否符合Delaunay的空圓特性，如不符的空圓特性，如不符合，則通過合，則通過LOP局部優(yōu)化過程進(jìn)行優(yōu)化。局部優(yōu)化過程進(jìn)行優(yōu)化。 其基本思想：運(yùn)用其基本思想：運(yùn)用Delaunay-TIN三角網(wǎng)的三角網(wǎng)的空外接圓性質(zhì)對兩個(gè)公共邊的三角形組成空外接圓性質(zhì)對兩個(gè)公共邊的三角形組成的四邊形進(jìn)行判斷，如果其中一個(gè)三角形的四邊形進(jìn)行判斷，如果其中一個(gè)三角形的外接圓中含有第四點(diǎn)，則交換四邊形的的外接圓中含有第四點(diǎn)，則交換四邊形的對角線。對角線。 局部優(yōu)化過程，local optimal procedure ，LOP 熱點(diǎn)應(yīng)用

14、熱點(diǎn)應(yīng)用-三角網(wǎng)數(shù)字地面模型快速構(gòu)建算法研究三角網(wǎng)數(shù)字地面模型快速構(gòu)建算法研究 LOP局部優(yōu)化過程是基于具有公共邊的兩個(gè)三角形進(jìn)行局部優(yōu)化過程是基于具有公共邊的兩個(gè)三角形進(jìn)行的，對每個(gè)三角形進(jìn)行的，對每個(gè)三角形進(jìn)行LOP時(shí)，要快速找出與處理三角時(shí)，要快速找出與處理三角形共邊的三角形，雖說可以通過拓?fù)潢P(guān)系快速找出共邊形共邊的三角形，雖說可以通過拓?fù)潢P(guān)系快速找出共邊的三角形，但由于逐點(diǎn)插入算法是一個(gè)動(dòng)態(tài)過程，因而的三角形，但由于逐點(diǎn)插入算法是一個(gè)動(dòng)態(tài)過程，因而如何在動(dòng)態(tài)過程中創(chuàng)建和維護(hù)拓?fù)潢P(guān)系，直接影響到算如何在動(dòng)態(tài)過程中創(chuàng)建和維護(hù)拓?fù)潢P(guān)系，直接影響到算法的執(zhí)行效率。法的執(zhí)行效率。 對每一次對每一

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

16、程是恒定的，它具有累計(jì)性。檢測。在算法中，這一過程是恒定的，它具有累計(jì)性。當(dāng)數(shù)據(jù)較大，它在整個(gè)程序執(zhí)行中所占用的當(dāng)數(shù)據(jù)較大，它在整個(gè)程序執(zhí)行中所占用的CPU時(shí)間不時(shí)間不容忽視。目前常見的做法是計(jì)算分裂三角形的外接圓圓容忽視。目前常見的做法是計(jì)算分裂三角形的外接圓圓心及半徑，然后利用第四頂點(diǎn)到圓心距離和外接圓的半心及半徑，然后利用第四頂點(diǎn)到圓心距離和外接圓的半徑關(guān)系進(jìn)行判定。這一過程中要多次執(zhí)行三角函數(shù)、開徑關(guān)系進(jìn)行判定。這一過程中要多次執(zhí)行三角函數(shù)、開方、除法、平方等運(yùn)算，而這些函數(shù)與加減乘除的執(zhí)行方、除法、平方等運(yùn)算，而這些函數(shù)與加減乘除的執(zhí)行效率相比，則是比較低的。因此有必要在保證計(jì)算精度

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

18、長過程角度，三角網(wǎng)生長算法分為收縮生長算法和擴(kuò)從生長過程角度，三角網(wǎng)生長算法分為收縮生長算法和擴(kuò)張生長算法兩類。張生長算法兩類。 收縮生長算法是先形成整個(gè)數(shù)據(jù)域的數(shù)據(jù)邊界（凸殼），收縮生長算法是先形成整個(gè)數(shù)據(jù)域的數(shù)據(jù)邊界（凸殼），并以此作為源頭，逐步縮小以形成整個(gè)三角網(wǎng)。并以此作為源頭，逐步縮小以形成整個(gè)三角網(wǎng)。 擴(kuò)張生長算法與收縮算法過程剛好相反，是從一個(gè)三角形擴(kuò)張生長算法與收縮算法過程剛好相反，是從一個(gè)三角形開始向外層層擴(kuò)展，形成覆蓋整個(gè)區(qū)域的三角網(wǎng)。開始向外層層擴(kuò)展，形成覆蓋整個(gè)區(qū)域的三角網(wǎng)。 三角網(wǎng)生長算法三角網(wǎng)生長算法-遞歸生長算法遞歸生長算法 在數(shù)據(jù)集中任取一點(diǎn)，查找距離此點(diǎn)最近的

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

20、不同的方法，如將數(shù)據(jù)分塊并排列，如將數(shù)據(jù)分塊并排列，以外接圓的方式限定其以外接圓的方式限定其搜索范圍。搜索范圍。 三角網(wǎng)生長算法三角網(wǎng)生長算法-凸閉包收縮法凸閉包收縮法 該算法的基本思路該算法的基本思路:首先找到包含數(shù)據(jù)區(qū)域的最小凸首先找到包含數(shù)據(jù)區(qū)域的最小凸多邊形，并從該多邊形開始從外向里逐層形成三角多邊形，并從該多邊形開始從外向里逐層形成三角形格網(wǎng)。形格網(wǎng)。 平面點(diǎn)凸閉包的定義是包含這些平面點(diǎn)的最小多邊平面點(diǎn)凸閉包的定義是包含這些平面點(diǎn)的最小多邊形。形。 在凸閉包中，連接任意兩點(diǎn)的線段必須完全位于多在凸閉包中，連接任意兩點(diǎn)的線段必須完全位于多邊形內(nèi)。凸閉包是數(shù)據(jù)點(diǎn)的自然極限邊界，相當(dāng)于邊形

21、內(nèi)。凸閉包是數(shù)據(jù)點(diǎn)的自然極限邊界，相當(dāng)于包圍數(shù)據(jù)點(diǎn)的最短路徑。包圍數(shù)據(jù)點(diǎn)的最短路徑。 凸閉包是數(shù)據(jù)集標(biāo)準(zhǔn)凸閉包是數(shù)據(jù)集標(biāo)準(zhǔn)Delaunay三角網(wǎng)的一部分。計(jì)三角網(wǎng)的一部分。計(jì)算凸閉包是該算法的核心。算凸閉包是該算法的核心。逐點(diǎn)插入算法逐點(diǎn)插入算法 1）定義包含所有數(shù)據(jù)點(diǎn)的最小外界矩形范圍，并以此作為最簡單的凸）定義包含所有數(shù)據(jù)點(diǎn)的最小外界矩形范圍，并以此作為最簡單的凸閉包。閉包。2）按一定規(guī)則將數(shù)據(jù)區(qū)域的矩形范圍進(jìn)行格網(wǎng)劃分（如限定每個(gè)格網(wǎng)）按一定規(guī)則將數(shù)據(jù)區(qū)域的矩形范圍進(jìn)行格網(wǎng)劃分（如限定每個(gè)格網(wǎng)單元的數(shù)據(jù)點(diǎn)數(shù)）。單元的數(shù)據(jù)點(diǎn)數(shù)）。3）剖分?jǐn)?shù)據(jù)區(qū)域的凸閉包形成兩個(gè)超三角形，所有數(shù)據(jù)點(diǎn)都一定在

22、這）剖分?jǐn)?shù)據(jù)區(qū)域的凸閉包形成兩個(gè)超三角形，所有數(shù)據(jù)點(diǎn)都一定在這兩個(gè)三角形范圍內(nèi)。兩個(gè)三角形范圍內(nèi)。4）對所有數(shù)據(jù)點(diǎn)進(jìn)行循環(huán)，作如下工作（設(shè)當(dāng)前處理的數(shù)據(jù)點(diǎn)為）對所有數(shù)據(jù)點(diǎn)進(jìn)行循環(huán)，作如下工作（設(shè)當(dāng)前處理的數(shù)據(jù)點(diǎn)為P）：）： 搜尋包含點(diǎn)P的三角形，將P與此三角形三個(gè)頂點(diǎn)相連，形成三個(gè)三角形； 由里到外優(yōu)化整個(gè)三角網(wǎng)； 重復(fù)以上過程直到所有點(diǎn)處理完畢； 刪除所有包含一個(gè)或多個(gè)超三角形頂點(diǎn)的三角形。5）處理外圍三角形。）處理外圍三角形。 分治算法分治算法 把點(diǎn)集把點(diǎn)集V以橫坐標(biāo)為主，縱坐標(biāo)為輔按升序排序；以橫坐標(biāo)為主，縱坐標(biāo)為輔按升序排序； 把點(diǎn)集把點(diǎn)集V分為近似相等的兩個(gè)子集分為近似相等的兩個(gè)子集

23、VL和和VR； 在在VL和和VR中生成三角網(wǎng)；中生成三角網(wǎng)； 用用LOP算法優(yōu)化所生成的三角網(wǎng)，使之成為算法優(yōu)化所生成的三角網(wǎng)，使之成為Delaunay三三角網(wǎng)；找出連接角網(wǎng)；找出連接VL和和VR中兩個(gè)凸殼的底線和頂線由底線至中兩個(gè)凸殼的底線和頂線由底線至頂線合并頂線合并VL和和VR中兩個(gè)三角網(wǎng)；中兩個(gè)三角網(wǎng)； 遞歸執(zhí)行步驟直至所有的所有點(diǎn)都已形成遞歸執(zhí)行步驟直至所有的所有點(diǎn)都已形成Delaunay三角網(wǎng)。三角網(wǎng)。 逐點(diǎn)插入法雖然實(shí)現(xiàn)比較簡單，占用內(nèi)存較小，但它的時(shí)間復(fù)雜度差，運(yùn)行速度慢；從時(shí)間復(fù)雜度方面看，分治算法最好，但由于遞歸執(zhí)行 ,它需要較大內(nèi)存空間。在較低檔的計(jì)算機(jī)平臺(tái)上，速度慢和占用大空間都是令人難以接受的。三角網(wǎng)生成算法的時(shí)間復(fù)雜度比較適中，并且生成的三角網(wǎng)形狀較好。 用VB編寫TIN的數(shù)據(jù)結(jié)構(gòu)的代碼如下：Public Type TIN_Struct ID As Integer 表示該三角形的編號(hào) F_ID As Integer 表示該三角形的第一頂點(diǎn)的編號(hào)S_ID As Integer 表示該三角形的第二頂點(diǎn)的編號(hào)T_ID As Integer 表示該三角形的第三頂點(diǎn)的編號(hào)FT_ID As Integer 表示該三角形的第一條邊上鄰接三角形的編號(hào)ST_ID As Integer 表示該三角形的第二條邊上鄰接三角形的編號(hào)TT_ID As