楊 偉， 鄧涵文， 馮賢菊， 廖雪花， 李曉寧*

（1.四川師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，四川成都610101； 2.河南工業(yè)職業(yè)技術(shù)學(xué)院電子信息工程學(xué)院，河南南陽473000）

矢量數(shù)據(jù)壓縮在計(jì)算機(jī)圖形學(xué)、地理信息系統(tǒng)（GIS）和數(shù)字制圖等方面的應(yīng)用非常廣泛，其中較為廣泛使用的壓縮方法為Douglas-Pecucker算法［1］及其一系列的改進(jìn)算法，其中改進(jìn)算法大多側(cè)重于算法時(shí)間效率的優(yōu)化［2］、距離閾值的計(jì)算［3-4］、自相交和相交拓?fù)洚惢瘑栴}的處理［5-7］等.在壓縮過程中，保持?jǐn)?shù)據(jù)的拓?fù)湟恢滦詫?shù)字制圖和GIS都至關(guān)重要［8］.然而，大多數(shù)矢量數(shù)據(jù)壓縮算法在壓縮數(shù)據(jù)時(shí)并不考慮數(shù)據(jù)的空間關(guān)系，壓縮后出現(xiàn)拓?fù)潢P(guān)系不一致［9］，如在對共享公共邊的無拓?fù)涫噶繄D形壓縮時(shí)存在公共邊裂縫的拓?fù)洳灰恢聠栴}.出現(xiàn)這一拓?fù)洚惢瘑栴}的根本原因是無拓?fù)涫噶繄D形的共享邊被存儲多次，當(dāng)壓縮算法對起止點(diǎn)敏感時(shí)，共享公共邊的兩相鄰圖形因起始點(diǎn)和結(jié)束點(diǎn)不同，壓縮后導(dǎo)致共享邊在2個圖形中出現(xiàn)不同的化簡結(jié)果［10］.如圖1（a）所示，多邊形 A 與 B 共享頂點(diǎn)｛P6，P7，P8，P9，P1｝，多邊形 A、B 經(jīng)壓縮算法化簡后，頂點(diǎn)P7從A中刪除，但沒有從B中刪除，公共邊｛P6，P7，P8，P9，P1｝在2 個圖形中的壓縮結(jié)果不一致，因而出現(xiàn)圖1（b）中的裂縫.

圖1 公共邊裂縫問題Fig.1 Common edge crack problem

針對這一問題，翟戰(zhàn)強(qiáng)等［11］采用窮舉搜索思想查找多邊形的公共邊，對公共邊和非公共邊分別壓縮.王凈等［12］采用深度搜索匹配法在整個矢量數(shù)據(jù)范圍內(nèi)查找公共邊，將其從多邊形數(shù)據(jù)中獨(dú)立出來重組數(shù)據(jù)，然后用DP算法進(jìn)行壓縮.張勝等［13］采用正向搜索和反向搜索相結(jié)合的方法提取公共邊生成等效元數(shù)據(jù)，對元數(shù)據(jù)壓縮后再重建數(shù)據(jù)并按原格式存儲.吳正升等［14］提出一個約束點(diǎn)串建立算法提取公共邊的首尾端點(diǎn)，將多邊形邏輯分段，然后再壓縮各個分段.同文獻(xiàn)［12-13］的方法相比，文獻(xiàn)［14］的算法所需輔助空間較少，但公共邊被多次壓縮，因而時(shí)間效率不高.謝亦才等［15］利用字符串的模式匹配算法（KMP算法）提取公共邊，根據(jù)公共邊對象的壓縮標(biāo)記保證公共邊只壓縮1次.金良益等［16］指出了深度搜索匹配法提取公共邊的不足，提出了一種基于共線搜索匹配的公共邊提取算法.此外，金良益［17］將公共邊的提取轉(zhuǎn)化為找最長公共子串，提出了一種基于動態(tài)規(guī)劃的無拓?fù)涫噶炕噙呅喂策吿崛∷惴?趙真等［18］提出了考慮空間對象拓?fù)潢P(guān)系的壓縮算法，保留了拓?fù)潢P(guān)系，解決了公共邊壓縮后出現(xiàn)裂縫的問題.

上述文獻(xiàn)均采取化簡前提取多邊形的公共邊，對公共邊和非公共邊分別壓縮的策略，保證公共邊去除的頂點(diǎn)保持一致.該類算法雖可解決公共邊裂縫問題，但時(shí)間效率比較低，主要原因有以下3點(diǎn)：

1）每個矢量圖形均需要同其他矢量圖形進(jìn)行是否相交判斷，假設(shè)矢量圖形數(shù)為m，則相交判斷的時(shí)間復(fù)雜度為O（m2）；

