基于散點(diǎn)及邊建立數(shù)字地面模型的研究及實(shí)現(xiàn)_夏建云.pdf

1、第 28卷 第 4期貴州工業(yè)大學(xué)學(xué)報(bào) ( 自然科學(xué)版 )V ol. 28 N o. 41999 年 8 月JO U RN AL O F GU IZHO U U N IV ERSI T Y O F T ECHN O LO G YAugust. 1999( Na tural Science Editio n)文章編號: 1009-0193( 1999) 04-0017-05基于散點(diǎn)及邊建立數(shù)字地面模型的研究及實(shí)現(xiàn)夏建云1 , 邸 元2( 1. 深圳市天健集團(tuán)股份有限公司 ,深圳 518034; 2. 北京大學(xué)力學(xué)與工程科學(xué)系 ,北京 100871)摘 要: 對構(gòu)筑三角形網(wǎng)格建立數(shù)字地面模型進(jìn)行了研

2、究 ,給出了基于散點(diǎn)和邊建立 三角形網(wǎng)格模型的生成算法和數(shù)據(jù)結(jié)構(gòu) ,并根據(jù)這些理論和方法在 Auto CAD R14 fo r Window s95環(huán)境下 ,用 Microsoft Visual C / C+ + 4. 2開發(fā)研制了建立數(shù)字地面 模型的應(yīng)用程序 AutoD TM。關(guān)鍵詞: 數(shù)字地面模型; 三角形網(wǎng)格;計(jì)算機(jī)輔助設(shè)計(jì); 軟件中圖分類號: P221; P236 文獻(xiàn)標(biāo)識碼: A0 前 言數(shù)字地面模型是以數(shù)字的形式按一定的結(jié)構(gòu)組織在一起、從離散數(shù)據(jù)結(jié)構(gòu)出發(fā)構(gòu)造相互 連接的網(wǎng)絡(luò)結(jié)構(gòu) ,表示實(shí)際地形特征的空間分布 ,從而建立起相關(guān)區(qū)域內(nèi)平面坐標(biāo)與高程間的 映射關(guān)系。通過數(shù)字地面模型 ,可

3、以方便地得到有關(guān)區(qū)域內(nèi)任一點(diǎn)的地形情況 ,獲得等高線、斷 面線、坡度圖等 ,并用于計(jì)算其高程、計(jì)算區(qū)域面積和土方工程量、劃分土地、繪制流水線圖等。 因此數(shù)字地面模型廣泛地應(yīng)用于公路 CAD、城市規(guī)劃及機(jī)場、水利、軍事的地理信息系統(tǒng)中 , 其原理還將適用于水文、海洋、氣象等數(shù)據(jù)的處理。地形表面不同于一般的數(shù)學(xué)曲面 ,它在形態(tài)上較為復(fù)雜 ,無法用某一確定的數(shù)學(xué)公式來表 達(dá)和處理 ,通常情況下都采用插值法 ,根據(jù)原有離散點(diǎn)的高程來插補(bǔ)未知點(diǎn)的高程。 數(shù)字地面 模型分為規(guī)則方格形網(wǎng)模型 RSG和不規(guī)則三角形網(wǎng)格模型 T IN 兩類 ,其中特別是 Delaunay 三角形網(wǎng)格適用于各種數(shù)據(jù)分布密度 ,有

4、利于更新和直接利用各種地形特征信息 ,直接利用原 始數(shù)據(jù)、保持原有精度 ,并具有唯一性好、追蹤繪制等高線算法簡單、適應(yīng)不規(guī)則形狀區(qū)域等優(yōu) 點(diǎn) ,因而被認(rèn)為最適宜表面逼近、建立數(shù)字地面模型。 構(gòu)筑 Delaunay 三角形網(wǎng)格過程中 ,算法 和數(shù)據(jù)結(jié)構(gòu)對構(gòu)網(wǎng)速度有著重要的影響 ,本文對基于散點(diǎn)及邊建立三角形網(wǎng)格地面模型和等 高線的繪制進(jìn)行了研究 ,并且開發(fā)了相應(yīng)的應(yīng)用程序 ,使所研究的構(gòu)網(wǎng)算法和數(shù)據(jù)結(jié)構(gòu)得以實(shí) 現(xiàn)。1 數(shù)據(jù)結(jié)構(gòu)及算法給定一個(gè) d維的歐幾里得空間 Ed 和其上的 N 個(gè)點(diǎn) mi 的集 M ,那么與 M 關(guān)聯(lián)的 1階收稿日期: 1999-03-2618 貴 州 工 業(yè) 大 學(xué) 學(xué) 報(bào)

