專題圖空間點聚合可視化算法研究

丁立國，熊 偉，周 斌

（1.信息工程大學，河南 鄭州 450000；2. 68029 部隊，甘肅 蘭州 730000）

技術熱點研究

專題圖空間點聚合可視化算法研究

丁立國1，熊 偉1，周 斌2

（1.信息工程大學，河南 鄭州 450000；2. 68029 部隊，甘肅 蘭州 730000）

在制作數字專題圖的過程中，當地圖可視區域有大量空間點需要可視化表達時，可通過對這些空間點進行技術綜合，對局部空間點分布規律以及密集性進行提取和抽象的方法，達到利用有限區域較客觀全面地展示空間點目標分布形態的目的。重點介紹了4種空間點聚合算法的聚合原理；根據算法的聚合過程分析了4種算法的優缺點；并從海量空間點的聚合性能和聚合形態兩方面對4種算法進行了測試與對比，最終選取了性能優、可視化效果佳的方格距離點聚合算法作為多重重要防護目標專題圖可視化表達的方法。

空間點聚合；專題圖表達；點聚合算法

隨著技術的不斷發展和數據的大量累積，數字地圖在瀏覽器端或移動App端的應用越來越廣泛，并為用戶提供了多種查詢和顯示方式，其中在地圖上查詢的結果通常以標記點的形式標注[1]。在制作數字專題圖的過程中，存在某些區域有大量點狀標識與對象需要顯示的情況，而在有限范圍內同時顯示這些空間點會相互堆疊和覆蓋，使得用戶難以區分或選取所需目標。為了解決在有限可視區域內和特定縮放級別下準確全面地顯示空間標識信息這一問題，需對這些空間點進行簡化與聚合。空間點聚合是地圖綜合技術的一 種，主要解決地圖中大量點標識可視化的問題[2]。專題圖上的點聚合即用少量特征點或圖標來抽象顯示某一區域范圍內大量類似點標識，以更為有效的方式傳輸或表達地理空間點分布情況，使專題圖顯示更加清晰和明朗。

針對多重重要防護目標專題圖制作過程中遇到的大規模空間點表達與可視化問題，本文研究分析了4 種常用的點聚合算法；并結合專題圖中重要目標數據量的規模，進行了空間點聚合模擬測試。根據測試橫向比較結果，選擇了性能相對較優、顯示效果較佳的聚合算法作為城市多重重要防護目標專題圖的可視化表達方法之一。

1 空間點聚合算法

1.1 基于網格的點聚合算法

其算法原理為先將地圖可視區域劃分為固定尺寸的正方形，每個縮放級別對應相應的正方形大小；然后將在同一網格中的點聚合至該正方形，默認設定聚合點為該正方形的中心；最終聚合后的每個正方形內僅顯示一個聚合點，且在該點上顯示正方形區域內所包含特征點的數量及其他屬性信息等[3-4]。本文將網格大小設為100 px×100 px，以視口區域左上角為起始點，按照矩陣計算各個點所對應的區間，將同一區間的點聚合顯示。

基于網格的點聚合算法運算速度快，每個原始點僅需在所屬區間內計算一次包含關系，無需進行相鄰關系和復雜距離的計算。采用該方法聚合后的點排列規整，分布較均勻；但其缺點也較明顯，有些距離較近、聚合度高的點，會因網格的分界線而被生硬地分在不同的聚合中。此外，聚合點位置選擇的是方形網格的中心，而非多點聚合的質心，這樣聚合出來的點有時無法精確展現原始點分布的規律和特征。如圖1、2所示，聚合前點標識分別分布在多個網格中，其中點6、點8、點9、點10原始密集度較高，但聚合后分布在不同的網格區間，原始分布特征被割裂了。

1.2 基于距離的點聚合算法

其算法原理為根據點與點之間的距離判斷聚合性。對每個點進行距離迭代計算[5]，若被迭代的點與擬聚合點的距離在指定的閾值范圍內，那么被迭代點就聚合到該點，否則就作為一個新的聚合點；每次聚合后需重新計算新的聚合點，新聚合點是迭代點和被聚合點的中心點，如此循環，聚合后的點坐標是多次迭代后多個點的中心點。如圖3、4所示，對各點進行距離迭代計算，原始點1和點2被聚合到新的1號位，原始點3和點4被聚合到2號位，原始點6、點8、點 9、點10被聚合到3號位。基于距離的點聚合算法能較客觀地反映所包含的原始點標識的位置信息，但當點數據量較大時，因其計算內容比基于網格的算法復雜，所需消耗的資源大、響應時間長。

圖1 基于網格的點聚合算法聚合過程

圖2 基于網格的點聚合算法聚合結果

圖3 基于距離的點聚合算法聚合過程

圖4 基于距離的點聚合算法聚合結果

1.3 基于方格距離的點聚合算法

