胡碧菡 李連營

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗與分析

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

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

圖1 2016美國選舉投票結果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值落后，情況則正好相反。利用基于擴散密度均衡方法構建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等面積圓錐投影將地域邊界的經度和緯度投影到2D空間上，將圖1（a）、圖2（a）嵌入一個Lx Ly的矩形框中，將其邊界作為熱力流動的反射邊界。矩形框大小的選擇需要綜合考慮，在保證Cartogram與邊界條件無關的條件下要盡量減少計算目標區(qū)域投影T的時間。綜合考慮后，矩形框的邊長等于各國南北和東西范圍最大值的1.5倍。制圖區(qū)域和矩形框邊緣之間的空間填充有平均密度ρˉ，這樣在整個矩形邊框內進行變形時，邊緣地區(qū)就不會對制圖區(qū)域產生影響。對于離散傅里葉變換，將大矩形框劃分為較小的正方形網格，使每個小正方形網格足夠覆蓋每張地圖上的地理區(qū)域。

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

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

4 結束語

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