2）提取公共頂點(diǎn)的方法大都采用雙向深度搜索匹配法、模式匹配算法或動態(tài)規(guī)劃算法，這一類算法在搜索多邊形數(shù)量較多時(shí)效率不高；

3）公共邊在壓縮時(shí)可能被壓縮處理多次.

原因2）為制約算法效率的關(guān)鍵.為解決上述問題，本文提出了一種基于單調(diào)鏈和Geohash索引的公共邊裂縫處理算法.

針對以往模型做了以下3點(diǎn)改進(jìn)：

針對1），為了避免在整個圖形集中進(jìn)行相交圖形的判斷，本文采用單調(diào)鏈掃描線算法，通過建立矢量圖形單調(diào)鏈，提前過濾掉了大量相離圖形，大大減少需要進(jìn)行相交判斷的矢量圖形數(shù)，一定程度上提高了算法效率；

針對2），本文利用Geohash編碼長于快速搜索的特性，構(gòu)建Geohash索引結(jié)構(gòu)，將空間劃分為一個個矩形區(qū)域，實(shí)現(xiàn)兩相交圖形的公共頂點(diǎn)快速查找，大大提高了公共點(diǎn)的查找速率；

針對3），設(shè)計(jì)了一個索引結(jié)構(gòu)存儲公共邊的壓縮信息，當(dāng)檢索到公共邊已被壓縮過時(shí)，則直接根據(jù)索引結(jié)構(gòu)提取公共邊的第一次壓縮數(shù)據(jù)，在保證公共邊只壓縮一次的條件下保證圖形的完整性和一致性.

1 基于單調(diào)鏈和Geohash索引的公共邊裂縫處理算法

基于單調(diào)鏈的掃描線算法常用于平面線段集合求交中過濾大量候選線段［19］.基于此，本文將其應(yīng)用于矢量圖形集的預(yù)處理，用于從眾多的矢量圖形中挑選出可能與當(dāng)前圖形相交的矢量圖形.其次，對每個矢量圖形，計(jì)算每個頂點(diǎn)的Geohash編碼，創(chuàng)建Geohash索引表.然后，利用Geohash索引快速查找的特性，根據(jù)圖形的相交圖形，在圖形中找到公共點(diǎn)和非公共點(diǎn)，并據(jù)此將矢量圖形劃分為公共邊集合和非公共邊集合.最后，對公共邊和非公共邊分段壓縮時(shí)，對壓縮過的公共邊建立索引，保證公共邊只壓縮一次.

算法可粗略分為初始化圖形單調(diào)鏈、生成相交圖形集、建立Geohash索引表、提取公共邊和分段壓縮5個步驟.依次詳述如下.

1.1 初始化圖形單調(diào)鏈單調(diào)鏈掃描線算法的前提就是生成矢量圖形的單調(diào)鏈.為此，本文利用堆排序算法，根據(jù)每個矢量圖形的最小外接矩形MBR（Minimum Bounding Rectangle）的最小橫坐標(biāo) xmin對圖形集進(jìn)行排序，生成一個xmin值由小到大的單調(diào)鏈，記為 MC（Monotonic Chain）.MC 中圖形的xmin單增，如果多個圖形的xmin相同，則按其最小縱坐標(biāo)ymin由小到大排序.如圖2所示的矢量圖形集｛A，B，C，D，E，F(xiàn)，G｝，排序后生成的圖形單調(diào)鏈 MC為｛A，D，B，E，C，F(xiàn)，G｝.

圖2 圖形集示例Fig.2 A graphics set example

1.2 生成相交圖形集基于生成的單調(diào)鏈MC，利用掃描線算法掃描單調(diào)鏈MC中的矢量圖形，確定每個圖形的相交圖形集.涉及的數(shù)據(jù)結(jié)構(gòu)有：MC，含義同上；AC（Active Chain）記錄同當(dāng)前掃描線相交的矢量圖形集合；RS（Related Shapes）為圖形的相交圖形集.

設(shè)單調(diào)鏈MC中有k個圖形，過每個圖形Si的MBR 的 xmin做縱向掃描線，記為 xi（i＝1，2，…，k）.初始化AC＝｛｝，對每一個xi，依次執(zhí)行如下步驟：

1）如果AC中圖形的MBR的xmax≤xi，從AC中刪除該圖形；

2）將該圖形Si插入AC；

3）將新插入圖形Si，同AC中已有圖形逐一進(jìn)行最小外接矩形的相交判斷，若AC中已有圖形與新插入圖形Si相交，則將該圖形保存在新插入圖形Si的相交圖形列表RS中.

