比例射線移位算法的改進(jìn)及其應(yīng)用

劉　晴，郭慶勝，龍　毅

(1.武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院，湖北武漢430079；2.南京師范大學(xué)地理科學(xué)學(xué)院，江蘇南京210023)

?

比例射線移位算法的改進(jìn)及其應(yīng)用

劉晴1，郭慶勝1，龍毅2

(1.武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院，湖北武漢430079；2.南京師范大學(xué)地理科學(xué)學(xué)院，江蘇南京210023)

摘要：點(diǎn)狀要素群移位的比例射線算法能夠較好地保持移位后點(diǎn)群的空間分布模式。文中從農(nóng)村居民地群移位的實(shí)際要求出發(fā)，對比例射線移位算法進(jìn)行了改進(jìn)：首先考慮居民地面積的不同大小對移位的影響；其次，設(shè)計(jì)比例射線移位的迭代方法；最后對于非常鄰近的居民地群的移位，采用“微小”移位方法。通過實(shí)驗(yàn)驗(yàn)所改進(jìn)的算法是有效的。

關(guān)鍵詞：制圖綜合；點(diǎn)群移位；比例射線移位；農(nóng)村居民地

移位算法,最初是為解決地圖綜合中比例尺縮放和符號(hào)化后引起的要素空間沖突而產(chǎn)生的算法，是制圖綜合的基本手段之一。隨著地理空間數(shù)據(jù)比例尺的縮小，地圖目標(biāo)之間將不可避免地產(chǎn)生沖突[1]。制圖綜合中,對于地圖要素間的空間沖突,主要是通過移位來解決,從而滿足對象之間的最小間隔要求,并保持地圖要素之間的鄰近空間關(guān)系[2]。

地圖上點(diǎn)狀要素群的移位可簡稱為點(diǎn)群移位，有很多學(xué)者對點(diǎn)群移位進(jìn)行過深入研究,提出了很多較為可行的移位算法[3-7]。但是點(diǎn)群自動(dòng)移位在不同類別的點(diǎn)狀要素群中會(huì)出現(xiàn)很多特殊情況，針對農(nóng)村居民地群的空間特征，本文對比例射線移位算法進(jìn)行了改進(jìn)。

1比例射線移位算法簡述

1.1　基本原理

比例射線移位是William A.Mackaness于1994年提出的，算法的主要思想是首先利用層次聚類算法確定潛在的空間沖突區(qū)域，找出產(chǎn)生空間沖突的對象群，將對象群看成一個(gè)整體，然后找到移位中心點(diǎn)[8]。沖突區(qū)域中每一個(gè)對象的移位距離都與其距離移位中心距離成函數(shù)關(guān)系，移位方向就是移位中心到每一個(gè)對象的射線方向。比例射線移位算法步驟如下：

1)設(shè)定一個(gè)合適閾值，通過基于最短距離的層次聚類算法將空間鄰近點(diǎn)聚集為一個(gè)類群，確定要素間可能沖突區(qū)域；

2)確定每一個(gè)類群的移位中心點(diǎn)；

3)通過比例射線函數(shù)計(jì)算移位量，對群內(nèi)點(diǎn)相對于中心點(diǎn)進(jìn)行移位；

4)針對沖突區(qū)域邊緣點(diǎn)移位量大的問題，通過引入衰減函數(shù)來控制局部變形和次生沖突。

1.2　算法的優(yōu)勢與不足

比例射線移位算法滿足了諸多制圖約束條件，在點(diǎn)群移位中，具有很強(qiáng)的優(yōu)越性，主要包括以下優(yōu)點(diǎn)：

1)實(shí)現(xiàn)了沖突的自動(dòng)識(shí)別，計(jì)算量小，簡單方便；

2)能夠較好地保持要素間的空間關(guān)系，從而保證整體空間布局基本不變；

