兩種地圖點群綜合算法的比較

李　赟,閆浩文,劉正軍

(1.蘭州交通大學測繪與地理信息學院，甘肅蘭州730070；2 中國測繪科學研究院，北京100830)

?

兩種地圖點群綜合算法的比較

李赟1,2,閆浩文1,劉正軍2

(1.蘭州交通大學測繪與地理信息學院，甘肅蘭州730070；2 中國測繪科學研究院，北京100830)

摘要：通過搭建實驗程序，分別對基于非加權Voronoi圖和加權Voronoi圖的點群自動綜合算法進行驗證，詳細對比和分析兩種算法計算結果對點群的統計信息、拓撲信息、度量信息和專題信息的傳遞情況，計算部分結果的相似度，從而得出加權Voronoi圖點群綜合算法更優的結論。

關鍵詞：傳統Voronoi圖；加權Voronoi圖；點群綜合；算法；相似度

數字地圖在比例尺變化的過程中產生地圖符號擁擠、堆疊和沖突等問題。要使得地圖清晰可讀，在地圖比例尺改變的過程中必須采取一些必要的操作(如：選擇、簡化、聚合等)來化簡地圖要素，這個過程稱之為地圖綜合[1]。

點群是地圖上常見的要素，如在中小比例尺地圖中的城市、島嶼群等，分析單個目標點信息沒有意義，值得關心的是群體分布所隱含的空間結構化信息[2]。綜合結果的質量評估是基于點群空間分布結構化信息的，主要是通過建立指標，對點群綜合前后空間分布結構化信息的對比[3]。點群目標典型的結構化特點有分布范圍輪廓形狀、密度、紋理結構特征等[4]，綜合前后的結果應該在分布模式、分布范圍、相對密度等方面保持相似關系。因此，量化計算綜合前后點群的相似度是算法評估的常用方法[5-6]。點群綜合過程中涉及的主要操作是選擇保留點，即通過“選取”算子實現點群自動綜合，選取的標準應符合地圖綜合過程中盡可能傳遞重要信息的原則。對現有的算法進行歸納，需要傳遞的信息有4類：統計信息、專題信息、度量信息和拓撲信息[1,7-9]。點群的統計信息是點數；專題信息是點的權值，通過對考察問題量化得到；度量信息包括點的局部密度、相對密度、點群分布范圍(分布多邊形)；拓撲信息為點的Voronoi鄰居[1,7-9]。

目前已有的點群綜合算法有居民地空間比率算法、分布系數算法、重力模型算法、圓增長算法、基于四叉樹的算法、點地圖化簡算法、顧及空間特征的算法、Kohonen網絡算法、基于Voronoi圖的算法和基于加權Voronoi圖的算法[6]。其中前6種算法只部分顧及了4類信息，第7、8種算法未能給出綜合結果對信息傳輸的量化評價。后2種算法顧及4類信息，算法9使用Ordinary Voronoi Diagram (簡稱OVD)為工具來表達點的影響范圍，算法10在算法9的基礎上使用改進的Multiplicatively Weighted Voronoi Diagram (簡稱MWVD)來替代OVD。由于后2種算法對信息傳遞考慮比較全面，且具有相關性，故本文通過實驗對后2種算法進行對比和分析。

1OVD和MWVD算法

1.1　基本概念

1)選取法則：確定地圖上的點數，可采用：

其中，Nf為被選取的點數，N0為綜合前的點數，S0為綜合前地圖比例尺分母，Sf為綜合后地圖比例尺分母。

2)虛擬邊界點：為了消除邊界點和內點差異化的處理方法，并且更符合真實邊界帶狀分布的特征，人為定義一組邊界點。原始點群全部位于虛擬邊界的內部。

3)Voronoi圖可以很好的表達地物要素的影響區域，算法中使用Voronoi圖來處理幾何度量信息和拓撲信息。

4)點的重要性程度值：重要性程度值屬于專題信息，反映不同點的重要性程度。

5)點的選取概率：表示某一點在下一輪刪除中被保留的概率，該值在算法中作為點是否被保留的參考，由點的重要性程度值和點的Voronoi圖面積共同確定。

1.2　OVD算法

OVD算法有以下3個步驟：

1)構造新點集：先構造原始點群的Delaunay三角網，由此搜索一條包含所有初始點的多邊形，該多邊形的頂點就是邊界點。然后構造一條新的邊界多邊形，使得該多邊形的每一條邊和初始點的邊界多邊形對應且平行，新多邊形稱為虛擬邊界，虛擬邊界的頂點為虛擬邊界點。虛擬邊界點和初始邊界點的距離等于初始邊界上邊長的平均值。虛擬邊界點和初始點共同構成了新點集。

2)基于Voronoi圖的點群反復綜合：構造新點集的Voronoi圖，根據