表1以圖2所示的圖形集為例，說明生成相交圖形集的執(zhí)行過程.圖形C、F的MBR的xmin相同，所以掃描線x5和掃描線x6相同，分別代表圖形C、F生成相交圖形列表的過程.

通過上述掃描過程，可以過濾掉大量相離圖形，快速確定每個矢量圖形的相交圖形.結(jié)束掃描后，每個圖形都生成一個列表RS，記錄了與自己相交的所有矢量圖形，為下一步的公共邊提取處理提供了基礎(chǔ)數(shù)據(jù).

表1 相交圖形集的生成過程Tab.1 Generation process of intersecting graphics sets

1.3 建立Geohash索引表Geohash編碼將二維的經(jīng)緯度坐標(biāo)編碼成一維的字符串，在實(shí)現(xiàn)鄰近點(diǎn)搜索時(shí)具有快速查找的顯著優(yōu)勢［20］.Geohash編碼技術(shù)廣泛應(yīng)用于空間數(shù)據(jù)的檢索，其編碼過程實(shí)際上是將區(qū)域劃分為一個個規(guī)則矩形，并對每個矩形進(jìn)行base32編碼.Geohash編碼長度越長，區(qū)域劃分越細(xì)，搜索時(shí)的效率越高.例如經(jīng)緯度坐標(biāo)為（116.389 550，39.928 167）的空間點(diǎn)，按 Geohash 編碼生成的二進(jìn)制序列為11100 11101 00100 01111，按base32編碼為wx4g，實(shí)際上是表明該點(diǎn)落在wx4g代表的矩形區(qū)域.

Geohash索引表的建立的過程如下：

對MC中每一個圖形Si，初始化一個Hash表HTi為空.對圖形Si中的每一個頂點(diǎn)Vk，

1）計(jì)算頂點(diǎn)Vk的Geohash編碼Code；

2）若Code在索引表HTi的表項(xiàng)中已存在，則將坐標(biāo)點(diǎn)插入到Geohash編碼對應(yīng)的鏈表之后，否則在索引表中新增一項(xiàng)，并保存Geohash編碼和坐標(biāo)點(diǎn)到該項(xiàng)對應(yīng)的鏈表.

按上述算法，MC中每一個圖形都會生成一個類似圖3的Geohash表.Geohash索引表中的每一項(xiàng)都由鍵值Geohash編碼及其對應(yīng)的坐標(biāo)點(diǎn)鏈表組成，鏈表中存放Geohash編碼相同的坐標(biāo)點(diǎn)，提供了Geohash編碼和坐標(biāo)點(diǎn)之間的映射關(guān)系.

圖3 Geohash索引表示例圖Fig.3 Example diagram of Geohash index table

通過鍵值Geohash編碼來檢索落在某個區(qū)域的坐標(biāo)點(diǎn)，只需搜索Geohash編碼對應(yīng)的鏈表中的坐標(biāo)點(diǎn)即可，速度非?？?當(dāng)編碼長度較大時(shí)，鏈表中的坐標(biāo)點(diǎn)個數(shù)接近于1，檢索坐標(biāo)點(diǎn)的時(shí)間復(fù)雜度接近于 O（1）.

1.4 公共邊提取公共邊提取的前提是公共點(diǎn)的判斷.根據(jù)上一節(jié)為每個圖形建立的Geohash表，對于相交的2個圖形A和B，判斷A上一點(diǎn)point是否為A和B的公共點(diǎn)的方法如下：

1）計(jì)算點(diǎn)point的Geohash編碼，假設(shè)為code2；

2）在圖形B的Geohash索引表中查找key值為code2的項(xiàng).如找到，轉(zhuǎn)3）；如未找到，point為圖形A、B的非公共點(diǎn)；

3）找到該項(xiàng)對應(yīng)的坐標(biāo)點(diǎn)鏈表（如圖4中虛線框部分），比較point與鏈表中的點(diǎn)坐標(biāo)是否相同.若相同，則point為公共點(diǎn)，否則為非公共點(diǎn).

圖4 公共點(diǎn)查找示意圖Fig.4 Example diagram of finding common points

公共邊提取實(shí)質(zhì)上是公共邊端點(diǎn)的查找.假如端點(diǎn)已經(jīng)確定，以之作為約束點(diǎn)，即可在約束點(diǎn)處將多邊形從邏輯上分段，拆分為公共邊和非公共邊.

假設(shè)圖形 A 頂點(diǎn)記為 ai，i＝1，2，…，m；圖形 B為 A 的一個相交圖形，其頂點(diǎn)記為 bj，j＝1，2，…，n.圖形A中的有2個相鄰頂點(diǎn)ai和ai-1，根據(jù)2個相鄰頂點(diǎn)是否是公共點(diǎn)這一特性，可劃分為4種可能：

