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

1、第 28卷 第 4期貴州工業(yè)大學學報 ( 自然科學版 )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基于散點及邊建立數(shù)字地面模型的研究及實現(xiàn)夏建云1 , 邸 元2( 1. 深圳市天健集團股份有限公司 ,深圳 518034; 2. 北京大學力學與工程科學系 ,北京 100871)摘 要: 對構(gòu)筑三角形網(wǎng)格建立數(shù)字地面模型進行了研

2、究 ,給出了基于散點和邊建立 三角形網(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ù)字地面 模型的應用程序 AutoD TM。關(guān)鍵詞: 數(shù)字地面模型; 三角形網(wǎng)格;計算機輔助設計; 軟件中圖分類號: P221; P236 文獻標識碼: A0 前 言數(shù)字地面模型是以數(shù)字的形式按一定的結(jié)構(gòu)組織在一起、從離散數(shù)據(jù)結(jié)構(gòu)出發(fā)構(gòu)造相互 連接的網(wǎng)絡結(jié)構(gòu) ,表示實際地形特征的空間分布 ,從而建立起相關(guān)區(qū)域內(nèi)平面坐標與高程間的 映射關(guān)系。通過數(shù)字地面模型 ,可

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

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

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

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

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

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

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

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

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

12、/ 指向下一個邊的指針;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òu)網(wǎng)算法可知 ,提高三角形、線段、點三種實體間拓撲關(guān)系的查詢 效率 ,減少形成三角形時對點的判斷次數(shù) ,可以顯著提高構(gòu)網(wǎng)算法的速度。例

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

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

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

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

17、o CAD R14 fo r Window s95環(huán)境下開發(fā)研制建立數(shù)字地面模型的應用程序 ,既利用了 Aut oCAD 強大的圖形功能 ,又利用了第 4期夏建云等: 基于散點及邊建立數(shù)字地面模型的研究及實現(xiàn) 21以 C+ + 為基礎面向?qū)ο蟮拈_發(fā)環(huán)境和 Window s95所具有的豐富資源 ,便于所開發(fā)程序的維護 、更新及與最先進的軟件技術(shù)同步發(fā)展。參 考 文 獻 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 .北京: 清華大學出版社 , 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.