一種三角網(wǎng)邊界提取的方法

1、測繪科學(xué)sc ience of su rveying and m app ingvo l134 supp lo c t1第 34卷增刊2009年 10月一種三角網(wǎng)邊界提取的方法于慶 , 王結(jié)臣 , 陳焱明(南京大學(xué)地理信息科學(xué)系 ,南京 210093 )【摘 要 】本文針對三角網(wǎng)數(shù)據(jù) , 提出一種邊界提取的新算法 。該算法需要先建立三角形 、邊 、頂點(diǎn)兩兩之間的拓?fù)潢P(guān)系 , 而后通過遞歸方法實(shí)現(xiàn)邊界的提取 。其實(shí)現(xiàn)思路是 : 該方法使用循環(huán)過程 , 首先在邊集合中找到一條鄰接三角形數(shù)量為 1的邊 , 該邊的兩個端點(diǎn)分別作為多邊形邊界的前一點(diǎn)與當(dāng)前點(diǎn) 。然后在當(dāng)前點(diǎn)的鄰接三角形中尋找鄰接三角形數(shù)

2、量為 1的邊且該邊的兩個端點(diǎn)有且只有一點(diǎn)與當(dāng)前點(diǎn)或前一點(diǎn)重合 。端點(diǎn)中非重合端點(diǎn)作為 多邊形邊界的后續(xù)點(diǎn) , 通過遞歸方法依次尋找邊界其他后續(xù)點(diǎn) , 直到與第一點(diǎn)重合時結(jié)束此次邊界提取 。之后進(jìn)入下一次循環(huán)提取下一條邊界直至所有邊界提取完畢 。筆者通過實(shí)驗(yàn)證明了該算法的正確性與合理性 , 具有較高的計算效率且易于實(shí)現(xiàn) ?！娟P(guān)鍵詞 】邊界 ; 不規(guī)則三角網(wǎng) ; 拓?fù)?; 多邊形 ; 遞歸算法【文章編號 】1009 22307 ( 2009 ) 08 20082 203【中圖分類號 】 p208【文獻(xiàn)標(biāo)識碼 】a對此筆者設(shè)計了一種新的數(shù)據(jù)結(jié)構(gòu)以便有效的組織三角形 、邊 、頂點(diǎn)的拓?fù)潢P(guān)系 。1) 點(diǎn)

3、集以數(shù)組形式存儲 , 數(shù)組中元素記錄數(shù)據(jù)點(diǎn)的位置 、二維 x , y坐標(biāo)值 、點(diǎn)的鄰接三角形數(shù)量及所在數(shù)組中的位置 。2) 邊集以邊數(shù)組存儲 , 數(shù)組中元素記錄邊的位置 、鄰接三角形數(shù)量 、邊的使用次數(shù)以及其兩個頂點(diǎn)所在數(shù)組中的位置 。3) 三角形集以三角形數(shù)組形式存儲 , 數(shù)組中元素記錄三角形的位置 、三個頂點(diǎn)及其對邊所在數(shù)組中的位置 、三角形是否位于多邊形內(nèi) 。 上述數(shù)據(jù)結(jié)構(gòu)用 c語言描述如下 :struc t d isc re tedpo in t / /三角形頂點(diǎn)數(shù)據(jù)結(jié)構(gòu)定義1 引言對多邊形實(shí)現(xiàn)三角剖分是眾多專家 、學(xué)者的研究熱點(diǎn) , 前輩們經(jīng)過探索與研究提出了諸多算法 , 如基于邊優(yōu)