3)移位中心會(huì)自動(dòng)向沖突最密集的位置靠近，從而能夠保證大多數(shù)的點(diǎn)只移動(dòng)一個(gè)最小距離。

原有的比例射線移位算法的不足之處主要包括：

1)沒有考慮空間目標(biāo)的大小，例如，建筑物有一定大小，不能僅僅簡單地將它們看成同樣的點(diǎn)；

2)無法確認(rèn)能通過1次移位就解決所有空間沖突，在進(jìn)行移位時(shí)，1次移位有時(shí)可能無法解決整個(gè)沖突區(qū)域的空間沖突問題；

3)有些空間沖突僅僅使用比例射線算法進(jìn)行移位很難解決，這時(shí)還需要與其它算法相結(jié)合。

2算法的改進(jìn)

2.1　考慮點(diǎn)群中空間目標(biāo)的大小

William A.Mackaness在介紹比例射線移位算法時(shí)也曾提到過給每一個(gè)點(diǎn)狀要素按照重要性分別賦予一個(gè)層級的思想[8]。也就是說，在執(zhí)行移位的過程中，沖突區(qū)域內(nèi)每一個(gè)點(diǎn)的重要性或者說層級是不同的，在移位中希望能夠保證重要的點(diǎn)，移動(dòng)的距離越小。實(shí)現(xiàn)這種思想的方法則是在確定移位中心時(shí)根據(jù)層級給每一個(gè)點(diǎn)賦予一個(gè)權(quán)重，對沖突區(qū)域內(nèi)每一個(gè)點(diǎn)進(jìn)行加權(quán)平均來確定移位中心。

比例射線移位算法是根據(jù)沖突區(qū)域內(nèi)每一個(gè)點(diǎn)距離移位中心的距離，依照一定比率計(jì)算相應(yīng)的移位量，然后對所有點(diǎn)進(jìn)行射線式移位的算法。考慮建筑物的面積大小，移位中心的計(jì)算見式(1)：

(1)

求得移位中心后，沖突區(qū)域中每個(gè)點(diǎn)的移位量EDis與其距移位中心的距離Dis的關(guān)系見式(2)。

EDis=k×Dis×a×e-bx.

(2)

其中，k是移位比率，按照式(3)計(jì)算。

k=minLength/MinDis.

(3)

式(3)中，minLength是在保持清晰度的前提下地圖上要素之間的最小間隔，一般為0.2 mm。MinDis是地圖上該點(diǎn)群中距離移位中心最近點(diǎn)的距離值。

式(2)中a×e-bx是衰減函數(shù)模型[9]，x的計(jì)算見式(4)。

x=(Dis-MinDis)/(MaxDis-MinDis).

T：But something is wrong.What’s wrong?T：What is the size?

(4)

其中，Dis是當(dāng)前點(diǎn)與移位中心的歐氏距離值，MaxDis是點(diǎn)群中距離移位中心最遠(yuǎn)點(diǎn)的距離值。

2.2　迭代過程

使用比例射線移位算法對沖突區(qū)域進(jìn)行移位之后，一般情況下，點(diǎn)群空間沖突都基本能夠得以解決，但是可能出現(xiàn)部分區(qū)域內(nèi)依然存在著小范圍空間沖突的情況。這個(gè)時(shí)候，如果改變移位函數(shù)的參數(shù)，沖突可能依舊難以解決或是容易造成其他要素的移位量過大。因此，本文設(shè)計(jì)了一個(gè)多次迭代的過程。其基本思想是：對沖突區(qū)域進(jìn)行比例射線移位之后，再一次判斷沖突，若仍然存在小部分沖突，則把依舊存在沖突的點(diǎn)群作為一個(gè)新的沖突區(qū)域，繼續(xù)進(jìn)行比例射線移位；如此循環(huán)下去，直到類似的空間沖突得以解決。

2.3　非常鄰近居民地的移位

