陳 云

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

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

王艷東等［3］闡明了中華人民共和國國家標準《地球空間數(shù)據(jù)交換格式》是一個完備的、簡單的、包容性強的空間數(shù)據(jù)轉(zhuǎn)換標準；陳澤民［4］指出了中國矢量數(shù)據(jù)交換格式在應(yīng)用中存在的若干問題；也有學者采用線序排列算法對無序邊界進行排序［5，6］；劉小偉等［7］實現(xiàn)了VCT文件到Shape的文件轉(zhuǎn)換；費中強等［8］實現(xiàn)了從VCT到DXF的數(shù)據(jù)格式轉(zhuǎn)換；王井利等［9］實現(xiàn)了VCT矢量格式到GDB的轉(zhuǎn)換算法；鮑文東等［10］實現(xiàn)了土地利用矢量數(shù)據(jù)交換文件VCT到Map Info數(shù)據(jù)格式的轉(zhuǎn)換。但是這些研究都沒有涉及從其他格式轉(zhuǎn)換成VCT的內(nèi)容。郭勝濤等［11］采用文件緩存方式導出VCT數(shù)據(jù)；陳若塵等［12］實現(xiàn)了基于ArcGIS Engine的GIS數(shù)據(jù)格式轉(zhuǎn)換；陳文玲等［13］基于MapObjects組件實現(xiàn)了從Shape格式到VCT格式的轉(zhuǎn)換；陳紅華等［14］基于空間ETL實現(xiàn)了VCT數(shù)據(jù)交換；吳小芳等［15］基于數(shù)據(jù)引擎思想實現(xiàn)了GIS數(shù)據(jù)的集成與共享，但沒有涉及面間接線處理的內(nèi)容；劉子立等［16］實現(xiàn)了基于節(jié)點共面的VCT3.0面間接線構(gòu)建算法，但轉(zhuǎn)換效率相對較低；也有學者實現(xiàn)了基于最大共邊的轉(zhuǎn)換算法［17，18］，算法較為高效，但主要面向單圖層轉(zhuǎn)換；文獻［19］中提出了多圖層的構(gòu)建算法，但未考慮并行計算；周琛等［20］實現(xiàn)了VCT文件到Shape文件的并行轉(zhuǎn)換方法；蔣波濤等［21］采用Map Reduce方法提升性能。綜上所述，VCT中的面要素要求使用間接坐標來描述，它需要按照一定的順序（順時針或者逆時針）記錄組成該多邊形數(shù)據(jù)的線要素和一些其他屬性信息。針對這種情況，本文給出了一種根據(jù)多圖層面要素的構(gòu)成線段構(gòu)建面要素間接線的并行處理算法。

1 算法設(shè)計

1.1 最大共邊算法

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

面要素由節(jié)點構(gòu)成，在VCT矢量圖中不同的面要素之間存在重疊的節(jié)點，如圖1所示。圖1（a）中，要素1的面節(jié)點順序編號為ABCDA；要素2的面節(jié)點順序編號為ADCMLKA。圖1（b）中，要素1的面節(jié)點順序編號為ABCDA；要素2的面節(jié)點順序編號為DEFGD；要素3的面節(jié)點順序編號為HIJH；要素4的面節(jié)點順序編號KPQK；要素5的外環(huán)節(jié)點順序編號為ADGFEDCMLKQPA，內(nèi)環(huán)節(jié)點順序編號為HJIH，需要注意的是，面要素因節(jié)點D通過兩次，將被檢測為無效圖形。

圖1 宗地、地類圖斑示例Fig.1 Examples of Parcels and Land Type Patches

最大共邊算法主要過程如下：

1）將矢量圖層數(shù)據(jù)中的各節(jié)點排序去重后進行唯一編號。以圖1（a）為例，節(jié)點集為A、B、C、D、M、L、K，記為0，1，…，6。

2）將矢量圖層數(shù)據(jù)中所有線段采用首末節(jié)點編號形成坐標，利用1維線降維成0維點的方式進行處理，類似于步驟1）進行排序去重后，刪除反向線段，僅保留一個方向的線段，再進行唯一編號。以圖1（a）為例，線段集為A B、B C、C D、D A、C M、M L、L K、K A，記為1，2，…，8。

3）根據(jù)圖層線段集合中的各線段，對各要素的組成線段進行編號，由于線段方向不同，線段編號存在正負。例如，圖1（a）要素2的編號結(jié)果為?4，?3，5，6，7，8。

