陳云

(廈門(mén)精圖信息技術(shù)有限公司 福建廈門(mén)361008）

1 引言

VCT(矢量數(shù)據(jù)交換格式)是土地利用中的一種非常重要的數(shù)據(jù)交換格式，是全國(guó)土地調(diào)查和土地利用數(shù)據(jù)庫(kù)更新的重要基礎(chǔ)。國(guó)土資源部在國(guó)家標(biāo)準(zhǔn)《地理空間數(shù)據(jù)交換格式》[1]基礎(chǔ)上制定了矢量數(shù)據(jù)交換格式VCT1.0、VCT2.0[2]和VCT3.0[3]。VCT1.0 采用未建立拓?fù)潢P(guān)系TOPO:0 的空間矢量數(shù)據(jù)交換格式[4]；VCT2.0 采用TOPO:1 的空間矢量數(shù)據(jù)交換格式，要求“面要素采用TOPO:1 方式，使用間接坐標(biāo)描述面要素，封閉邊界由線(xiàn)要素組成”；VCT3.0 中要求“面要素中的<面的特征類(lèi)型>::=100，100 表示由間接坐標(biāo)構(gòu)成的面對(duì)象”，此外VCT3.0 還要求地類(lèi)圖斑（面）、宗地（面）兩個(gè)層必須引入同一組線(xiàn)對(duì)象。

王艷東等在文獻(xiàn)[5]中闡明了《地球空間數(shù)據(jù)交換格式》CNSDTF 是一個(gè)完備的、簡(jiǎn)單的、包容性強(qiáng)的空間數(shù)據(jù)轉(zhuǎn)換標(biāo)準(zhǔn)，但并沒(méi)有給出具體如何轉(zhuǎn)換的過(guò)程；陳文玲等實(shí)現(xiàn)了基于MapObjects 組件中Shape 格式到Vct 格式的轉(zhuǎn)化[6]，并沒(méi)有涉及面間接線(xiàn)處理內(nèi)容；劉子立等實(shí)現(xiàn)基于節(jié)點(diǎn)共面的VCT3.0面間接線(xiàn)構(gòu)建算法[7]，但轉(zhuǎn)換效率相對(duì)較低；文獻(xiàn)[8]中雖然有給出多圖層處理的一些思路，但并沒(méi)有給出具體的算法。綜上所述VCT 中的面要素要求使用間接坐標(biāo)來(lái)描述,它需要按照一定的順序(順時(shí)針或者逆時(shí)針) 記錄組成該多邊形數(shù)據(jù)的線(xiàn)要素和其他一些屬性信息，針對(duì)這種情況，現(xiàn)給出了一種根據(jù)多圖層面要素的構(gòu)成線(xiàn)段構(gòu)建面要素間接線(xiàn)的快速算法。

2 最大共邊算法

2.1 算法原理

無(wú)論是TOPO:0 和TOPO:1，還是面對(duì)象必須由引用線(xiàn)對(duì)象的間接坐標(biāo)構(gòu)成，其本質(zhì)是減少數(shù)據(jù)存儲(chǔ)的冗余。所以從空間數(shù)據(jù)導(dǎo)出的間接線(xiàn)即要保證能構(gòu)成所有面要素，同時(shí)間接線(xiàn)的數(shù)量也要最少，不同間接線(xiàn)應(yīng)不重疊和不重復(fù)。為了達(dá)成這個(gè)目標(biāo)，在進(jìn)行構(gòu)建間接線(xiàn)時(shí)，需要對(duì)每個(gè)面狀要素的構(gòu)成節(jié)點(diǎn)進(jìn)行分析。按每個(gè)面的構(gòu)成節(jié)點(diǎn)順序進(jìn)行重疊判斷，根據(jù)節(jié)點(diǎn)與不同面之間的重疊及連續(xù)性判斷間接線(xiàn)的構(gòu)成。

面要素是由節(jié)點(diǎn)構(gòu)成，在VCT 矢量圖中不同的面要素之間存在重疊的節(jié)點(diǎn)，如圖1、圖2 所示。除線(xiàn)段AB 和線(xiàn)段BC，并把新共線(xiàn)段AC 的映射信息添加到地類(lèi)圖斑圖層要素1 面間接線(xiàn)信息中；類(lèi)似的，將宗地圖層要素1 的面間接線(xiàn)信息中刪除線(xiàn)段AB 和線(xiàn)段BC，并把新共線(xiàn)段AC 的映射信息添加到宗地圖層要素1 面間接線(xiàn)信息中；同時(shí)，更新共線(xiàn)段映射表，即從共線(xiàn)段映射表中刪除共線(xiàn)段AB和共線(xiàn)段BC，并添加新共線(xiàn)段AC。上述過(guò)程也是體現(xiàn)了最大共邊的思路。