1）若ai為公共點(diǎn)且ai-1為非公共點(diǎn)，則ai為公共邊的端點(diǎn).ai和圖形B中與ai坐標(biāo)相同的頂點(diǎn)bj分別為圖形A和B的拆分點(diǎn)，如圖5（a）.

2）若ai為非公共點(diǎn)且ai-1為公共點(diǎn)，則ai-1為公共邊的端點(diǎn)，ai-1和圖形B中與ai-1坐標(biāo)相同的頂點(diǎn)bk分別為圖形A和B的拆分點(diǎn)，如圖5（b）.

3）若ai、ai-1均為公共點(diǎn)，則需進(jìn)一步判斷圖形B 中ai、ai-1對應(yīng)的公共點(diǎn)bj、bk是否連續(xù)（包括正向連續(xù)或反向連續(xù)），若不連續(xù)，則ai-1、ai為公共邊的端點(diǎn)，ai-1、bk和 ai、bj均為圖形 A、B 的拆分點(diǎn)，如圖5（c）；若連續(xù)，則 ai不是端點(diǎn)，ai-1是否為端點(diǎn)尚需結(jié)合ai-2是否為公共點(diǎn)來判斷.

4）若 ai、ai-1均為非公共點(diǎn)，則 ai、ai-1均不是公共邊的端點(diǎn).

圖5 公共邊首尾點(diǎn)的3種情況Fig.5 Three kinds of end point cases on common edge

記sorta、sortb為記錄圖形A、B所有公共邊首尾點(diǎn)下標(biāo)的有序鏈表.假設(shè)ai為公共點(diǎn)，bj為B中與ai坐標(biāo)相同的公共點(diǎn)；ai-1為公共點(diǎn)，bk為B中與ai-1坐標(biāo)相同的公共點(diǎn)，初始化i＝1.根據(jù)上面的公共點(diǎn)判斷規(guī)則，在2個相交矢量圖形中查找公共邊端點(diǎn)的主要步驟如下：

1）讀取矢量圖形 A（a1，a2，…，ai，…，am）、B（b1，b2，…，bj，…，bn）.

2）讀取矢量圖形 A 上點(diǎn) ai（i＝1，2，…，m）的Geohash編碼.

3）根據(jù)上面的公共點(diǎn)判斷方法，判斷ai是否為公共點(diǎn).若ai為公共點(diǎn)，轉(zhuǎn)4）；若ai為非公共點(diǎn)，轉(zhuǎn) 6）.

4）若ai-1為非公共點(diǎn)，則ai為公共邊的端點(diǎn)，ai、bj應(yīng)為拆分點(diǎn)（如圖6中的的情況），將其下標(biāo)存儲在各自的排序表sorta、sortb，否則轉(zhuǎn)5）.

5）若 i＝m，則 ai為公共邊的端點(diǎn)，ai、bj為拆分點(diǎn)，將其下標(biāo)存儲在各自的排序表sorta、sortb，轉(zhuǎn)7）；否則進(jìn)一步判斷bj下標(biāo)同bk下標(biāo)是否連續(xù)，即｜j-k｜是否等于 1，若不連續(xù)（｜j-k｜！＝1），則 ai、ai-1為公共邊的端點(diǎn)，ai-1、bk和 ai、bj均為拆分點(diǎn)，將其下標(biāo)存儲在各自的排序表sorta、sortb，轉(zhuǎn)7）.

6）若ai-1為公共點(diǎn)，則ai-1為公共邊界的端點(diǎn)，ai-1、bk為拆分點(diǎn)（如圖6中的的情況），將其下標(biāo)存儲在各自的排序表sorta、sortb；否則，轉(zhuǎn)7）.

圖6 公共邊首尾端點(diǎn)的標(biāo)記Fig.6 Mark the ends of common edge

7）i＋ ＋，若 i＞m 結(jié)束；否則，轉(zhuǎn)2）.

待所有圖形處理完，每個圖形可得到一個記錄圖形拆分點(diǎn)下標(biāo)的有序鏈表sort.根據(jù)這個有序鏈表對圖形進(jìn)行邏輯分段，就可將圖形分為公共邊和非公共邊.如圖6所示，圖形A得到的有序鏈表為｛4，6｝，可將其拆分成下標(biāo)為1 ～4、4 ～6、6 ～1 的3個邏輯分段；圖形B的有序鏈表為｛5，7｝，可將其拆分成下標(biāo)為1～5、5～7、7～1的3個邏輯分段.