5、 (自然科學(xué)版 )1999年Vo ronoi 圖為覆蓋 Ed 的一個(gè)凸多邊形序列 V ( m1 ) , V ( m2 ) V ( mi ) V ( mN ) ,其中 V ( mi )包含了 Ed 中所有以 M 中的點(diǎn) mi 為歐幾里得距離最近點(diǎn)的點(diǎn)。于是 ,這 N 個(gè)凸多邊形將 Ed 劃分 成為一個(gè)凸網(wǎng) ,記為 Vor ( M )。V or( M)的幾何直線對偶構(gòu)成了一個(gè)新的圖 ,即在 Ed 中對 M 的一個(gè) Delaunay 三角形網(wǎng)格剖分。 可知 , Vo r( M )至多有 ( 2N - 5)個(gè)頂點(diǎn)和 ( 3N - 6)條邊。 根據(jù)自動(dòng)或半自動(dòng)攝影測量和遙感方式 ,或者其它野外測量的地面

6、數(shù)據(jù)信息 ,除了地面坐標(biāo)、高程數(shù)據(jù)之外 ,重要的地形和地物的特征信息還包括地性線、山脊線、山谷線、斷裂線等 ,這 些數(shù)據(jù)常以控制線段的形式引入不規(guī)則三角網(wǎng)地面模型的構(gòu)網(wǎng)算法中。 設(shè) S是 Ed 中點(diǎn)集 M 和線段端點(diǎn)集 L 的并 ,如果在 S形成的 Delaunay三角形網(wǎng)中的每一個(gè)三角形的外接圓范圍內(nèi) 不包含與該三角形頂點(diǎn)通視的其它點(diǎn) ,而且三角形的邊與 L中任何約束線段 Li 不相交或僅交 于端點(diǎn) ,則該三角形網(wǎng)格為 Ed 上 S由 L 約束的 Delaunay 三角形網(wǎng)。根據(jù)以上定義可以導(dǎo)出 Delaunay 三角形網(wǎng)的以下特性: 在 Delaunay 三角形網(wǎng)中任一三 角形的外接圓范圍

7、內(nèi)不會(huì)有其它點(diǎn)存在并與其通視 ,即空圓特性; 在構(gòu)網(wǎng)時(shí) ,總是選擇最鄰近 的點(diǎn)形成三角形并且不與約束線段相交;形成的三角形網(wǎng)總是具有最優(yōu)的形狀特征 ,任意兩個(gè) 相鄰三角形形成的凸四邊形的對角線如果可以互換的話 ,那么兩個(gè)三角形 6個(gè)內(nèi)角中最小的 角度不會(huì)變大 ;不論從區(qū)域何處開始構(gòu)網(wǎng) ,最終都將得到一致的結(jié)果 ,即構(gòu)網(wǎng)具有唯一性。這些特性是建立 Delaunay 三角形網(wǎng)數(shù)字地面模型算法和數(shù)據(jù)結(jié)構(gòu)的依據(jù)?；谏Ⅻc(diǎn)建立 數(shù)字地面模型 ,常采用在 d維的歐幾里得空間 Ed 中構(gòu)造 Dela unay三角形網(wǎng)的通用算法 逐 點(diǎn)插入算法 ,具體算法過程如下:1. 遍歷所有散點(diǎn) ,求出點(diǎn)集的包容盒 ,得

8、到作為點(diǎn)集凸殼的初始三角形并放入三角形鏈表。2. 將點(diǎn)集中的散點(diǎn)依次插入 ,在三角形鏈表中找出其外接圓包含插入點(diǎn)的三角形 (稱為該點(diǎn)的影響三角形 ) ,刪除影響三角形的公共邊 ,將插入點(diǎn)同影響三角形的全部頂點(diǎn)連接起來 , 從而完成一個(gè)點(diǎn)在 Delaunay 三角形鏈表中的插入。3. 根據(jù)優(yōu)化準(zhǔn)則對局部新形成的三角形進(jìn)行優(yōu)化 (如互換對角線等 )。將形成的三角形放入 Dela unay三角形鏈表。4. 循環(huán)執(zhí)行上述第 2步 ,直到所有散點(diǎn)插入完畢。上述基于散點(diǎn)的構(gòu)網(wǎng)算法理論嚴(yán)密、唯一性好 ,網(wǎng)格滿足空圓特性 ,較為理想。由其逐點(diǎn)插 入的構(gòu)網(wǎng)過程可知 ,在完成構(gòu)網(wǎng)后 ,增加新點(diǎn)時(shí) ,無需對所有的點(diǎn)