4）根據(jù)上述圖層線段集合中的各線段建立共線段映射表，關(guān)鍵字為線段編號，值為共邊信息，格式為“圖層要素編碼|（環(huán)）面索引號”，分隔符為“|”。例如，映射表中圖1（a）線段C D的關(guān)鍵字為3，共線信息為“1|0”和“2|0”，默認第一個面索引起始為0。

5）將矢量圖層各要素中具有相同共邊信息的相鄰線段進行合并。例如，圖1（a）中，要素1中線段A B和B C的共邊信息都是“1|0”，進行合并后生成新的合并共邊，將該共邊編號全局增1，并添加到共線段映射表。如果合并過程碰到環(huán)島類型，則轉(zhuǎn)至步驟6），否則重復執(zhí)行本步驟，直到?jīng)]有該合并的共邊。

6）針對環(huán)島類型的新共線段，根據(jù)其首節(jié)點的相鄰節(jié)點來判斷矢量化方向，并進行唯一正負編號。以圖1（b）為例，要素3中，線段H I和線段I J合并后，形成新的共線段H J。此后，共線段H J和線段H J合并時，則無法判斷此環(huán)是順時針方向還是逆時針方向，應(yīng)采用相鄰節(jié)點的方法來判斷方向。假設(shè)圖1（b）要素3中，合并后新共線段為H H［H I J H］，起點為H，矢量化方向的下一相鄰節(jié)點為I，則要素3的面間接線與新共線段的方向相同；而要素5中內(nèi)環(huán)起點為H，矢量化方向的下一相鄰節(jié)點為J，與新共線段不同，則方向與新共線段的方向相反。處理完成后，進入下個要素面進行合并，繼續(xù)執(zhí)行步驟5）。

1.2 多圖層應(yīng)用設(shè)計

最大共邊算法為了適應(yīng)多圖層處理情況，針對上述步驟進行如下擴展處理：

①在步驟1）中，利用參與的多個面圖層建立全局唯一節(jié)點集。以圖1（a）和圖1（b）為例，全局唯一節(jié)點集為A、B、C、D、E、F、G、H、I、J、K、L、M、P、Q，記為0，1，…，14。

②在步驟2）中，利用參與的多個面圖層建立全局唯一線段集。

③在步驟3）中，遍歷多個面圖層，并對要素面中的線段進行正負編號。

④在步驟4）中，對共邊信息采用“圖層名稱或圖層索引號|圖層要素編碼|（環(huán)）面索引號”擴展格式以適應(yīng)多圖層的應(yīng)用擴展。以圖1（a）和圖1（b）為例，線段C D的共邊信息分別為“ZD|1|0”“ZD|2|0”和“DLTB|1|0”“DLTB|5|0”，默認外環(huán)面索引為0。

⑤在步驟5）中，針對每個圖層的共線段進行合并，直到無法再合并為止。

1.3 MapReduce性能提升

針對多圖層實際應(yīng)用情況，對上述算法進行優(yōu)化設(shè)計，引入Map Reduce框架，進一步提升面間接線構(gòu)建效率。具體算法設(shè)計如下：

①采用Map Reduce并行處理框架生成唯一節(jié)點集。Map并行處理子過程：對于每一圖層，按照步驟1）生成該圖層的唯一節(jié)點集。Reduce單線程處理子過程：首先將每個圖層的唯一節(jié)點集合并到總節(jié)點集；然后對總節(jié)點集再執(zhí)行排序去重過程；最后生成唯一總節(jié)點集。

②采用Map Reduce框架生成唯一線段集。Map子過程：對于每個圖層，按步驟2）生成該圖層的唯一線段集。Reduce子過程：首先將每個圖層的唯一線段集添加到總線段集；然后再執(zhí)行排序和線段去重并保留單向線段過程；最后形成唯一總線段集。

③采用Map Reduce框架按最小線段建立共線段映射表。Map子過程：對于每個圖層，按步驟3）進行正負編號，同時按步驟4）建立該圖層的共線段映射表。Reduce子過程：將每個圖層處理好的共線段映射表整合到總的共線段映射表中（添加過程如下：針對每個圖層共線段映射表中的各個共線段，查找總的共線段映射表中是否存在，如果存在，則對共線段信息進行合并；如果不存在，則把該共線段添加到總的共線段映射表中），最終得到最小共線段映射表。

④為后續(xù)最小共線段合并成最大共線段做準備，此時僅采用Map框架對最小共線段映射表中的每條共線段的共線信息進行排序。

1.4 面間接線檢測方法