首先以每個點為正方形的中心，外包一個邊長固定的正方形，邊長為用戶初始設置的默認值；再對每個點的外包正方形進行迭代。區別于基于距離的算法，該算法不是計算點與點之間的距離，而是計算各點外包正方形的幾何關系[6]。若迭代點的外包正方形與現有聚合點的外包正方形相交，則把迭代點聚合到該聚合點中；若該迭代點的外包正方形與多個已知聚合點的外包正方形均相交，則比較該點到各聚合點的距離，將其聚合到距離相對較近的聚合點中；若不相交，則新建聚合點，如此循環，直到所有原始點都遍歷完畢。分別在各比例尺下的縮放級別設定不同的外包正方形，再進行遍歷計算。如圖5、6所示，以原始點9為例，原始點9與點7、點8、點10都相交，則計算點9與各相交點的距離，最后點9與距離較近的點8聚合，而點6、點8、點10各兩兩相交，直接聚合而無需計算距離，最終點6、點8、點9、點10被聚合到3號位。基于方格距離的點聚合算法運算速度比基于網格的算法慢，但比基于距離的算法快，每個原始點只需計算一次，僅需計算部分點與點之間的距離，計算出的聚合點能較精確地反映原始點位置分布的疏密特征。需要注意的是，迭代順序的不同會導致最終聚合結果有少許差異，但總體分布特征無顯著變化。

圖5 基于方格距離的點聚合算法聚合過程

圖6 基于方格距離的點聚合算法聚合結果

1.4 基于K-means的點聚合算法

其算法原理為采用兩個對象的距離作為相似性評價指標，兩個對象的距離越近，其相似度越大，將距離近的對象進行聚合[7-8]。首先隨機選取K個種子點，依次計算余下N-K個點到各種子點的距離，將這些點劃歸到相似度高（距離最近）的分組中。根據分組結果，重新計算聚合分組中各自的點群質心作為新的種子點，點群質心為分組中所含點X坐標與Y坐標的均值。重新計算所有空間點P={P1,P2,…,Pn}到每個新的種子點距離，每個空間點Pn得到一組距離Si={Sn1,Sn2,…,Snk}，計算Si中的最小值，則該點就被劃分到距離最小值對應的種子分組。以此類推，每個數據點Pn都被聚合到新的種子點，若新的種子點和對應分組中空間點的距離達到設置的閾值，則認為新的種子點質心位置趨于穩定，空間點聚合過程完成，停止計算。隨機取2個種子點，求其余5個點到這2個種子點的距離，如圖7所示計算距離后，點1、2與上面的種子點劃分為一組，點3、點4、點5與下面的種子點歸為一組，重新計算種子點的質心，確定2個新的種子點，重復計算距離，若新的種子點與空間點的距離達到設定的閾值，則停止計算新的種子質心位置，停止距離計算，聚合完成。圖8為使用K-means算法的聚合計算過程，圖9為使用K-means算法計算后的聚合效果。基于K-means的點聚合算法框架清晰，當聚合點較密集且被聚合的對象之間分布相似、差異明顯時，能確定K個種子劃分達到平方誤差最小時效果最優。該算法在聚合過程中需對樣本反復進行分類調整，不斷計算調整新的種子質心位置，因此當聚合數量較大時，計算量是呈幾何級數增加的，需對算法的時間復雜度進行分析和改進，才能提高該聚合算法的應用范疇。

圖7 基于K-means的點聚合算法模擬演示

圖8 基于K-means的點聚合算法聚合過程

圖9 基于K-means的點聚合算法聚合結果

2 算法實驗與對比測試

2.1 測試對象

某城市的多重重要防護目標專題圖顯示，在該城市中心城區約12 km2范圍內，包含的重要防護目標及掩體數量約為3 000～4 000個，因顯示區域縮放比例尺的變化，數字顯示終端區域內可視目標數量分布從數十到成百上千不等。

2.2 測試環境

在Windows Server 2012網絡環境下開發，構建B/ S服務方式，數據點以Json本地化存儲與網絡傳輸，算法聚合采用JS腳本實現。通過該技術可方便地操作頁面對象，對傳輸到本地的空間點進行實時運算，從而可忽略服務器或網絡等因素對實驗結果的影響。

2.3 測試內容

如圖10所示，在當前模式下，目標分布較為密集，部分目標相互壓蓋，不易選取和查看，視覺效果差。通過使用點聚合算法，對地圖中顯示集中的區域進行聚合處理，即用少量的點或易區分的圖標來展示點分布密集程度，讓專題圖顯示更加直觀清晰。通過橫向比較4種點聚合算法的性能以及聚合后不同比例尺下的分布顯示效果，對該城市同一片區內同等數量的空間點進行聚合測試，比較各算法在不同比例尺下的聚合效率，即在同一顯示區域內對不同顯示級別點目標的聚合性能，以及聚合后的可視化效果是否能較為全面客觀地反映目標分布的集聚特征。

