胡碧菡 李連營

1武漢大學資源與環(huán)境科學學院，湖北武漢，430079

地理信息可視化分為點數(shù)據(jù)可視化、線數(shù)據(jù)可視化、區(qū)域數(shù)據(jù)可視化［1］。傳統(tǒng)方法中，每個地圖區(qū)域顯示一個與實際陸地面積成比例的區(qū)域，有時可能嚴重歪曲人口統(tǒng)計數(shù)據(jù)，在人口專題地圖中，人口密集的城市應(yīng)該比人口稀少的大城市得到更多關(guān)注度。Cartogram解決了這個問題，它按照屬性數(shù)據(jù)的比例重新分配區(qū)域面積，對地圖進行適當扭曲變形，同時保持各個區(qū)域單元的鄰接關(guān)系。雖然會在一定程度上改變實際區(qū)域的面積和輪廓，但是能更加直觀地表達該區(qū)域的屬性數(shù)據(jù)信息。

在過去，數(shù)學、計算機科學和物理領(lǐng)域的GIS科學家和研究人員在用計算機制作Cartogram時，開發(fā)出了一系列高效的Cartogram地圖繪制算法。為了減少角度的變形，Tobler［2，3］開始了計算機自動繪制Cartogram的第一步，但是這種方法在某些情況下可能會產(chǎn)生地圖的重疊，從而破壞地圖的拓撲結(jié)構(gòu)。為了提高計算速度，Dougenik等［4］引入了一種“細胞”算法，該算法比Tobler算法快，但仍然不能排除拓撲錯誤。Gusein?Zade等［5］完全去除了單元格，使用一個連續(xù)的“位移場”來測量地圖上每個點的位移。Dorling［6］提出了基于細胞自動機的方法，該方法在每次迭代中識別接近區(qū)域邊界的細胞，并進行重新分配。此算法十分簡單，但是生成的Cartogram十分扭曲，不易閱讀。現(xiàn)在最常用、最權(quán)威的方法是基于擴散密度均衡的算法［7］，該算法能保留原來區(qū)域間的拓撲關(guān)系，但計算效率不高。針對此問題，本文提出一種基于熱力傳導的Cartogram算法。

1 傳統(tǒng)基于擴散密度均衡的Cartogram生成算法

根據(jù)特定人口密度繪制地圖的方法允許人口以某種方式從高密度地區(qū)流動到低密度地區(qū)，直到各地的人口密度均衡。即基礎(chǔ)物理學的線性擴散過程［8］是傳統(tǒng)基于擴散方法的基礎(chǔ)。

從概念上講，這種基于擴散密度均衡的算法在進行不同分辨率轉(zhuǎn)換時，會產(chǎn)生不同的格網(wǎng)尺寸、擴散格網(wǎng)尺寸、迭代次數(shù)及生成時間，轉(zhuǎn)換質(zhì)量越高，生成Cartogram所需的時間越長。為此，需要優(yōu)化算法。

2 基于熱力傳導的Cartogram生成算法

在基于熱力傳導的Cartogram算法中，人口密度ρ不僅是位置r(x，y)的函數(shù)，也是時間t的函數(shù)。在一個密度均衡的投影中，時間趨于無窮時，人口密度必須接近均值，即所有的x、y必須滿足：

式中，為時間趨于無窮時的均衡密度。即粒子必須以熱力擴散的方式傳導，不同密度區(qū)域中的所有初始密度差異隨著時間推移而完全消除，然而僅通過這種基于熱力擴散的方式還不能定義投影T，必須要知道每個點(x，y)在t時刻被熱流拖動的速率v(x，y，t)。因為在流動過程中沒有熱力源，所以v必須滿足質(zhì)量守恒方程，即連續(xù)方程：

式中，?為拉普拉斯算子。

如果已知所有的(x，y，t)對應(yīng)的v(x，y，t)，就可以通過r(0)計算出r(t)：

投影T是將r(0)移動到t趨于無窮的r(t)的函數(shù)。

擴散方程需要同時滿足菲克定律和連續(xù)方程，將菲克定律代入連續(xù)方程后，由式（2）可知，密度ρ由擴散方程控制，這是基于擴散的Cartogram生成算法背后的關(guān)鍵因素，菲克擴散的一個優(yōu)點是不會產(chǎn)生可能導致投影T嚴重變形的渦流。菲克擴散并不是獨一無二的能保持質(zhì)量守恒且無渦流產(chǎn)生的擴散過程，本文為了探尋其他無渦流且能保持質(zhì)量守恒的制圖算法，使用密度區(qū)域平均的線型均衡的方法來代替之前的擴散方程。

對所有坐標進行仿射變換后，把地圖區(qū)域置于一 個邊界為xmin=0，xmax=Lx，ymin=0，ymax=Ly（Lx、Ly表示矩形框邊界坐標）的矩形框中，規(guī)定粒子不能流出矩形框范圍內(nèi)，t≤1內(nèi)的速度可以用正弦和余弦的傅里葉變換來表示。

用Lx Ly的矩形網(wǎng)格覆蓋地圖，在計算開始時，使用快速傅里葉變換算法來對地圖上的各坐標點進行變換［9］。這個過程在總運算時間中所占的比例可以忽略不計，將Lx Ly傅里葉變換儲存在存儲器中，用基本微分算法在每個網(wǎng)格點r處得到v(r，t)。在此基礎(chǔ)上，求出方程中的被積函數(shù)。使用預測校正法數(shù)值逼近積分，自動適應(yīng)下一個時間步長的大小，在每個步驟中，將每個Lx Ly集成體直接分配給不同的處理單元。因此，可以通過多核處理器并行計算。