4、先的 任意多邊形最優(yōu)三角剖分法 1 、 kong切耳法 2 、基于二叉 樹思想的多邊形三角剖分法 3 、帶特征約束的散列數(shù)據(jù)的 最優(yōu)三角剖分法 4 等 。然而關(guān)注并對三角網(wǎng)中提取邊界信 息并構(gòu)建成面進(jìn)行研究的人并不多 。目前已經(jīng)提出的算法 有三角形集合的邊界生成算法 5 , 該方法只是獲取三角網(wǎng) 中邊界線段集合 , 并沒有將邊界線段按順序首尾連接生成 閉合邊界 。張獻(xiàn)穎等 6 提出的空間三角網(wǎng)格曲面的邊界提 取方法能夠?qū)崿F(xiàn)三角網(wǎng)邊界的提取 , 但該方法需要對三角 網(wǎng)中每個點(diǎn)進(jìn)行邊界點(diǎn)判斷 , 計算量過大 , 算法的執(zhí)行效 率不高 。為此 , 探索三角網(wǎng)邊界提取方法有著一定的理論 意義和實(shí)際需求

5、 ?？紤]到拓?fù)潢P(guān)系在空間數(shù)據(jù)中的重要性 , 本文設(shè)計了一種有效的數(shù)據(jù)結(jié)構(gòu)來存儲三角形 、邊 、頂點(diǎn) 兩兩之間的拓?fù)潢P(guān)系 , 而后通過遞歸方法實(shí)現(xiàn)邊界的提取 。2 數(shù)據(jù)結(jié)構(gòu)設(shè)計在數(shù)據(jù)結(jié)構(gòu)設(shè)計中用到了鄰接三角形的概念 , 點(diǎn)與邊 同三角形的鄰接關(guān)系描述如下 :設(shè) t、 e、 p 分別為三角網(wǎng)中的三角 形集合 、邊 集 合 、 點(diǎn)集合 。若 pi t, 則稱 t為 pi 的一個鄰接三角形 ; 若 ei t, 則稱 t為 ei 的一個鄰接三角形 ; 若 ei = ta tb ( ta t , tb t ) , 則稱 ei 為內(nèi)部邊 , 否則為邊界邊 。本文算法的核心是利用拓?fù)潢P(guān)系進(jìn)行多邊形邊界提取 ,

6、拓?fù)浣Y(jié)構(gòu)是明確定義空間結(jié)構(gòu)關(guān)系的一種數(shù)學(xué)方法 , 在地理信息系統(tǒng)中 , 它不但用于空間數(shù)據(jù)的編輯和組織 , 而且 在空間分析和應(yīng)用中都具有非常重要的意義 。拓?fù)鋽?shù)據(jù)清楚地反映出實(shí)體之間的邏輯結(jié)構(gòu)關(guān)系 , 而且這種拓?fù)鋽?shù)據(jù)較幾何數(shù)據(jù)有更大的穩(wěn)定性 , 即其不隨地圖投影而變化 7 。doub le x, y;/ /頂點(diǎn)的 x, y坐標(biāo)in t 3 indextrigan le;中的位置/ /鄰接三角形在三角形集合in t trin um; 3 d ispo in ts;/ /鄰接三角形數(shù)量/ /頂點(diǎn)集合struc t edgein t sta rt;in t end;/ /三角形邊數(shù)據(jù)結(jié)構(gòu)定義/

7、/邊的起點(diǎn)在數(shù)組中位置/ /邊的終點(diǎn)在數(shù)組中位置in t tricoun t; / /鄰接三角形數(shù)量boo l u sed; / /提取邊界時 , 判定邊是否使用過 3 edge s;/ /邊集合struc t triangle_ n e t / /三角形數(shù)據(jù)結(jié)構(gòu)定義in t p1;in t p2;in t p3;in t edgep1; in t edgep2; in t edgep3; 3 trin e ts;/ /頂點(diǎn) p1在數(shù)組中位置/ /頂點(diǎn) p2在數(shù)組中位置/ /頂點(diǎn) p3在數(shù)組中位置/ /頂點(diǎn) p1對應(yīng)的邊在數(shù)組中位置/ /頂點(diǎn) p2對應(yīng)的邊在數(shù)組中位置/ /頂點(diǎn) p3對應(yīng)的邊在