當(dāng)沖突區(qū)域中兩個(gè)或多個(gè)建筑物在空間上非常鄰近，尤其是在其與移位中心的距離較遠(yuǎn)時(shí)，僅僅使用比例射線算法進(jìn)行移位很難解決沖突。為此，本文提出了一種改進(jìn)算法和Dewdney的“unhappiness”算法[10][11]相結(jié)合。這個(gè)算法的基本思想是：對于每一個(gè)對象，都在它當(dāng)前位置的周圍找?guī)讉€(gè)可以替代它的位置，然后從中選擇與周圍對象的重疊度達(dá)到最小值那個(gè)位置，并將此位置作為該對象的新位置。

本文簡化了Dewdney的“unhappiness”算法，先選取一個(gè)合適的生成候選點(diǎn)半徑，對相應(yīng)的點(diǎn)進(jìn)行微小移動(dòng)，然后繼續(xù)利用改進(jìn)的比例射線移位算法，對它們進(jìn)行移位。過程如下：

1)選取非常鄰近的農(nóng)村居民地點(diǎn)群，計(jì)算中心點(diǎn)，并設(shè)置移位半徑r；

2)在以中心點(diǎn)為圓心，r為半徑的圓周上找到候選的8個(gè)新位置(分別為中心點(diǎn)圓周上從正北方向起，每隔45°確定一個(gè)新位置，組成這8個(gè)位置)；

3)在這8個(gè)候選的新位置中找到一個(gè)作為過于鄰近要素的新位置；

4)對擁有新位置的點(diǎn)和整個(gè)沖突區(qū)域的其它點(diǎn)一起進(jìn)行比例射線移位，并對結(jié)果進(jìn)行評估，判斷沖突的解決效果。

3算法的實(shí)驗(yàn)

為了驗(yàn)證改進(jìn)后的比例射線移位算法，本文實(shí)驗(yàn)數(shù)據(jù)是法國一處農(nóng)村居民地地圖，來源于French national mapping agency Institute Geographic National，地圖比例尺為1∶10 000，地圖投影為Gauss_Kruger，坐標(biāo)系是GCS_Beijing_1954。利用AE+C#編程實(shí)現(xiàn)該算法，軟件的界面見圖1。

圖1　軟件界面

為了更好地說明算法的實(shí)驗(yàn)效果，在地圖中找到三處典型的沖突區(qū)域，如圖2所示。

圖2　沖突區(qū)域

考慮建筑物面積大小后的移位結(jié)果見圖3(本次實(shí)驗(yàn)中a=1,b=1)，圖中灰色區(qū)域?yàn)榻ㄖ镌嘉恢茫瑑?nèi)邊框?yàn)橐莆缓蟮慕ㄖ?，外邊框?yàn)闆_突檢測的緩沖區(qū)邊界?？梢钥吹?jīng)_突基本得以解決了。但是從圖3中可以看到，圖3(a)和圖3(b)中還是存在沖突(見圓圈所示之處)，圖3(b)中是新產(chǎn)生的沖突。很明顯，這些沖突需要采用本文提到的迭代處理方法，圖4及圖5分別是對圖3(a)和圖3(b)進(jìn)行迭代的結(jié)果。結(jié)果表明在進(jìn)行比例射線移位迭代之后，空間沖突問題都得到了很好的解決。

圖3　考慮面積大小的移位結(jié)果

圖4　沖突區(qū)域圖3(a)的迭代過程

圖5　沖突區(qū)域圖3(b)的迭代過程

另外，圖6是兩個(gè)建筑物非常鄰近且又距移位中心較遠(yuǎn)的情況，按照本文的方法進(jìn)行了“微小”移位處理，新位置的選擇見圖6。

圖6　新位置的選擇

4結(jié)論與討論

本文在點(diǎn)群移位已有的比例射線移位算法基礎(chǔ)上提出了幾點(diǎn)改進(jìn)，并用AE+C#編程實(shí)現(xiàn)了該算法，取得了很好的實(shí)驗(yàn)結(jié)果，得到了以下的結(jié)論：