9、進(jìn)行重新構(gòu)網(wǎng) ,只需對新點(diǎn)的 影響三角形范圍進(jìn)行局部聯(lián)網(wǎng) ,且局部聯(lián)網(wǎng)的方法簡單易行。同樣 ,點(diǎn)的刪除、移動(dòng)也可快速動(dòng) 態(tài)地進(jìn)行。 但在實(shí)際應(yīng)用當(dāng)中 ,這種構(gòu)網(wǎng)算法不易引入地面的地性線和特征線 ,當(dāng)點(diǎn)集較大時(shí) 構(gòu)網(wǎng)速度也較慢 ,如果點(diǎn)集范圍是非凸區(qū)域或者存在內(nèi)環(huán) ,則會(huì)產(chǎn)生非法三角形。 為了克服基 于散點(diǎn)構(gòu)網(wǎng)算法的上述缺點(diǎn) ,特別是為了提高算法效率 ,可以對網(wǎng)格中三角形的空圓特性稍加 放松 ,亦即采用基于邊的構(gòu)網(wǎng)方法 ,其算法簡述如下:1. 根據(jù)已有的地性線和特征線 ,形成控制邊鏈表。2. 以控制邊鏈表中一線段為基邊 ,從點(diǎn)集中找出同該基邊兩端點(diǎn)距離和最小的點(diǎn) ,以該點(diǎn) 為頂點(diǎn) ,以該基邊為邊

10、 ,向外擴(kuò)展一個(gè)三角形 (僅滿足空橢圓特性 )并放入三角形鏈表。3. 按照上述第 2步 ,對控制邊鏈表所有的線段進(jìn)行循環(huán) ,分別向外擴(kuò)展。4. 依次將新形成的三角形的邊作為基邊 ,形成新的控制邊鏈表 ,按照上述第 2步 ,對控制第 4期夏建云等: 基于散點(diǎn)及邊建立數(shù)字地面模型的研究及實(shí)現(xiàn) 19邊鏈表所有的線段進(jìn)行循環(huán) ,再次向外擴(kuò)展 ,直到所有三角形不能再向外擴(kuò)展為止。 實(shí)際工程項(xiàng)目中 ,建立數(shù)字地面模型使用的數(shù)據(jù)點(diǎn)可達(dá)數(shù)百萬個(gè) ,因此在確定數(shù)據(jù)結(jié)構(gòu)和算法時(shí)要充分考慮計(jì)算機(jī)存儲容量和算法效率。 本文構(gòu)網(wǎng)算法中點(diǎn)、邊、三角形三種實(shí)體的數(shù) 據(jù)結(jié)構(gòu)如下:struct Point / / 描述散點(diǎn)的鏈

11、表ads point point;/ / 散點(diǎn)/ / 指向下一個(gè)散點(diǎn)的指針struct Point *pnex tpoint;struct Edge / / 描述邊的鏈表char ty pe;/ / 邊的類型struct Point *pfro mpoint;/ / 指向邊起點(diǎn)的指針struct Point *ptopoint;/ / 指向邊終點(diǎn)的指針struct Triang le *plefttriang le;/ / 指向邊左測三角形的指針struct Triang le *prighttriang le;/ / 指向邊右測三角形的指針struct Edge *pnex tedge;/

12、/ 指向下一個(gè)邊的指針;struct Triang le / / 描述三角形的鏈表char ty pe;/ / 三角形的類型struct Edge *pedg e1;/ / 指向三角形第一條邊的指針struct Edge *pedg e2;/ / 指向三角形第二條邊的指針struct Edge *pedg e3;/ / 指向三角形第三條邊的指針struct Triang le *pnex ttria ngle;/ / 指向下一個(gè)三角形的指針;由前述基于散點(diǎn)和邊的構(gòu)網(wǎng)算法可知 ,提高三角形、線段、點(diǎn)三種實(shí)體間拓?fù)潢P(guān)系的查詢 效率 ,減少形成三角形時(shí)對點(diǎn)的判斷次數(shù) ,可以顯著提高構(gòu)網(wǎng)算法的速度。例

13、如 ,基于邊的構(gòu)網(wǎng) 算法中 ,從點(diǎn)集中找出同某一基邊兩端點(diǎn)距離和最小的點(diǎn)的這一過程 ,并不需要對點(diǎn)集中所有 的點(diǎn)進(jìn)行判斷 ,僅對那些位于基邊附近的點(diǎn)進(jìn)行判斷就可以了。 在本文核心算法實(shí)現(xiàn)中 ,將整 個(gè)點(diǎn)集所在的范圍劃分成為若干區(qū)域 ,位于該區(qū)域內(nèi)的點(diǎn)以鏈表形式連接在一起 ,這些區(qū)域則 以一個(gè)二維數(shù)組來索引:struct Point m n / /m*n個(gè)區(qū)域內(nèi)的散點(diǎn)鏈表數(shù)組2 等值線的繪制建立了數(shù)字地面模型之后 ,就可以進(jìn)行等值點(diǎn)的追蹤和等高線的繪制。設(shè)欲繪制的等高線 的高程為 z,對數(shù)字地面模型三角形鏈表中的每個(gè)三角形的三個(gè)邊進(jìn)行循環(huán) ,由 z 的值進(jìn)行 判別:z = ( z - z1 )