1.5 分段壓縮基于上一小節(jié)的提取結(jié)果，可將每個圖形邏輯分段為公共邊和非公共邊，依次對每個分段進(jìn)行壓縮，能夠解決公共邊裂縫的問題.但公共邊在共邊圖形中至少出現(xiàn)2次，出于效率考慮的原因，希望其只被壓縮1次.為實(shí)現(xiàn)上述目的，并且保證所有共邊圖形的完整性和一致性，本文設(shè)計(jì)了一個索引結(jié)構(gòu)表，用于為一個圖形保存有關(guān)公共邊壓縮的索引信息，如圖7所示.

圖7 公共邊壓縮信息索引表Fig.7 Index table of common edge compression information

信息索引結(jié)構(gòu)表中每個元素保存每條公共邊有關(guān)壓縮的必要信息，元素由（key，Value）鍵值對構(gòu)成.其中key為公共邊壓縮前首點(diǎn)在原鏈表中的索引號；Value有2個數(shù)據(jù)段，一個為該公共邊壓縮后首點(diǎn)在新鏈表中的索引號Indexafter，另一個為公共邊壓縮后頂點(diǎn)的數(shù)量length.當(dāng)圖形未被壓縮時(shí)，索引表為空；有公共邊被壓縮后，索引表記錄了圖形中公共邊的壓縮結(jié)果.

圖6所示的圖形A，只具有一條公共邊，其首尾點(diǎn)分別為｛4，6｝.假設(shè)該公共邊第一次壓縮，壓縮后非公共邊1～4由4個點(diǎn)約簡為3個點(diǎn)，公共邊4～6由3個點(diǎn)約簡為2個點(diǎn)，則A需要維護(hù)圖7所示的壓縮信息索引表，表中只有一個元素，其（key，Value）分別為（4，（3，2））.

分段壓縮時(shí)，首先根據(jù)有序鏈表數(shù)據(jù)將原點(diǎn)鏈表分解為多個邏輯分段.對于每一個分段，執(zhí)行如下步驟：

1）如果該段為非公共邊，直接調(diào)用壓縮算法.

2）如果為公共邊，首先根據(jù)其首尾點(diǎn)索引號j、k找到其在共邊圖形中的對應(yīng)索引號l、m.以l、m的最小值min（l，m）作為鍵值，在共邊圖形的壓縮信息索引表中查找該項(xiàng)是否存在.如果不存在，該公共邊未被壓縮，轉(zhuǎn)3）；如果存在，該公共邊已被壓縮，轉(zhuǎn)4）.

3）直接調(diào)用壓縮算法，并保存該公共邊的壓縮索引信息到圖形的公共邊壓縮信息索引表.

4）根據(jù)該項(xiàng)的Value，從共邊圖形壓縮后的頂點(diǎn)鏈表中，直接拷貝或者反序拷貝從Indexafter開始的length個頂點(diǎn)作為壓縮結(jié)果.

根據(jù)公共邊首尾點(diǎn)索引號j、k查找其在共邊圖形中的對應(yīng)索引號l、m時(shí)，有可能會出現(xiàn)反序情況，如圖6所示，A中的公共邊頂點(diǎn)序號｛4，6｝在B中對應(yīng)為｛7，5｝.在查找索引信息時(shí)，需根據(jù)較小值｛5｝作為查找的鍵值，同時(shí)拷貝公共邊壓縮數(shù)據(jù)時(shí)也需要反序.

1.6 算法整體流程綜上所述，從多個圖形對象中提取公共邊和非公共邊的算法流程如下：

1）對矢量圖形集進(jìn)行堆排序，獲得圖形集的單調(diào)鏈MC.

2）通過掃描線算法掃描上述單調(diào)鏈MC，確定每個圖形的相交圖形列表RS.

3）構(gòu)建所有圖形的Geohash索引.

4）相交圖形公共點(diǎn)的查找和標(biāo)記.遍歷每個圖形，查找圖形和其相交圖形列表RS中所有圖形的公共點(diǎn)，根據(jù)公共邊首尾端點(diǎn)的判斷規(guī)則，標(biāo)記公共邊的首尾公共點(diǎn)、邏輯分段公共邊和非公共邊.

5）分段壓縮.

設(shè)shapes為所有圖形的集合；MC為根據(jù)圖形最小包圍盒構(gòu)建的單調(diào)鏈；AC為活動圖形鏈；RS［i］為第 i個圖形的相交圖形列表；HeapSort（shapes）用于生成圖形的單調(diào)鏈，其詳細(xì)的處理流程參見本文1.1 小節(jié)；CheckCross（e，s）用于判斷圖形 e、s的最小外接矩形是否相交；GeohashTable（s）用于為圖形s建立Geohash索引表，其詳細(xì)的處理流程參見本文 1.3 小節(jié)；MarkEndPoint（s，e）用于標(biāo)記圖形s、e的公共邊端點(diǎn)，其詳細(xì)的處理流程參見本文1.4小節(jié)；Compress（s）用于壓縮圖形 s中的各個分段，其詳細(xì)的處理流程參見本文1.5小節(jié).算法偽碼如下：