8、數(shù)組中位置/ /三角形集合作者簡介 : 于慶 ( 19842) , 男 , 碩 士 研究生 , 主要研究領(lǐng)域?yàn)榈乩硇畔⑾到y(tǒng) 。e2m a il: yq0451 1631com3 邊界提取算法311 生成拓?fù)潢P(guān)系在用本文算法進(jìn)行三角網(wǎng)邊界提取之前需要完成多邊形三角剖 分 及 三 角 形 、邊 、頂 點(diǎn) 之 間 的 拓 撲 關(guān) 系 的 建 立 。文獻(xiàn) 1 24 中 介 紹 了 三 角 剖 分 的 詳 細(xì) 過 程 , 這 里 不 再 敖收稿日期 : 2009 207203形集合中的位置 。這樣便建立了三角形 、邊 、點(diǎn)之間的拓織邊界數(shù)據(jù)結(jié)構(gòu) , 在邊界提取過程中建立最小外包矩形如撲關(guān)系 。312 邊

9、界提取算法三角網(wǎng)形態(tài)如圖 1 所示 , 其中內(nèi)部的邊具 有兩個鄰接三角形 , 而位于邊界的邊有且只有一個鄰接三角形 。三角網(wǎng)中邊的這個性質(zhì)對邊界提取有著至關(guān)重要的作用 。我們 在三角形邊的數(shù)據(jù)結(jié)構(gòu)中使用 tricoun t屬性記 錄邊的鄰接三角形數(shù)量 。算法的主要思路 : 該方法使用循環(huán)過程 , 首先在邊集合中找到一條鄰接三角形數(shù)量為 1 的邊 , 該邊的 兩個端點(diǎn)分別作為多邊形邊界的前一點(diǎn)與當(dāng)前點(diǎn) 。在當(dāng)前點(diǎn)的鄰接三角形中首先尋找滿足條件 tricoun t = 1 的邊且該邊的兩個端點(diǎn)有且只有一點(diǎn)與當(dāng)前點(diǎn)或前一點(diǎn)重合 。端點(diǎn)中非重合端點(diǎn)作為多邊形邊界的后續(xù)點(diǎn) , 因該邊已被使用 一次 ,

10、故改寫 u sed 成員為 true, 表明該邊的使用情況以便于減少后續(xù)判斷 , 其次通過遞歸方法依次尋找邊界其他后續(xù)點(diǎn) , 直到與第一點(diǎn)重合時結(jié)束此次邊界提取 , 之后進(jìn)入 下一次循環(huán)提取下一條邊界直至所有邊界提取完畢 。完整流程描述如下 :圖 3所示 , 將復(fù)雜的邊界包含關(guān)系判斷轉(zhuǎn)換成簡單的矩形之間的包含判斷 。我們在數(shù)據(jù)結(jié)構(gòu)中用 x_ m in, x_ m ax, y_ m in, y_m ax 記錄了整條邊界的坐標(biāo)范圍 , 其中外邊界的 x_ m in、y_ m in最小 , x_ m ax、 y_ m ax最大 。這種邊界范圍對比的 方法易于實(shí)現(xiàn) , 況且記錄 的各邊界的坐標(biāo)范圍 在

11、 很 多 g is操作中非常實(shí)用 , 例如圖層顯示時經(jīng)常根據(jù)邊界范圍與應(yīng)用程序顯示區(qū)之間的空間關(guān)系決定是否進(jìn)行邊界繪制 。4 實(shí)例與分析為測試算法的性能 , 我們進(jìn)行了一些實(shí)驗(yàn) 。測試計 算 機(jī)配 置 為 : pen tium 4 1173 g cpu , 210 g 內(nèi) 存 , 操 作 系 統(tǒng) w indow s x pp rofe ssiona l。圖 4 為 測試圖件 之 一 , 該 圖 基 本 信息如下 : 共有 2條邊界 , 節(jié)點(diǎn)總數(shù) 26個 , 剖分后生成 25 個三角形構(gòu)成三角網(wǎng) (如圖 5 ) , 對剖分后生成的三角網(wǎng)進(jìn)行 邊界提取 , 多邊形形態(tài)如圖 6 所示 , 與剖分前的