圖1 地類(lèi)圖斑（DLTB）-面間接線(xiàn)示例

圖2 宗地（ZD）-面間接線(xiàn)示例

（8）在合并過(guò)程中，存在無(wú)法合并的情況：其一、圖層要素（環(huán)）面的相鄰間接線(xiàn)的共邊信息不同，例如圖1 中要素1 中的線(xiàn)段BC 和線(xiàn)段CD；其二、雖然相鄰間接線(xiàn)的共邊信息相同，但存在共邊信息中對(duì)應(yīng)的要素（環(huán)）面不存在該相鄰間接線(xiàn)，例如圖1中要素1 中的線(xiàn)段CD 和線(xiàn)段DA，其共線(xiàn)信息中的地類(lèi)圖斑圖層要素5 外環(huán)對(duì)應(yīng)的線(xiàn)段AD 和線(xiàn)段DC 并不相鄰，以及圖2 中要素1 對(duì)應(yīng)的線(xiàn)段CD 和線(xiàn)段DA 并不相鄰，還有宗地圖層要素2 對(duì)應(yīng)的線(xiàn)段AD 和線(xiàn)段DC 也不相鄰。因此，在合并過(guò)程中，引入預(yù)判過(guò)程，對(duì)符合條件的才進(jìn)行合并更新。

（9）在合并更新過(guò)程中，對(duì)于環(huán)島情況，存在方向可能不對(duì)的情況，需要特殊處理。例如：圖1 中地類(lèi)圖斑圖層要素3 中，線(xiàn)段HI 和線(xiàn)段IJ 進(jìn)行合并后，形成新的共線(xiàn)段HJ，此后，共線(xiàn)段HJ 和線(xiàn)段HJ進(jìn)行合并時(shí)，則無(wú)法判斷此環(huán)是順時(shí)針?lè)较蜻€是逆時(shí)針?lè)较?。由此，采用相鄰?jié)點(diǎn)的辦法來(lái)判斷是順時(shí)針?lè)较蜻€是逆時(shí)針?lè)较?。例如：圖1 中地類(lèi)圖斑圖層要素3 中，合并后新共線(xiàn)段為HH(HIJH)，起點(diǎn)為H，矢量化方向的下一相鄰節(jié)點(diǎn)為I，則與新共線(xiàn)段的方向相同；而地類(lèi)圖斑圖層要素5 中內(nèi)環(huán)起點(diǎn)為H，矢量化方向的下一相鄰節(jié)點(diǎn)為J，與新共線(xiàn)段不同，則方向與新共線(xiàn)段的方向相反。

（10）需要注意，針對(duì)多圖層的情況，通常存在如下情況，例如：宗地圖層要素2 的邊KA，在地類(lèi)圖斑圖層中被要素4 節(jié)點(diǎn)P 打斷，但實(shí)際宗地圖層中要素2 直接用KA 邊表示，中間并沒(méi)有節(jié)點(diǎn)P。因此針對(duì)這種情況，為了不改變宗地圖層的拓?fù)浣Y(jié)構(gòu)，對(duì)KA 邊不進(jìn)行打斷處理，此時(shí)，構(gòu)建間接線(xiàn)KA 與KP是分別獨(dú)立的間接線(xiàn)，其間接線(xiàn)信息也是不同的。上述構(gòu)建方法也是兼容這種特殊情況。

（11）在完成合并后，提出一種檢測(cè)方法，驗(yàn)證生成的面間接線(xiàn)是否正確。通過(guò)對(duì)上述圖層要素生成的面間接線(xiàn)數(shù)據(jù)CommonLineVec，通過(guò)把面間接線(xiàn)按方向首尾進(jìn)行拼接，重新形成一條完成的線(xiàn)LinePointVec，首先判斷該線(xiàn)是否封閉，如果不是，則生成的面間接線(xiàn)有誤；接著把拼接后的線(xiàn)按雙份擴(kuò)充處理成DoubleLinePointVec，例如圖1 要素1 拼接后的線(xiàn)LinePointVec 的節(jié)點(diǎn)結(jié)果如BCDAB，則線(xiàn)DoubleLinePointVec 的節(jié)點(diǎn)如BCDABCDAB，即中間去掉一個(gè)重復(fù)的拼接節(jié)點(diǎn)B；然后，通過(guò)原始節(jié)點(diǎn)數(shù)據(jù)polygonLineVec，依次遍歷DoubleLinePointVec，在DoubleLinePointVec 中找到完全匹配的子序列ABCDA，則表明面間接線(xiàn)生成成功，否則面間接線(xiàn)構(gòu)建失敗。