Input：shapes，vector graphics set and points have no labels

Ouput：shapes，vector graphics set and points have labels

Initializations：

-MC：monotonic chain of shapes，initialized to null；

-AC：active chain of shapes，initialized to null；

For every shape s in shapes｛

／*Compute Minimum Bounding Rectangle*／

Compute MBR（s）；

｝

／*Sort shapes in the increasing order of the minimum x coordinate of its MBR and the minimum y coordinate if minimum x coordinates are equal*／

MC←HeapSort（shapes）；

／*Build relative shapes collection for every shape in MC*／

M←count of shapes in MC；

For i←1 to M｛

／*initialized related shapes set of the i th element of MC*／

RS［i］＝null；

s←MC ［i］；／*the i th element of MC*／

／*the minimum x coordinate of MBR of shape s；

x←s.MBR.xmin；

For every shape e∈AC｛

If e.MBR.xmax≤x then delete e from AC；

｝

For every shape e∈AC ｛

If CheckCross（e，s）then insert（RS［i］，e）；

｝

insert（AC，s）；

｝

／*Construct Geohash Table for every shape in MC*／

For every shape s in MC｛

GeohashTable（s）；

｝

／*Label all end pointsfor every shape

For every shape s in MC｛

For every shape e in RSof shape s｛

／*Find and label end points of shape s and e

MarkEndPoint（s，e）

｝｝

／*Compress every shape sectionally

For every shape s in MC｛

／*Compress every shape s

Compress（s）

｝

2 實(shí)驗(yàn)結(jié)果及分析

本文選取了3個數(shù)據(jù)集，實(shí)現(xiàn)了算法以驗(yàn)證算法的性能.數(shù)據(jù)集分別為：中國省級行政界線Data1，世界地圖中的國家行政界線Data2，中國縣級行政界線Data3.3個真實(shí)矢量地圖數(shù)據(jù)集分別代表了不同數(shù)量等級和不同分布狀態(tài)的地圖數(shù)據(jù)，其參數(shù)如表2所示.

實(shí)驗(yàn)環(huán)境如下，處理器：Intel（R）Core（TM）i7-7700HQ CPU ＠ 2.80 GHz；內(nèi)存：8.00 GB.

表2 測試數(shù)據(jù)集參數(shù)列表Tab.2 Parameter list of three test data sets

2.1 公共邊提取與否對數(shù)據(jù)壓縮影響的定性分析針對上述3個數(shù)據(jù)集，本文采用經(jīng)典Douglas-Peucker算法作為壓縮算法，對比直接進(jìn)行壓縮處理的化簡結(jié)果和經(jīng)本文算法做公共邊預(yù)處理后再壓縮的結(jié)果.總的說來，本文的公共邊提取算法，能夠保證公共邊的化簡結(jié)果一致，解決公共邊裂縫問題.

圖8給出了中國省級行政界線數(shù)據(jù)未做公共邊預(yù)處理和做公共邊預(yù)處理后壓縮結(jié)果的局部放大對比示例.圖8（a）中的粗實(shí)線為未做公共邊提取的壓縮結(jié)果，圖8（b）中的虛線為采用本文算法做公共邊提取后的壓縮結(jié)果.從局部放大圖可以看出，圖8（a）中圓圈部位發(fā)生了裂縫，而圖8（b）則保持了2段公共邊的化簡結(jié)果一致.

圖9給出了世界地圖國家行政界線數(shù)據(jù)未做公共邊預(yù)處理和做公共邊預(yù)處理后壓縮的局部放大對比示例.圖9（a）中粗實(shí)線為未做公共邊提取的壓縮結(jié)果，圖9（b）中的虛線為采用本文算法做公共邊提取后的壓縮結(jié)果.圓圈內(nèi)國家行政邊界與多國接壤，圈內(nèi)線段均為公共邊.從圓圈的局部放大圖可以看出，圖9（a）中圓圈部分粗實(shí)線線條多為雙線，表明多處公共邊被壓縮成不同的結(jié)果，而圖9（b）則保持了多段公共邊的化簡結(jié)果一致.

圖8 測試數(shù)據(jù)集Data1在2種情況下的化簡結(jié)果Fig.8 Different simplified results with or without extraction of common edges in Data1 set