14、( z - z2 )20 貴 州 工 業(yè) 大 學(xué) 學(xué) 報(bào) (自然科學(xué)版 )1999年其中 , z1、z 2 分別是三角形一條邊兩個(gè)端點(diǎn)的高程 ,兩個(gè)端點(diǎn)的平面位置設(shè)為 ( x 1、 y1 )和 ( x 2、 y2 )。 如果 z> 0,則等高線不通過該三角形邊; 如果 , z = 0,則等高線正好通過該三角形 邊的端點(diǎn); 如果 z < 0,則等高線通過該三角形邊 ,由下式來計(jì)算邊上等值點(diǎn)的平面位置 ( x ,y ):x =x 1 +x2-x 1( z - z1 )z2-z1y =y1 +y2-y1( z - z 1 )z 2- z1將三角形的兩個(gè)邊上等值點(diǎn)相連接 ,便得到了通過該三

15、角形的等值線段。依次可繪制出所 有指定高程的等值線。3 實(shí)例及結(jié)束語根據(jù)以上給出的生成算法和數(shù)據(jù)結(jié)構(gòu) ,本文采用 Micro soft Visual C /C+ + 4. 2為編程語 言 ,研制了在 AutoC AD R14 fo r Window s95環(huán)境下運(yùn)行的基于散點(diǎn)和邊建立數(shù)字地面模型的 程序 Auto DTM。 Auto DTM 根據(jù)實(shí)際工程數(shù)據(jù)構(gòu)筑的實(shí)例如圖所示 ,圖 1是 Auto DTM構(gòu)筑 的一三角形網(wǎng)地面模型實(shí)例的局部圖 ,圖 2是 Auto DTM 構(gòu)筑的另一三角形網(wǎng)地面模型實(shí)例 和等值線的局部圖 ,其中淺色線條表示三角形網(wǎng)格 ,深色線條表示繪制出的等值線。圖 1 Au

16、to DTM 建立的一數(shù)字地面圖 2 Auto DTM建立的一數(shù)字地面模型模型實(shí)例局部實(shí)例和等值線局部 AutoD TM 程序的具體應(yīng)用情況表明:1. 基于邊建立數(shù)字地面模型的算法和數(shù)據(jù)結(jié)構(gòu) ,對各種數(shù)據(jù)分布適應(yīng)性強(qiáng) ,便于更新和直接利用各種地形特征信息 ,保持原有數(shù)據(jù)精度 ,并具有追蹤繪制等高線算法簡單、適應(yīng)不規(guī)則 形狀區(qū)域等優(yōu)點(diǎn)。2. 由于散點(diǎn)數(shù)據(jù)量大 ,數(shù)字地面模型技術(shù)往往受制于構(gòu)網(wǎng)速度。本文前述的基于邊建立數(shù) 字地面模型的算法和數(shù)據(jù)結(jié)構(gòu) ,構(gòu)網(wǎng)速度快 ,算法效率高 ,可滿足實(shí)際工程項(xiàng)目的需要。3. 采用 Microsoft Visual C /C+ + 4. 2為編程語言 ,在 Aut

17、o CAD R14 fo r Window s95環(huán)境下開發(fā)研制建立數(shù)字地面模型的應(yīng)用程序 ,既利用了 Aut oCAD 強(qiáng)大的圖形功能 ,又利用了第 4期夏建云等: 基于散點(diǎn)及邊建立數(shù)字地面模型的研究及實(shí)現(xiàn) 21以 C+ + 為基礎(chǔ)面向?qū)ο蟮拈_發(fā)環(huán)境和 Window s95所具有的豐富資源 ,便于所開發(fā)程序的維護(hù) 、更新及與最先進(jìn)的軟件技術(shù)同步發(fā)展。參 考 文 獻(xiàn) 1 FrancoP. Prepar ata, Michael Ian Sha mos. Co mputa tio nal Geo metr yAn Intr oduc tion M . Spring erV er lag ,198

18、5. 2 J. M ar k W ar e. A Pr ocedure fo r Automatica lly Co rr ec ting Inva lid FlatT ria ng les Occur ring in T riang u-lated Co ntour Data J. Co mpute rs & Geosciences. 1998, 24( 2): 141 151. 3 方 鐵. Auto CAD C語言高級編程 M .北京: 清華大學(xué)出版社 , 1995.Research and implementation of constructing digital terrain model using discrete points and edgesX IA Jia n-yuan1 , DI Yuan2( 1. Shenzhen To ng e Group Co.