圖10 聚合前的空間點目標分布圖

2.4 測試結果

從圖11中可以看出，當在大比例尺下可視區域內待聚合空間點的數量較少時，各算法在聚合性能上無明顯差異，當比例尺逐步減小，顯示區域內需要聚合的數據量變大時，各算法的實時聚合性能出現明顯差異。基于網格的點聚合算法，聚合性能好、效率高，聚合后的形態分布規整；但展現出的分布形態和聚合后的密集性存在失真現象。基于距離的點聚合算法，計算時間較長，性能比其他算法滯后。基于距離的點聚合算法，時間復雜度呈線性增加。基于K-means的點聚合算法，時間復雜度呈幾何級數增長，隨著聚合量的大幅增加，其聚合效率最低，對系統資源占用和損耗也最大。基于方格距離的聚合算法與基于K-means的點聚合算法相比，在時間損耗、性能表現上基于方格距離的算法有優勢，而在主觀感受上基于K-means的點聚合算法計算后的空間點聚合形態較好，且該算法可根據顯示級別調整聚合的密集度，能根據地圖顯示比例以及可視區域的大小動態變化聚合度，即通過調整種子參數獲得更優化的動態聚合閾值。

圖11 在不同比例尺下各聚合算法的性能對比

本文研究了4種空間點聚合算法，綜合考量各算法的復雜度、運行效率、聚合后的渲染效果，選擇基于方格距離的點聚合算法作為多重重要防護目標聚合可視化專題圖的綜合方法。該算法在運行效率上較優，同時也能客觀全面地反映重要目標的分布形態與特征，易于使用和交互。從圖12可以看出，與圖10相比，聚合后的顯示樣式更加美觀，圖中聚合符號內的數字表示該聚合區域內包含的重要防護目標數量，根據聚合量的大小采用分色與圖標尺寸相結合的顯示樣式來展示該聚合區域的重要防護目標分布密集程度，易于掌握各區域的目標分布權重，為決策提供有力參照。

圖12 基于方格距離的點聚合后的渲染效果

3 結 語

在多重重要防護目標專題圖制作過程中，使用聚合技術對地圖上空間點進行合理可視化表達是一種較優的方案，其實質上是聚合算法在數字專題地圖上的應用創新，不僅減輕了系統渲染海量數據的負荷，而且可以讓用戶從整體上感知海量目標對象的分布特征，為用戶提供了良好的交互體驗。

通過對4種空間點聚合算法的分析，本文選擇基于方格距離的點聚合算法作為專題圖制圖綜合的技術方法，基于現有成果將從兩個方面繼續分析：對不同屬性的目標合理細化，分類聚合分層顯示；優化K-means算法，提高聚合性能。該算法伸縮性較好，當處理大數據聚合時，還需研究如何根據數據量以及期望的聚合效果預先初始化隨機種子點，選擇較合理的點群質心點計算方法，從而減少算法的復雜程度，改進算法的運行效率，以期提出一種更優的點聚合可視化算法。

[1] 郭亞友.數字地圖制圖綜合技術研究[J].測繪標準化, 2011,27(3)：33-36

[2] 郭慶勝,黃遠林,鄭春燕,等.空間推理與漸進式地圖綜合[M].武漢：武漢大學出版社,2007：42

[3] 田啟明,王麗珍,尹群.基于網格距離的聚類算法的設計、實現和應用[J].計算機應用,2005,25(2)：294-296

[4] 劉果.基于網格密度的海量空間點聚合顯示算法[J].測繪與空間地理信息,2015,38(4)：174-176

[5] 戴鳳嬌,肖林華,楊琭,等.基于百度地圖的標記點聚合算法研究[J].中國科技信息,2013(23)：82-85

[6] Habibullayevich, Kholmuradov G, CHEN X. Efficient Filtering and Clustering Mechanism for Google Maps[J].Journal of Advanced Management Science,2013,1(1)：108-111

[7] 周愛武,于亞飛.K-means聚類算法的研究[J].計算機技術與發展,2011,21(2)：62-65

[8] 張建輝.K-means聚類算法研究及應用[D].武漢：武漢理工大學,2007

[9] 何鵬舉.天地圖大規模標注顯示的探討[J].地理空間信息, 2015,13(1)：174-175,179

P208

B

1672-4623（2017）05-0006-04

10.3969/j.issn.1672-4623.2017.0050.2

丁立國，博士研究生，工程師，研究方向為作戰環境學，主要從事GIS網絡服務與專題數據可視化方面研究工作。

2016-07-15。

項目來源：國家自然科學基金資助項目（41271393）；地理信息工程國家重點實驗室重點基金資助項目（SKLGIE2014-Z-4-1）。