1)針對農(nóng)村居民地移位的實(shí)際要求，考慮居民地面積的大小后，能夠保證面積越大的建筑物移位的距離越??；

2)多次迭代的過程能夠很好地解決新產(chǎn)生的類似空間沖突；

3)對于沖突區(qū)域中非常鄰近且與移位中心距離較遠(yuǎn)的建筑物的移位，采用“微小”移位方法，即先進(jìn)行微移位處理，再對整體采用比例射線移位算法進(jìn)行移位，能夠取得更好的效果。

農(nóng)村建筑物群與道路等有密切關(guān)系，為了能解決不同要素之間的空間沖突，還需要進(jìn)一步研究不同移位算法的結(jié)合。

參考文獻(xiàn)：

[1]陳科,謝明霞,李柱林.基于面積分界尺度的居民地輪廓化簡[J].測繪工程,2012,21(2):32-34.

[2]吳小芳,杜清運(yùn),胡月明,等.制圖綜合中移位算法概述分析[J].測繪科學(xué),2008,33(2):117-120.

[3]艾廷華.基于場論分析的建筑物群的移位[J].測繪學(xué)報(bào),2004,33(1):89-94.

[4]熊枝艷，劉遠(yuǎn)剛，郭慶勝，等.一種改進(jìn)的點(diǎn)群移位算法及其應(yīng)用[J].測繪與空間地理信息,2014,37(10):71-74.

[5]費(fèi)立凡.用計(jì)算機(jī)模擬人類制圖員解決地圖縮編中的圖形沖突[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2004,29(5):426-432.

[6]侯璇,武芳,劉芳,等.基于彈性力學(xué)思想的居民地點(diǎn)群目標(biāo)位移模型[J].測繪科學(xué),2005,30(2):44-47.

[7]吳小芳,杜清運(yùn),徐智勇.多層次移位原則的道路與建筑物空間沖突處理[J].測繪學(xué)報(bào),2010,39(6)：649-654.

[8]WILLIAM A.M.An Algorithm for Conflict Identification and Feature Displacement in Automated Map Generalization[J].Cartography and Geographic Information Systems,1994,21 (4):219-232.

[9]王成金.中國交通流的衰減函數(shù)模擬及特征[J].地理科學(xué)進(jìn)展，2009，28 (5):690-696.

[10]WILLIAM A.M.Automated Displacement for Large Numbers Of Discrete Map Objects[J].Algorithmica,2001,30 (2):302-311.

[11]DEWDNEY A.K.Computer Recreations：Diverse personalities search for social equilibrium at a computer party[J].Scientific American,1987,257:112-116.

[責(zé)任編輯：王文福]

The improvement and application of proportional radial displacement

LIU Qing1,GUO Qing-sheng1,LONG Yi2

(1.School of Resource and Environment Science,Wuhan University,Wuhan 430079,China；2.School of Geographic Science,Nanjing Normal University,Nanjing 210023,China)

Abstract：The proportional radial displacement algorithm for the displacement of a group of points can be used to maintain spatial distribution patterns of points after displacement.In this paper,the proportional radial displacement algorithm is improved according to the real demand of rural residents’ displacement.Firstly,the size of rural residents is put into consideration during displacement;secondly,an iterative method of proportional radial displacement is designed;lastly,a “minimum” displacement method is proposed for rural residents which are too closed to each other.The effectiveness of the improved algorithm is verified by means of the practical test.

Key words：cartographic generalization；points displacement；proportional radial displacement；rural residents

作者簡介：劉晴(1992-)，女，碩士.

基金項(xiàng)目：國家863計(jì)劃資助項(xiàng)目(2012AA12A402 );國家自然科學(xué)基金資助項(xiàng)目(41071289，41171350，41471384)

收稿日期：2014-11-18

中圖分類號(hào)：P283.1；TP319

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

文章編號(hào)：1006-7949(2015)12-0068-04