李　赟,閆浩文,劉正軍

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

?

兩種地圖點(diǎn)群綜合算法的比較

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

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

摘要：通過(guò)搭建實(shí)驗(yàn)程序，分別對(duì)基于非加權(quán)Voronoi圖和加權(quán)Voronoi圖的點(diǎn)群自動(dòng)綜合算法進(jìn)行驗(yàn)證，詳細(xì)對(duì)比和分析兩種算法計(jì)算結(jié)果對(duì)點(diǎn)群的統(tǒng)計(jì)信息、拓?fù)湫畔?、度量信息和專題信息的傳遞情況，計(jì)算部分結(jié)果的相似度，從而得出加權(quán)Voronoi圖點(diǎn)群綜合算法更優(yōu)的結(jié)論。

關(guān)鍵詞：傳統(tǒng)Voronoi圖；加權(quán)Voronoi圖；點(diǎn)群綜合；算法；相似度

數(shù)字地圖在比例尺變化的過(guò)程中產(chǎn)生地圖符號(hào)擁擠、堆疊和沖突等問(wèn)題。要使得地圖清晰可讀，在地圖比例尺改變的過(guò)程中必須采取一些必要的操作(如：選擇、簡(jiǎn)化、聚合等)來(lái)化簡(jiǎn)地圖要素，這個(gè)過(guò)程稱之為地圖綜合[1]。

點(diǎn)群是地圖上常見(jiàn)的要素，如在中小比例尺地圖中的城市、島嶼群等，分析單個(gè)目標(biāo)點(diǎn)信息沒(méi)有意義，值得關(guān)心的是群體分布所隱含的空間結(jié)構(gòu)化信息[2]。綜合結(jié)果的質(zhì)量評(píng)估是基于點(diǎn)群空間分布結(jié)構(gòu)化信息的，主要是通過(guò)建立指標(biāo)，對(duì)點(diǎn)群綜合前后空間分布結(jié)構(gòu)化信息的對(duì)比[3]。點(diǎn)群目標(biāo)典型的結(jié)構(gòu)化特點(diǎn)有分布范圍輪廓形狀、密度、紋理結(jié)構(gòu)特征等[4]，綜合前后的結(jié)果應(yīng)該在分布模式、分布范圍、相對(duì)密度等方面保持相似關(guān)系。因此，量化計(jì)算綜合前后點(diǎn)群的相似度是算法評(píng)估的常用方法[5-6]。點(diǎn)群綜合過(guò)程中涉及的主要操作是選擇保留點(diǎn)，即通過(guò)“選取”算子實(shí)現(xiàn)點(diǎn)群自動(dòng)綜合，選取的標(biāo)準(zhǔn)應(yīng)符合地圖綜合過(guò)程中盡可能傳遞重要信息的原則。對(duì)現(xiàn)有的算法進(jìn)行歸納，需要傳遞的信息有4類(lèi)：統(tǒng)計(jì)信息、專題信息、度量信息和拓?fù)湫畔1,7-9]。點(diǎn)群的統(tǒng)計(jì)信息是點(diǎn)數(shù)；專題信息是點(diǎn)的權(quán)值，通過(guò)對(duì)考察問(wèn)題量化得到；度量信息包括點(diǎn)的局部密度、相對(duì)密度、點(diǎn)群分布范圍(分布多邊形)；拓?fù)湫畔辄c(diǎn)的Voronoi鄰居[1,7-9]。

目前已有的點(diǎn)群綜合算法有居民地空間比率算法、分布系數(shù)算法、重力模型算法、圓增長(zhǎng)算法、基于四叉樹(shù)的算法、點(diǎn)地圖化簡(jiǎn)算法、顧及空間特征的算法、Kohonen網(wǎng)絡(luò)算法、基于Voronoi圖的算法和基于加權(quán)Voronoi圖的算法[6]。其中前6種算法只部分顧及了4類(lèi)信息，第7、8種算法未能給出綜合結(jié)果對(duì)信息傳輸?shù)牧炕u(píng)價(jià)。后2種算法顧及4類(lèi)信息，算法9使用Ordinary Voronoi Diagram (簡(jiǎn)稱OVD)為工具來(lái)表達(dá)點(diǎn)的影響范圍，算法10在算法9的基礎(chǔ)上使用改進(jìn)的Multiplicatively Weighted Voronoi Diagram (簡(jiǎn)稱MWVD)來(lái)替代OVD。由于后2種算法對(duì)信息傳遞考慮比較全面，且具有相關(guān)性，故本文通過(guò)實(shí)驗(yàn)對(duì)后2種算法進(jìn)行對(duì)比和分析。

1OVD和MWVD算法

1.1　基本概念