12、多邊形 形 態(tài)完全吻合 。采用本文方法進(jìn)行邊界提取過程中 , 提取時間與多 邊形節(jié)點(diǎn)數(shù)量相關(guān)與多邊形邊界數(shù)量無關(guān) 。這是由于邊界提取過程實(shí)質(zhì)是根據(jù)當(dāng)前點(diǎn)與前一點(diǎn)尋找后續(xù)點(diǎn) , 因此后續(xù)點(diǎn)越多消耗 時 間 越 長 ; 在 邊 界 提 取 過 程 中 采 用 循 環(huán) 過 程 ,每循環(huán)一次 完 成 一 條 邊 界 的 提 取 。而 在 邊 界 提 取 過 程 中 ,尋找邊界后續(xù)點(diǎn)時利用了三角網(wǎng)中三角形與邊 、三角形與頂點(diǎn) 、頂點(diǎn)和邊之間的拓?fù)潢P(guān)系 , 只需在當(dāng)前點(diǎn)鄰接三 角形中尋找滿足條件的邊 , 提取邊的節(jié)點(diǎn) , 過程簡單大大 加 快了邊界提取速度 , 況且利用本方法在從三角網(wǎng)提取邊界過程中不受邊

13、界數(shù)量影響 。5 結(jié)束語本算法利用了三角網(wǎng)中邊界邊有且只有一個鄰接三角 形的特性 , 通過設(shè)計合理的數(shù)據(jù)結(jié)構(gòu) , 在三角網(wǎng)生成過 程 中建立三角形 、邊 、頂點(diǎn)之間的拓?fù)潢P(guān)系 , 直接遍歷三 角 網(wǎng)邊界集合中各邊的鄰接屬性 , 采用遞歸方法完成了邊界 點(diǎn)的排序 、實(shí)現(xiàn)了邊界線的提取 , 并解決了復(fù)雜多邊形 中 內(nèi)邊界與外邊界的判斷 。通過實(shí)驗(yàn)證明該方法穩(wěn)定性強(qiáng)并 易于實(shí)現(xiàn) , 可應(yīng)用于從不規(guī)則三角網(wǎng)的數(shù)字地面模型中快 速獲取地物輪廓線信息 , 同時也為三角網(wǎng)邊界提取提供了 一種思路和途徑 。參考文獻(xiàn)圖 1 三角網(wǎng)形態(tài)初始化 , 對三角網(wǎng)邊界集合數(shù)組 edge s進(jìn)行初始化 , 將u sed屬性

14、設(shè)為 fa lse。循環(huán)過程 , 遍歷 三 角 網(wǎng) 的 邊 集 合 , 找 到 一 條 tricoun t屬性值為 1的任意邊 , 判斷其端點(diǎn)鄰接三角形數(shù)量 , 若為 1則作為當(dāng)前點(diǎn) , 另一端點(diǎn)作為前一點(diǎn) , 通過當(dāng)前點(diǎn)尋找后續(xù)點(diǎn) 。1) 遍歷當(dāng)前點(diǎn)的所有鄰接三角形 , 找到滿足如下條件的邊 。鄰接三角形數(shù)量為 1; 在多邊形邊界提取過程中該 邊未被使用過 , 即 u sed屬性值為 fa lse; 與前一點(diǎn)和當(dāng)前點(diǎn)構(gòu)成的邊有且只有 1個交點(diǎn) 。2) 將該邊中不與當(dāng)前點(diǎn)重合的一端設(shè)為后續(xù)點(diǎn) , 重新設(shè)置前一點(diǎn)與當(dāng)前點(diǎn) , 令前一點(diǎn)指向當(dāng)前點(diǎn) 、當(dāng)前點(diǎn)指向 后續(xù)點(diǎn) , 并將該邊的 u sed屬