3)確定最后保留在結果地圖上的點數：設最后一輪刪除地圖上保留點數為n1，倒數第二輪刪除地圖上保留點數為n2，若|Nf-n1|<|Nf-n2|，則綜合結果保留點數為n1，反之為n2。

1.3　MWVD算法

MWVD算法基本步驟和OVD算法相似，也具有3個步驟[10-14]：

1)構造新點集：同OVD算法，找到初始點的邊界多邊形。連接初始點邊界多邊形質心和邊界點，并向外延伸得到虛擬邊界頂點，延伸長度與該射線通過的初始邊界點相關聯的三角形邊長的平均值。順次連接各延長線頂點就得到了虛擬邊界多邊形。

2)基于MWVD的點群反復綜合：①構造包含虛擬點在內的新點群的MWVD；②利用

計算每個點的選取概率Pi，Ai是第i點的Voronoi多邊形面積；③點群初始點都賦以“自由”的狀態，綜合過程中還會產生“固定”和“被刪”的狀態；④把“自由”點按選取概率的升序排列；⑤找出“自由”點中選取概率最小的一個，若該點所有鄰居點都是自由的，則標記該點為“被刪”，并固定其所有鄰居點，返回④；否則把“固定”點改為“自由”點，結束本輪刪除。

3)確定最后保留在結果地圖上的點數：方法同OVD算法。

1.4　兩種算法比較

本文從以下方面對兩種算法進行對比:

1)統計信息。即點數，用最終結果保留的點數和用基本選取法則計算的理論值做對比。

2)專題信息。分別計算綜合前后點群重要性程度值，對比兩種算法在綜合過程中對專題信息的傳遞效果。

3)度量信息。計算綜合前后點群的分布多邊形，從多邊形相似性來判定綜合結果對點群分布范圍的傳遞情況。

2實驗研究

程序采用C#語言編寫，設計自定義文件格式，支持文件讀寫，鼠標繪制點群，計算Delaunay三角網、加權和非加權Voronoi圖、邊界多邊形等，并對OVD和MWVD點群綜合算法均進行了實現，還支持單步查看每一輪刪除結果的功能。此外，程序實現統計綜合前后點群專題信息(重要性程度值)、相對局部密度和分布邊界等信息的功能。

2.1　實驗1

選取四川省1~3級城市的點群數據，共156個點。城市點群綜合是常見的點群綜合性問題，在綜合過程中，等級高的城市應盡可能被保留，且要顧及點群分布密度。原數據見圖1。

圖1　四川省156個城市點群數據(1級126個，2級29個，3級1個)

實驗中設定原始地圖比例尺分母為S0=10 000,目標地圖比例尺分母為Sf=50 000,MWVD算法和OVD算法的綜合結果見圖2。

圖2　四川省城市點群數據綜合結果

1)根據選取的基本法則計算得到的目標地圖點數為69。MWVD算法綜合后點數為59，OVD算法結果為66。可以看出OVD算法的綜合結果保留點數更接近按基本選取法則計算的結果，OVD算法總共進行了4輪刪除，每一輪刪除的點數分別為29、24、21、16；WMVD算法進行了3輪刪除，每一輪刪除的點數為44、30、23。結論：MWVD算法每一輪刪除點的“幅度”比OVD算法大，效率更高。

2)綜合前點的重要性程度平均值為1.198 718，綜合后MWVD算法結果為1.423 729，OVD算法為1.287 879。可見在綜合過程中，MWVD算法更好的保留了重要性程度大的點。

3)MWVD算法和OVD算法綜合前后的點群分布范圍見圖3。圖中實線為原始點群分布范圍，虛線為綜合后點群的分布范圍。原始點群分布多邊形面積為92 492 610.86，MWVD與OVD算法計算結果點群的分布多邊形面積分別為101 269 409.51、105 851 225.30，相對面積分別為1.095、1.144。由此可知，MWVD算法計算結果的分布多邊形與原始點群分布多邊形面積相似比更大。從形態上觀察，MWVD算法計算結果的分布多邊形也與原始點群分布多邊形重合度更大。

圖3　四川省城市點群數據分布范圍(虛線為綜合后數據分布范圍)

2.2　實驗2

模擬了兩組數據，具有兩種不同等級的點(1和2)見圖4。數據1點分布均勻的特點，電線桿塔的分布，包含51個點；數據2分布狹長，呈帶狀分布，包含40個點。實驗參數同實驗1。

1)數據1原始數據包含51個點，基本選取法則計算結果為22個點，經過MWVD算法綜合后剩余18個點(經3輪刪除)，經過OVD算法綜合后剩余21個點(經5輪刪除)；數據2原始數據包含40個點，基本選取法則計算結果為17個點，經過MWVD算法綜合后剩余20個點(經3輪刪除，取第2輪刪除的結果)，經過OVD算法綜合后剩余18個點(經5輪刪除，去第4輪刪除的結果)。再次驗證了MWVD算法效率高的結論。