1)選取法則：確定地圖上的點(diǎn)數(shù)，可采用：

其中，Nf為被選取的點(diǎn)數(shù)，N0為綜合前的點(diǎn)數(shù)，S0為綜合前地圖比例尺分母，Sf為綜合后地圖比例尺分母。

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

3)Voronoi圖可以很好的表達(dá)地物要素的影響區(qū)域，算法中使用Voronoi圖來(lái)處理幾何度量信息和拓?fù)湫畔ⅰ?/p>

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

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

1.2　OVD算法

OVD算法有以下3個(gè)步驟：

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

2)基于Voronoi圖的點(diǎn)群反復(fù)綜合：構(gòu)造新點(diǎn)集的Voronoi圖，根據(jù)

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

1.3　MWVD算法

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

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

2)基于MWVD的點(diǎn)群反復(fù)綜合：①構(gòu)造包含虛擬點(diǎn)在內(nèi)的新點(diǎn)群的MWVD；②利用

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

3)確定最后保留在結(jié)果地圖上的點(diǎn)數(shù)：方法同OVD算法。

1.4　兩種算法比較

本文從以下方面對(duì)兩種算法進(jìn)行對(duì)比:

1)統(tǒng)計(jì)信息。即點(diǎn)數(shù)，用最終結(jié)果保留的點(diǎn)數(shù)和用基本選取法則計(jì)算的理論值做對(duì)比。

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

3)度量信息。計(jì)算綜合前后點(diǎn)群的分布多邊形，從多邊形相似性來(lái)判定綜合結(jié)果對(duì)點(diǎn)群分布范圍的傳遞情況。

2實(shí)驗(yàn)研究

程序采用C#語(yǔ)言編寫(xiě)，設(shè)計(jì)自定義文件格式，支持文件讀寫(xiě)，鼠標(biāo)繪制點(diǎn)群，計(jì)算Delaunay三角網(wǎng)、加權(quán)和非加權(quán)Voronoi圖、邊界多邊形等，并對(duì)OVD和MWVD點(diǎn)群綜合算法均進(jìn)行了實(shí)現(xiàn)，還支持單步查看每一輪刪除結(jié)果的功能。此外，程序?qū)崿F(xiàn)統(tǒng)計(jì)綜合前后點(diǎn)群專題信息(重要性程度值)、相對(duì)局部密度和分布邊界等信息的功能。

2.1　實(shí)驗(yàn)1

選取四川省1~3級(jí)城市的點(diǎn)群數(shù)據(jù)，共156個(gè)點(diǎn)。城市點(diǎn)群綜合是常見(jiàn)的點(diǎn)群綜合性問(wèn)題，在綜合過(guò)程中，等級(jí)高的城市應(yīng)盡可能被保留，且要顧及點(diǎn)群分布密度。原數(shù)據(jù)見(jiàn)圖1。

圖1　四川省156個(gè)城市點(diǎn)群數(shù)據(jù)(1級(jí)126個(gè)，2級(jí)29個(gè)，3級(jí)1個(gè))

實(shí)驗(yàn)中設(shè)定原始地圖比例尺分母為S0=10 000,目標(biāo)地圖比例尺分母為Sf=50 000,MWVD算法和OVD算法的綜合結(jié)果見(jiàn)圖2。

圖2　四川省城市點(diǎn)群數(shù)據(jù)綜合結(jié)果

1)根據(jù)選取的基本法則計(jì)算得到的目標(biāo)地圖點(diǎn)數(shù)為69。MWVD算法綜合后點(diǎn)數(shù)為59，OVD算法結(jié)果為66?？梢钥闯鯫VD算法的綜合結(jié)果保留點(diǎn)數(shù)更接近按基本選取法則計(jì)算的結(jié)果，OVD算法總共進(jìn)行了4輪刪除，每一輪刪除的點(diǎn)數(shù)分別為29、24、21、16；WMVD算法進(jìn)行了3輪刪除，每一輪刪除的點(diǎn)數(shù)為44、30、23。結(jié)論：MWVD算法每一輪刪除點(diǎn)的“幅度”比OVD算法大，效率更高。

2)綜合前點(diǎn)的重要性程度平均值為1.198 718，綜合后MWVD算法結(jié)果為1.423 729，OVD算法為1.287 879?？梢?jiàn)在綜合過(guò)程中，MWVD算法更好的保留了重要性程度大的點(diǎn)。

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

圖3　四川省城市點(diǎn)群數(shù)據(jù)分布范圍(虛線為綜合后數(shù)據(jù)分布范圍)

2.2　實(shí)驗(yàn)2

