劉　晴，郭慶勝，龍　毅

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

?

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

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

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

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

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

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

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

1比例射線移位算法簡述

1.1　基本原理

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

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

2)確定每一個類群的移位中心點；

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

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

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

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

1)實現(xiàn)了沖突的自動識別，計算量小，簡單方便；

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

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

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

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

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

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

2算法的改進

2.1　考慮點群中空間目標的大小

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

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

(1)

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

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

(2)

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

k=minLength/MinDis.

(3)

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

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

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

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

(4)

其中，Dis是當前點與移位中心的歐氏距離值，MaxDis是點群中距離移位中心最遠點的距離值。

2.2　迭代過程

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

2.3　非常鄰近居民地的移位

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

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

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

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

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

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

3算法的實驗

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

圖1　軟件界面

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

圖2　沖突區(qū)域

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

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

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

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

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

圖6　新位置的選擇

4結(jié)論與討論

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

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

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

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

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

參考文獻：

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

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

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

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

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

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

[7]吳小芳,杜清運,徐智勇.多層次移位原則的道路與建筑物空間沖突處理[J].測繪學(xué)報,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é)進展，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.

[責任編輯：王文福]

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-)，女，碩士.

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

收稿日期：2014-11-18

中圖分類號：P283.1；TP319

文獻標識碼：A

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