圖9 測試數(shù)據(jù)集Data2在2種情況下的化簡結(jié)果Fig.9 Different simplified results with or without extraction of common edges in Data2 set

從實(shí)驗(yàn)結(jié)果來看，采用本文算法預(yù)先處理相鄰圖形的公共邊，可以保證公共邊在相鄰圖形中化簡結(jié)果的一致，解決常見的公共邊裂縫問題.值得注意的是，雖然都采用DP算法作為壓縮算法，但因?yàn)楣策叡徊鸱趾?，輸入DP算法處理流程的數(shù)據(jù)首尾點(diǎn)發(fā)生了變化，導(dǎo)致公共邊提取后的壓縮結(jié)果與不預(yù)先提取公共邊的結(jié)果有些細(xì)微變化.

2.2 算法的時(shí)間效率分析本文算法中涉及公共邊提取和分段壓縮2個部分，其中分段壓縮部分，其時(shí)間效率受壓縮算法的選取而不同，所以在時(shí)間效率分析上僅對公共邊提取部分的時(shí)間效率進(jìn)行分析.假設(shè)M為圖形集中的圖形總數(shù)，N為圖形集中總的頂點(diǎn)個數(shù)，m為掃描次數(shù)（最壞情況下為圖形總數(shù)M），k為每次掃描要處理的圖形最大值（k?M），ni為圖形i的頂點(diǎn)總數(shù)，ki為圖形i的RS集合中包含的圖形數(shù)，L為Geohash編碼長度，S為Geohash編碼對應(yīng)矩形區(qū)域所包含的點(diǎn)數(shù)的最大值，則公共邊提取算法的4個環(huán)節(jié)的時(shí)間復(fù)雜度分別為：

1）初始化圖形單調(diào)鏈，時(shí)間復(fù)雜度為O（M log2M）.

2）生成每個圖形的相交圖形集合RS，時(shí)間復(fù)雜度為O（k*m）.

4）公共邊的提取.需要遍歷每個圖形，查找圖形和相交圖形集合RS中圖形的公共點(diǎn)，標(biāo)記首尾公共點(diǎn).對于圖形i，判斷其上所有點(diǎn)是否為公共點(diǎn)共需要ni*ki*S次判斷，那么M個圖形總的時(shí)間復(fù)雜度為

其中，K＝max（ki），K?M.

綜上，算法公共邊提取的時(shí)間復(fù)雜度為

2.2.1 Geohash編碼長度對時(shí)間效率的影響 Geo-hash編碼在算法中的作用是減小公共點(diǎn)的搜索范圍.Geohash編碼長度L決定了搜索空間大小，是影響算法時(shí)間效率的重要因素.為測試編碼長度L對算法時(shí)間效率的影響，本文用1～9的編碼長度對3組數(shù)據(jù)集進(jìn)行了公共邊提取實(shí)驗(yàn)，其實(shí)驗(yàn)結(jié)果如表3所示.可以看出，隨著編碼長度L的增加，提取公共邊的時(shí)間總體上呈先下降后上升的趨勢.這是因?yàn)殡S著編碼長度L的增加，每個編碼所對應(yīng)的矩形區(qū)域和落入該區(qū)域的頂點(diǎn)數(shù)越來越小，也就是說Geohash索引表中的頂點(diǎn)鏈表越來越短，查找公共點(diǎn)所花費(fèi)的時(shí)間越來越少.在極限狀態(tài)下，每個編碼所對應(yīng)的矩形區(qū)域最多只包含1個數(shù)據(jù)點(diǎn)，此時(shí)公共點(diǎn)的查找時(shí)間最短.此后，編碼長度的增加對于公共點(diǎn)查找時(shí)間沒有影響，但構(gòu)建索引的時(shí)間一直隨編碼長度單調(diào)遞增.因此，提取公共邊的時(shí)間總體上呈先下降后上升的趨勢.在實(shí)際應(yīng)用中，由于數(shù)據(jù)采集精度的限制，無論數(shù)據(jù)的體量大小、稀疏程度，編碼長度較為合適的取值范圍為4～6.例如，數(shù)據(jù)集Data1，頂點(diǎn)數(shù)在萬級規(guī)模，編碼長度為5時(shí)，提取公共邊耗時(shí)最小，為45.72 ms；數(shù)據(jù)集Data2，頂點(diǎn)數(shù)在十萬級規(guī)模，編碼長度為4時(shí)，提取公共邊耗時(shí)最小，為102.31 ms；數(shù)據(jù)集Data3，頂點(diǎn)數(shù)在百萬級規(guī)模，編碼長度為5時(shí)，提取公共邊耗時(shí)最小，為 1 246.22 ms.