模擬了兩組數(shù)據(jù)，具有兩種不同等級(jí)的點(diǎn)(1和2)見(jiàn)圖4。數(shù)據(jù)1點(diǎn)分布均勻的特點(diǎn)，電線桿塔的分布，包含51個(gè)點(diǎn)；數(shù)據(jù)2分布狹長(zhǎng)，呈帶狀分布，包含40個(gè)點(diǎn)。實(shí)驗(yàn)參數(shù)同實(shí)驗(yàn)1。

1)數(shù)據(jù)1原始數(shù)據(jù)包含51個(gè)點(diǎn)，基本選取法則計(jì)算結(jié)果為22個(gè)點(diǎn)，經(jīng)過(guò)MWVD算法綜合后剩余18個(gè)點(diǎn)(經(jīng)3輪刪除)，經(jīng)過(guò)OVD算法綜合后剩余21個(gè)點(diǎn)(經(jīng)5輪刪除)；數(shù)據(jù)2原始數(shù)據(jù)包含40個(gè)點(diǎn)，基本選取法則計(jì)算結(jié)果為17個(gè)點(diǎn)，經(jīng)過(guò)MWVD算法綜合后剩余20個(gè)點(diǎn)(經(jīng)3輪刪除，取第2輪刪除的結(jié)果)，經(jīng)過(guò)OVD算法綜合后剩余18個(gè)點(diǎn)(經(jīng)5輪刪除，去第4輪刪除的結(jié)果)。再次驗(yàn)證了MWVD算法效率高的結(jié)論。

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

3)兩組數(shù)據(jù)經(jīng)兩種算法綜合后的分布多邊形見(jiàn)圖5。

從表1中可以看出，MWVD算法的計(jì)算結(jié)果分布多邊形面積相似比結(jié)果更優(yōu)。

圖4　兩組模擬數(shù)據(jù)

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

原始點(diǎn)群分布多邊形面積MWVD計(jì)算結(jié)果分布多邊形面積OVD計(jì)算結(jié)果分布多邊形面積MWVD計(jì)算結(jié)果面積相似比OVD計(jì)算結(jié)果面積相似比數(shù)據(jù)185959768.2390410791.7827342477.691.050.32數(shù)據(jù)2152688127.55151357841.8176259107.250.990.50

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

本文對(duì)OVD和MWVD點(diǎn)群綜合算法的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比分析，驗(yàn)證兩種算法的可行性。通過(guò)對(duì)比，基于MWVD點(diǎn)群綜合算法在效率、綜合結(jié)果的各項(xiàng)信息的傳遞中效果更優(yōu)。本文討論的兩種算法屬于圖的點(diǎn)群綜合算法，具有很高的時(shí)間復(fù)雜度，如何有效地提高效率有待進(jìn)一步研究。另外，點(diǎn)群自動(dòng)綜合算法結(jié)果需在分布模式、分布范圍、相對(duì)密度等方面保持相似關(guān)系，因此相似度計(jì)算的研究將應(yīng)該作為地圖綜合算法的必要補(bǔ)充。

參考文獻(xiàn)：

[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]艾廷華，劉耀林.保持空間分布特征的群點(diǎn)化簡(jiǎn)方法[J].測(cè)繪學(xué)報(bào)，2002，31(2)：175-181.

[3]牛繼強(qiáng)，徐豐，姚高偉.點(diǎn)群多尺度表達(dá)不確定性評(píng)估方法研究[J].測(cè)繪科學(xué)，2011，36(4)：75-77.

[4]郭慶勝.點(diǎn)狀要素群的結(jié)構(gòu)化及其在綜合中的應(yīng)用[J].測(cè)繪學(xué)院學(xué)報(bào)，1999，16(3)，210-213.

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

[6]劉濤，杜清運(yùn)，閆浩文.空間點(diǎn)群目標(biāo)相似度計(jì)算[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2011，36(10)：1149-1153.

[7]閆浩文，王家耀.基于Voronoi圖的點(diǎn)群目標(biāo)普適綜合算法[J].中國(guó)圖象圖形學(xué)報(bào)，2005，10(5)：633-636.

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

[9]陳靜靜，閆浩文.應(yīng)用一級(jí)鄰近點(diǎn)生成加權(quán)Voronoi圖的思想[J].重慶工學(xué)院學(xué)報(bào)(自然科學(xué)版)，2008，22(1)：85-88.

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

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

[12]于艷平，沈婕，尚在穎.點(diǎn)群選取與化簡(jiǎn)算法時(shí)間復(fù)雜度研究[J].南京師大學(xué)報(bào)(自然科學(xué)版)，2012，35(1)：111-116.

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

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

[責(zé)任編輯：李銘娜]

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

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

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(40871208)

收稿日期：2014-09-20

中圖分類(lèi)號(hào)：P283.1

文獻(xiàn)標(biāo)識(shí)碼：A

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