2)數據1綜合前重要性程度值的平均值為1.215 686，經MWVD算法綜合后為1.5，經OVD算法綜合后為1.476 19；數據2綜合前重要性程度值的平均值為1.2，經MWVD算法綜合后為1.4，經OVD算法綜合后為1.388 889。兩組數據的實驗中，MWVD算法對重要性程值得傳播率略高于OVD算法。此外，點群中重要性程度值高的點數越少，MWVD算法和OVD算法綜合后點群的重要性程度值的平均值越接近。

3)兩組數據經兩種算法綜合后的分布多邊形見圖5。

從表1中可以看出，MWVD算法的計算結果分布多邊形面積相似比結果更優。

圖4　兩組模擬數據

圖5　兩組數據綜合前后分布范圍(虛線為綜合后)

原始點群分布多邊形面積MWVD計算結果分布多邊形面積OVD計算結果分布多邊形面積MWVD計算結果面積相似比OVD計算結果面積相似比數據185959768.2390410791.7827342477.691.050.32數據2152688127.55151357841.8176259107.250.990.50

3結束語

本文對OVD和MWVD點群綜合算法的實驗結果進行對比分析，驗證兩種算法的可行性。通過對比，基于MWVD點群綜合算法在效率、綜合結果的各項信息的傳遞中效果更優。本文討論的兩種算法屬于圖的點群綜合算法，具有很高的時間復雜度，如何有效地提高效率有待進一步研究。另外，點群自動綜合算法結果需在分布模式、分布范圍、相對密度等方面保持相似關系，因此相似度計算的研究將應該作為地圖綜合算法的必要補充。

參考文獻：

[1]YAN H W,WEIBEL R.An algorithm for point cluster generalization based on the Voronoi diagram [J].Computers and GeoSciences,2008,34(8):939-954.

[2]艾廷華，劉耀林.保持空間分布特征的群點化簡方法[J].測繪學報，2002，31(2)：175-181.

[3]牛繼強，徐豐，姚高偉.點群多尺度表達不確定性評估方法研究[J].測繪科學，2011，36(4)：75-77.

[4]郭慶勝.點狀要素群的結構化及其在綜合中的應用[J].測繪學院學報，1999，16(3)，210-213.

[5]梅耀元，閆浩文，李強.多尺度地理空間點狀要素相思關系研究[J].測繪與空間地理信息，2010，33(2)：18-20.

[6]劉濤，杜清運，閆浩文.空間點群目標相似度計算[J].武漢大學學報(信息科學版)，2011，36(10)：1149-1153.

[7]閆浩文，王家耀.基于Voronoi圖的點群目標普適綜合算法[J].中國圖象圖形學報，2005，10(5)：633-636.

[8]閆浩文，王邦松.地圖點群綜合的加權Voronoi算法[J].武漢大學學報(信息科學版)，2013，38(9)：1088-1091.

[9]陳靜靜，閆浩文.應用一級鄰近點生成加權Voronoi圖的思想[J].重慶工學院學報(自然科學版)，2008，22(1)：85-88.

[10]蒙印，艾廷華，楊井源.1∶250 000水系要素綜合縮編技術方法[J].測繪與空間地理信息，2014，37(3):201-203.

[11]夏永亮.基于復雜網絡理論的城市道路網絡自動綜合方法[J].測繪與空間地理信息，2014，37(8):155-156.

[12]于艷平，沈婕，尚在穎.點群選取與化簡算法時間復雜度研究[J].南京師大學報(自然科學版)，2012，35(1)：111-116.

[13]武芳，王家耀.地圖自動綜合概念框架分析與研究[J].測繪工程，2002，11(2)：18-20，48.

[14]王輝連，武芳，王寶山，等.用于數字地圖自動綜合的多邊形合并算法[J].測繪工程，2005，14(3)：15-18.

[責任編輯：李銘娜]

Comparison of two point cluster generalization algorithms

LI Yun1，2,YAN Hao-wen1,LIU Zheng-jun2

(1.School of Geomatics,Lanzhou Jiaotong University,Lanzhou 730070,China；2.Chinese Academy of Surveying & Mapping,Beijing 100830,China)

Abstract：A test program is build up, in which the OVD-based and MWVD-based algorithms for point cluster generalization are verified.The statistical,topological,metric and thematic information transmissions during the process of generalization are analyzed in details. The similarities of some of the results are also calculated,thus the MWVD-based algorithm is proved to be better.

Key words：ordinary Voronoi diagrams；multiplicative weighted Voronoi diagrams；point cluster generalization；algorithms；similarity

作者簡介：李赟(1986-),男，碩士研究生.

基金項目：國家自然科學基金資助項目(40871208)

收稿日期：2014-09-20

中圖分類號：P283.1

文獻標識碼：A

文章編號：1006-7949(2015)12-0043-05