同樣可以看出，提取公共邊所需的時(shí)間與數(shù)據(jù)規(guī)模成正向關(guān)系.在同一編碼長度下，隨著數(shù)據(jù)集頂點(diǎn)數(shù)、圖形數(shù)量的增加，提取公共邊所需時(shí)間也總體呈上升趨勢.在編碼長度為2～3時(shí)，數(shù)據(jù)集Data1提取公共邊所需時(shí)間明顯大于Data2的處理時(shí)間.這主要是因?yàn)镈ata1的圖形比較緊湊，每個圖形的相交圖形個數(shù)K較大的緣故.

2.2.2 算法時(shí)間效率的對比實(shí)驗(yàn)與分析 為進(jìn)一步驗(yàn)證算法的時(shí)間效率，本文選用文獻(xiàn)［14，17］算法和本文算法進(jìn)行對比，其實(shí)驗(yàn)結(jié)果如表4所示.

可以看出，當(dāng)Geohash編碼長度范圍為4～6區(qū)間，本文算法的時(shí)間效率明顯優(yōu)于文獻(xiàn)［17］的動態(tài)規(guī)劃算法和文獻(xiàn)［14］的深度搜索算法.

表3 不同編碼長度、數(shù)據(jù)量和圖形分布狀態(tài)下的公共邊提取時(shí)間Tab.3 Common edge extraction time under different encoding lengths，data amounts，and graphics distribution ms

表4 3個不同算法的公共邊提取時(shí)間Tab.4 Common edge extraction time using three different algorithms ms

此外，本文還對公共邊壓縮一次和未作公共邊壓縮次數(shù)約束的時(shí)間效率進(jìn)行對比，其結(jié)果如表5所示.設(shè)t0為公共邊壓縮次數(shù)未限制的壓縮時(shí)間，t1為公共邊壓縮一次的壓縮時(shí)間，時(shí)間減少率定義為（t1-t0）／t0.

可以看出，限定公共邊壓縮1次時(shí)，算法的效率也有一定的提高.但是對不同的數(shù)據(jù)集，效率提升不同.例如，差不多的壓縮率情況下，對數(shù)據(jù)集Data3，做了公共邊壓縮次數(shù)限定后，時(shí)間減少90.02%.而數(shù)據(jù)集Data2，做了同樣的處理，時(shí)間僅減少了19.92%.這可能跟數(shù)據(jù)集中公共邊的數(shù)量有關(guān).

表5 公共邊壓縮次數(shù)處理前后的不同壓縮時(shí)間Tab.5 Different compression time before and after limiting common edge compression times

綜上，實(shí)驗(yàn)結(jié)果說明了本文的公共邊提取算法，不僅能夠有效地解決公共邊裂縫問題，在時(shí)間效率上也具有較大的優(yōu)越性.

3 結(jié)論

本文在分析多矢量數(shù)據(jù)壓縮時(shí)產(chǎn)生公共邊裂縫的原因，以及解決該問題的常用方法的優(yōu)缺點(diǎn)的基礎(chǔ)上，提出了一種基于單調(diào)鏈和Geohash的公共邊裂縫處理算法，并通過實(shí)驗(yàn)驗(yàn)證了本文算法在解決裂縫問題上的有效性，對比分析了本文算法的時(shí)間效率.

本文還設(shè)計(jì)了一個公共邊壓縮信息索引表，用于公共邊多次壓縮時(shí)直接從第一次壓縮結(jié)果中提取數(shù)據(jù)，從實(shí)驗(yàn)結(jié)果看，經(jīng)過該環(huán)節(jié)處理后，壓縮時(shí)間也有比較明顯地減少.

本文算法不局限于任何壓縮算法，可作為一個預(yù)處理過程，在壓縮前對矢量數(shù)據(jù)進(jìn)行邏輯分段，保證公共邊壓縮結(jié)果的一致性，從而解決公共邊裂縫問題.從實(shí)驗(yàn)結(jié)果可以看出，Geohash編碼長度對于公共邊提取過程的時(shí)間效率的影響比較大，而本文僅從數(shù)據(jù)采集精度的角度給出了編碼長度的一個適當(dāng)范圍，未涉及如何自適應(yīng)的確定編碼長度這一問題，未來需進(jìn)一步研究討論.

此外，本文算法在實(shí)現(xiàn)過程中，未過多考慮數(shù)據(jù)結(jié)構(gòu)與算法的優(yōu)化，如果進(jìn)一步優(yōu)化算法與數(shù)據(jù)結(jié)構(gòu)，在時(shí)間效率上和空間效率上應(yīng)當(dāng)有提升的空間.