在面間接線構(gòu)建完成后，為了檢驗生成的面間接線的正確性，本文給出一種快速自動測試設(shè)計方案，形成閉環(huán)管理。具體算法設(shè)計如下：

①針對上述并行算法生成的面間接線數(shù)據(jù)，將面間接線按方向進行首尾拼接，重新形成一條完整的線。假設(shè)生成的面間接線數(shù)據(jù)如下：間接線1的順序節(jié)點為A D；間接線2的順序節(jié)點為D C；間接線3的順序節(jié)點為A B C…。以圖1（a）的要素1為例，假設(shè)要素1生成的面間接線結(jié)果為（?1，3，?2），則要素1面間接線按順序進行拼接后形成完整線（記為ZD_FEATURE1_LINE1）的順序節(jié)點結(jié)果為D A B C D，已去掉中間重復節(jié)點。

②判斷拼接線是否封閉，如果不是，則生成的面間接線有誤，則面間接線構(gòu)建失敗。例如，ZD_FEATURE1_LINE1的首尾節(jié)點都為D，因此生成正確。

③將拼接線進行雙份擴充處理，形成雙倍線。例如，圖1（a）要素1的拼接線ZD_FEATURE1_LINE1進行雙倍擴展處理后，形成雙倍線（記為ZD_FEATURE1_LINE1_TWICE）順序節(jié)點為D A B C D A B C D，已去掉一個重復的拼接節(jié)點D。

④判斷要素面中原始順序節(jié)點數(shù)據(jù)是否是其對應(yīng)雙倍線的子集。例如，圖1（a）要素1的原始順序節(jié)點數(shù)據(jù)為A B C D A，顯而易見，可以從其雙倍線ZD_FEATURE1_LINE1_TWICE中查找到完全匹配的子序列A B C D A，這表明要素1的面間接線生成成功；否則面間接線構(gòu)建失敗。

⑤利用上述自動檢測過程可以同時處理不同圖層、不同要素、不同面對象，相互間并不沖突，易于采用并行算法實現(xiàn)，因此可以復用§1.3的Map處理過程進行性能優(yōu)化。

2 算法實現(xiàn)與比較

算法程序通過地理信息系統(tǒng)開發(fā)平臺King?Map V6.0實現(xiàn)，King Map V6.0平臺升級版基于QT5.9開發(fā)，通過C/C++語言實現(xiàn)，采用Qt Con?current框架的blocking Mapped Reduced機制實現(xiàn)Map Reduce功能，多次采用阻塞機制是因為前后步驟之間需要同步，保持數(shù)據(jù)一致性。該平臺運行環(huán)境為VMware虛擬機：Windows7 SP1旗艦版64位操 作 系 統(tǒng)；DDR3 800 MHz 4 GB內(nèi) 存；Intel（R）Core（TM）i5?4200U@1.60 GHz 2.30 GHz雙核處理器；硬盤50 GB，5 400 r/min。算法程序以某鎮(zhèn)的行政區(qū)圖層（64個要素）、宗地圖層（290個要素）和地類圖斑圖層（1 730個要素）為例進行間接線的構(gòu)建和導出，檢驗結(jié)果表明，導出的結(jié)果數(shù)據(jù)真實可靠。不同算法的性能比較結(jié)果如表1所示。

從表1中可以看出，本文算法在雙線程情況下，經(jīng)過1.014 s從64個行政區(qū)、290個宗地和1 730個地類圖斑中構(gòu)建7 904個間接線。雖然達不到理論上的性能提升效果，但性能仍有所提升，約提升15.6%。相較于節(jié)點共面算法，本文算法性能大幅提升。對導出結(jié)果進行檢驗，確認導出數(shù)據(jù)正確且所有的間接線不重疊和不重復，符合VCT的要求，如圖2所示。

表1 算法性能比較Tab.1 Comparison of Performances of Different Algorithms

圖2 導出的數(shù)據(jù)Fig.2 Export Data

3 結(jié)束語

本文通過面要素的共邊合并，提出了一種并行構(gòu)建多圖層面要素間接線的算法，同時給出了一種面間接線構(gòu)建是否有效性的高效并行檢測方法。該算法已在地理信息系統(tǒng)開發(fā)平臺KingMap V6.0上編程實現(xiàn)并進行測試。結(jié)果表明，該算法可靠，不僅在性能上大幅提升，還解決了一些無效圖形問題。例如，同一個面多次經(jīng)過同一個節(jié)點。但是，該算法仍然存在不足之處，有待在分布式環(huán)境下進行擴展設(shè)計和實現(xiàn)，后續(xù)會對此問題進行研究。