與傳統(tǒng)基于擴散密度均衡的Cartogram生成算法相比，該方法有以下特點：①多線程處理。多個處理單元同時工作，從而大大減少計算時間。②積分與時間t無關(guān)。傅里葉變換只需要在計算開始時進行一次，并且后續(xù)只需要簡單的加減乘除運算，大大提高了運算速度。③傳統(tǒng)基于擴散的算法需要連續(xù)迭代計算直至t趨于無窮大，而本文算法只需要計算到t=1的時刻，這樣就不需要再檢查積分是否收斂，并可以從不同起點開始積分，大大減少計算時間。

該方法的計算效率和圖形精度在理論上都有很大提高。為了檢驗該結(jié)論，本文用經(jīng)典的美國總統(tǒng)大選數(shù)據(jù)和印度國內(nèi)生產(chǎn)總值數(shù)據(jù)來進行實驗與分析。

3 實驗與分析

本文實驗環(huán)境為Mac Book Air，配置為Intel Core i5處理器，1.6 GHz雙核，8 GB運行內(nèi)存，256 GB固態(tài)盤（solid state disk，SSD），采用C語言實現(xiàn)Cartogram算法。

本文用2016年美國選舉投票結(jié)果及2015年印度國內(nèi)生產(chǎn)總值（gross domestic product，GDP）數(shù)據(jù)進行實驗分析。圖1（a）、圖1（b）分別是2016年美國選舉投票結(jié)果基于傳統(tǒng)擴散方法和基于熱力傳導的算法生成的Cartogram。兩者宏觀上無可識別性差別，但是生成圖1（b）所需要的時間僅為生成圖1（a）所需時間的1/10。

圖1 2016美國選舉投票結(jié)果CartogramFig.1 Cartogram of Election Results of America in 2006

由圖2可以看出，按照行政區(qū)劃分的最大的兩個州拉賈斯坦邦（RJ）和中央邦（MP）在Cartogram上縮小，因為它們的GDP排名分別為第七和第十。GDP最高的馬哈拉施特拉邦（MH）在Cartogram上略微增長，最明顯的是德里（DL）的增長，雖然行政區(qū)劃面積很小，但是其GDP比很多大州的都要高，而阿魯納恰爾邦（AR）和其他幾個東北部州，雖然行政區(qū)劃面積很大，但是由于GDP值落后，情況則正好相反。利用基于擴散密度均衡方法構(gòu)建Cartogram需要130.6 s，而使用本文算法只要5.2 s。具體運算時間見表1。

圖2 2015印度聯(lián)邦地區(qū)行政區(qū)劃及GDP數(shù)據(jù)生成的CartogramFig.2 Administrative Divisions and Cartogram Generated by GDP Data in India

表1 基于擴散和基于熱力傳導的Cartogram算法的運算時間Tab.1 Calculation Time of Diffusion?Based Algorithm and Cartogram Based on Heat Conduction

在實驗中，首先使用Albers等面積圓錐投影將地域邊界的經(jīng)度和緯度投影到2D空間上，將圖1（a）、圖2（a）嵌入一個Lx Ly的矩形框中，將其邊界作為熱力流動的反射邊界。矩形框大小的選擇需要綜合考慮，在保證Cartogram與邊界條件無關(guān)的條件下要盡量減少計算目標區(qū)域投影T的時間。綜合考慮后，矩形框的邊長等于各國南北和東西范圍最大值的1.5倍。制圖區(qū)域和矩形框邊緣之間的空間填充有平均密度ρˉ，這樣在整個矩形邊框內(nèi)進行變形時，邊緣地區(qū)就不會對制圖區(qū)域產(chǎn)生影響。對于離散傅里葉變換，將大矩形框劃分為較小的正方形網(wǎng)格，使每個小正方形網(wǎng)格足夠覆蓋每張地圖上的地理區(qū)域。

式（3）在數(shù)值上積分，時間步長的選擇決定了估計r(1)的準確度。實現(xiàn)高精度制圖的一種可能策略是采取大量的小步長。通過實驗，本文決定采用一種不同的策略來減少運算時間：在初始積分期間，僅使用適度數(shù)量的自適應(yīng)時間步長。在開始積分前，將中等寬度的高斯模糊應(yīng)用于初始密度來加速收斂。算法的關(guān)鍵點在于使用第一次積分的輸出作為下一次積分的輸入，這樣會更加接近客觀區(qū)域。通過足夠多次的積分，可以得到比較精確的結(jié)果。對于美國的48個州，進行了5次迭代后，即使是華盛頓特區(qū)的極端情況，目標區(qū)域和生成Cartogram區(qū)域的差異僅為0.31%。在印度，進行12次迭代后，安達曼和尼科巴群島目標區(qū)域和Cartogram區(qū)域之間的最大差異為0.72%。這些細小差異是眼睛無法識別出來de，通常將最大面積誤差設(shè)置為<1%。

該算法的運算速度非常快，僅用3.7 s就生成了美國選舉的Cartogram，僅用5.2 s就生成了印度GDP的Cartogram。與傳統(tǒng)擴散方法相比，該算法大大節(jié)省了時間，面積誤差也較小。

4 結(jié)束語

本文算法比傳統(tǒng)的擴散算法計算效率高，但是也存在一些問題需要改進，比如其運算不是基于shp格式的，而是通過原始數(shù)據(jù)坐標來進行的運算，雖然會加快運算速度，但是缺乏操作的簡便性，后期需要在數(shù)據(jù)轉(zhuǎn)換、運算方面開展進一步研究。未來還可以結(jié)合大數(shù)據(jù)來對Cartogram進行進一步創(chuàng)新，從多個維度進行分析，從而推動地圖學的發(fā)展［10］。