15、性設(shè)置為 true。如閉合則轉(zhuǎn)入步驟 3 ) , 否則轉(zhuǎn)入步驟 1 ) 。3) 保存追蹤所得的結(jié)果邊界 , 必要時進(jìn)行邊界數(shù)據(jù)壓 縮等后處理 。此次循環(huán)結(jié)束 , 轉(zhuǎn)入下一次循環(huán) 。輸出追蹤結(jié)果的邊界集合 , 過程結(jié)束 。313 多邊形構(gòu)建復(fù)雜多邊形通常包含 “洞 ”, 其形態(tài)如圖 2所示 。要完 成該類多邊形的建立首先要判定邊界之間的包含關(guān)系 , 確定多邊形的外邊界與 “洞 ”。 1 翟仁健 , 武芳 , 薛本新 1 基于邊優(yōu)先的任意多邊形最 優(yōu) 三 角 剖 分 j . 測 繪 科 學(xué) , 2008, 33 ( 1 ) :12221251x ian shu kong, h1eve re tt,

16、 godfried tou ssa in t1the graham scan triangu la te s simp le po lygon s j . pa tte rn r ecogn ition l e tte rs, 1990 , 11 ( 11 ) : 713 27161劉強(qiáng) , 李德仁 1 基于二叉樹思想的任意多邊形三角剖分遞歸算法 j . 武漢大學(xué)學(xué)報 (信息科 學(xué)版 ) ,2002 , 27 ( 5 ) : 52825331(下轉(zhuǎn)第 88頁 ) 2 3 88測繪科學(xué)第 34卷m e sse rli b , and ive s j d1moun ta in s of the w

17、o r1da 3 globa lp rio rity m .the pa rthenon pub lish inggroup1n ew yo rk andlondon, 19971p rice m f, and n b u tt ( ed s1 ) fo re sts in su sta inab le moun ta in deve lopm en t repo rt fo r 2000 r . cab in te r2 na tiona l, w a lling2fo rd, u k: 4291南京大學(xué) , 等 1 地理學(xué)詞典 m . 北京 : 商務(wù)印書館 , 19821肖克 非 1 中

18、國 山 區(qū) 經(jīng) 濟(jì) 學(xué) m . 北 京 : 大 地 出 版社 , 19881徐樵利 , 譚傳鳳 1 山地地理系統(tǒng)綜論 m . 南京 :華中師范大學(xué)出版社 , 19941程鴻 1 我國山地資源的開發(fā) j . 山地研究 (現(xiàn) 山地學(xué)報 ) , 1983, 1 ( 2) : 1271趙 松 喬 1 我 國 山 地 環(huán) 境 的 自 然 特 點(diǎn) 及 其 開 發(fā) 利 用 j . 山地研究 (現(xiàn)山地學(xué)報 ) , 1983 , 1 ( 3 ) : 1291周啟鳴 , 劉學(xué)軍 1數(shù)字地形分析 m . 北京 : 科學(xué)出版社 , 2006: 59 2601湯國安 , 楊昕 1a rcg is地理信息系統(tǒng)空間分析試驗(yàn)

19、教程 m . 北京 :科學(xué)出版社 , 2006: 3452346湯國安 , 陳正江 , 趙牡丹 , 等 1a rcv iew地理信息系統(tǒng) 空 間 分 析 方 法 m . 北 京 : 科 學(xué) 出 版 社 ,2005: 1691陳加 兵 , 勵惠國 , 鄭達(dá)賢 , 等 1 基于 d em 的 福 建省小流域 劃 分 研 究 j . 地 球 信 息 科 學(xué) , 2007, 9( 2 ) : 74 2951 4 5 6 7 5 結(jié)束語山地的準(zhǔn)確定義 、山地范圍的界定 、山地的精確分類一 直以來都是山地科學(xué)研究的一個難點(diǎn) 。本研究在地理信息系 統(tǒng) ( g is)技術(shù)支持下 , 基于水文分析模型 , 通過

