最大共邊算法在多圖層面間接線構(gòu)建中的應用

陳云

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

1 引言

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

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

2 最大共邊算法

2.1 算法原理

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

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

圖1 地類圖斑（DLTB）-面間接線示例

圖2 宗地（ZD）-面間接線示例

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

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

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

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

2.2 算法流程設計

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

圖3 總體流程

圖8 處理環(huán)島類型共線信息流程

圖9 圖層面間接線檢測流程

2.3 算法實例

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

表1 算法性能比較

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

圖10 地類圖斑圖層面間接線結(jié)果

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

3 結(jié)束語

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