2.2 算法流程設(shè)計(jì)

算法總體流程如圖3 所示, 其中關(guān)鍵環(huán)節(jié)之圖層相鄰共邊合并（27）流程如圖4 所示，以及有效性檢測(cè)（30）流程如圖9 所示。在圖4 中，關(guān)鍵步驟之相鄰線(xiàn)段合并成候選共邊（27.9）流程如圖5 所示，以及關(guān)鍵步驟之預(yù)判兩個(gè)相鄰線(xiàn)段合并是否有效（27.10）的流程如圖6 所示，還有關(guān)鍵步驟之新合并共線(xiàn)段（27.11）的流程如圖7 所示。特別地，圖7 中處理環(huán)島類(lèi)型共線(xiàn)信息（27.11.10）步驟如圖8 所示。

圖3 總體流程

圖8 處理環(huán)島類(lèi)型共線(xiàn)信息流程

圖9 圖層面間接線(xiàn)檢測(cè)流程

2.3 算法實(shí)例

算法程序通過(guò)地理信息系統(tǒng)開(kāi)發(fā)平臺(tái)KingMap V6.0 進(jìn)行驗(yàn)證，平臺(tái)通過(guò)C/C++語(yǔ)言實(shí)現(xiàn)。平臺(tái)運(yùn)行環(huán)境為虛擬機(jī)：Win7 SP1 旗艦版64 位操作系統(tǒng)；DDR3 800MHz 4GB；Intel(R) Core(TM) i5-4200U @1.60GHz 2.30GHz 雙核處理器，其中虛擬機(jī)CPU 分配單核雙線(xiàn)程；硬盤(pán)50GB，5400 轉(zhuǎn)。算法程序以某鎮(zhèn)的行政區(qū)圖層和地類(lèi)圖斑圖層進(jìn)行間接線(xiàn)的構(gòu)建和導(dǎo)出，經(jīng)過(guò)驗(yàn)證導(dǎo)出的結(jié)果數(shù)據(jù)真實(shí)可靠。不同算法性能結(jié)果如表1 所示。

表1 算法性能比較

從表1 可以看出，本文算法程序經(jīng)過(guò)0.955 秒從64 個(gè)行政區(qū)和1730 個(gè)地類(lèi)圖斑中構(gòu)建4729 個(gè)間接線(xiàn)。根據(jù)對(duì)導(dǎo)出結(jié)果的驗(yàn)證，確認(rèn)導(dǎo)出數(shù)據(jù)正確且所有的間接線(xiàn)不重疊和不重復(fù)，符合VCT 的要求，如圖10 和圖11 所示。其中，最小共邊算法生成的20915 條間接線(xiàn)，通過(guò)相鄰間接線(xiàn)合并后，使得間接線(xiàn)數(shù)量最少，最終行政區(qū)和地類(lèi)圖斑兩個(gè)圖層僅需4729 條間接線(xiàn)來(lái)構(gòu)建。

圖10 地類(lèi)圖斑圖層面間接線(xiàn)結(jié)果

圖11 行政區(qū)圖層面間接線(xiàn)結(jié)果

3 結(jié)束語(yǔ)

通過(guò)面要素的共邊合并提出了一種構(gòu)建面要素間接線(xiàn)的算法，解決了多圖層面間接線(xiàn)構(gòu)建的問(wèn)題；同時(shí)，還提出了一種圖層面間接線(xiàn)有效性檢測(cè)算法。該算法已在地理信息系統(tǒng)開(kāi)發(fā)平臺(tái)KingMap V6.0上編程實(shí)現(xiàn)并進(jìn)行測(cè)試，驗(yàn)證了算法的可靠性。該算法不僅從性能得到大幅提升，同時(shí)，還解決了一些無(wú)效圖形問(wèn)題，例如：同一個(gè)面多次經(jīng)過(guò)同一個(gè)節(jié)點(diǎn)。