20、 d em 數(shù)據(jù)自 動提取山地相對高程的方法 , 對山地概念的定義 、山地分 類 、山地范圍的界定等等有極其重要的借鑒作用 。目前 , 該 方法是提取山地相對高程最快 , 完全擺脫了人為因素的最有 效的方法 。該方法的科學(xué)性 、合理性和能否推廣有待于對山 地本身形成機(jī)制作進(jìn)一步研究以及實(shí)地驗(yàn)證和對比分析 。參考文獻(xiàn) 8 9 10 11 12 1 祝 國 瑞 1 地 圖 學(xué) m . 武 漢 : 武 漢 大 學(xué) 出 版 社 ,2003: 42024211 13 江曉波 1中國山地范圍界定的初步意見學(xué)報 , 2008, 26 ( 2 ) : 12921361 2 j . 山地re sea rch o

21、n ca lcu la t ion of m oun ta in re la t ive e leva t ion ba sed on hydro log ica l ana ly s isa b stra c t: moun ta in re la tive e leva tion is so sign ifican t in the ea rth system sc ience1a lso, its ca lcu la tion and extrac tion is an im 2 po rtan t sub jec t abou t geograp h ic info rm a tion

22、 sc ience, moun ta in sc ience and m app ing1b a sed on g is, th is p ap e r extrac ted moun ta in re l2 a tive e leva tion u sing d em da ta by the mode l of hyd ro logica l ana lysis1r e su lts show tha t th is m e thod no t on ly can extrac t moun ta in re la2 tive e leva tion ea sily and qu ick

23、ly, bu t a lso the re su lts a re sc ien tific and rea sonab le1 it is mo re impo rtan t tha t it p rovide s a new m e thod fo r ca lcu la ting and extrac ting moun ta in re la tive e leva tion and it is extrem e ly impo rtan t fo r defin ition of moun ta in range, the defin ition,c la ssifica tion

24、and con struc tion of d igita l moun ta in1key word s: moun ta in, moun ta in re la tive e leva tion, d em , g is, hyd ro logic ana lysisx ion g b o , ch en x ue2hua , l iu yan 2feng ( in stitu te of moun ta in h aza rd s a nd environm en t, ch ine se a cadem y of sc ience s chengdu 610041 , ch ina;

25、 gradua ted u n ive rsity of ch ine se a cadem y of sc ience s, b e ijing 100041, ch ina; chengdu ca rtograp h ic pub lish ing hou se ( ccph ) chengdu 610100 , ch ina; s ichuan bu reau of su rveying and m app ing, chengdu 610041, ch ina; sichuan p rovinc ia l comm ittee of po litica l sc ience and l

26、 aw, chengdu 610041 , ch ina)(上接第 83頁 )杜丹蕾 , 陳學(xué)工 1 三角網(wǎng)中三角形集合的邊界生成算法 j . 現(xiàn) 代 計 算 機(jī) (專 業(yè) 版 ) , 2007 , 8: 18 219 , 261張獻(xiàn)穎 , 周明全 , 耿國華 1 空間三角網(wǎng)格曲面的邊 界 提 取 方 法 j . 中 國 圖 像 圖 形 學(xué) 報 , 2003, 8( 10 ) : 1223212261 6 盧朝陽 , 吳成柯 1任意多邊形內(nèi)帶特征約束的散列數(shù)據(jù)的最優(yōu)三角剖分 j . 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報 , 1997 , 9 ( 4 ) : 30223081 4 7 5 黃杏元 1地理信

27、息系統(tǒng)概論 m .出版社 , 20011北京 : 高等教育a m e thod of boun da ry ex tra c t ion for tr ian g le m e sha b stra c t: a cco rd ing to the triangu la tion da ta, the au tho r p ropo sed a new m e thod fo r bounda ry extrac tion1the p ropo sed a lgo rithm needed to bu ild the topo logica l re la tion sh ip be twee

28、n triangle s, ve rtice s and edge s, and then rea lized bounda ry extrac ting by u sing re2 cu rsion m e thod1the app roach rea lized like th is: th is m e thod u sed cyc lic p roce ss, firstly find ing an edge wh ich had on ly one ad jacency triangle in edge se t1the two extrem e po in ts of the edge we re u sed a s p reviou s and cu rren t po in t of po lygona l bounda ry1f ind