丁立國，熊 偉，周 斌

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

技術(shù)熱點(diǎn)研究

專題圖空間點(diǎn)聚合可視化算法研究

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

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

在制作數(shù)字專題圖的過程中，當(dāng)?shù)貓D可視區(qū)域有大量空間點(diǎn)需要可視化表達(dá)時(shí)，可通過對這些空間點(diǎn)進(jìn)行技術(shù)綜合，對局部空間點(diǎn)分布規(guī)律以及密集性進(jìn)行提取和抽象的方法，達(dá)到利用有限區(qū)域較客觀全面地展示空間點(diǎn)目標(biāo)分布形態(tài)的目的。重點(diǎn)介紹了4種空間點(diǎn)聚合算法的聚合原理；根據(jù)算法的聚合過程分析了4種算法的優(yōu)缺點(diǎn)；并從海量空間點(diǎn)的聚合性能和聚合形態(tài)兩方面對4種算法進(jìn)行了測試與對比，最終選取了性能優(yōu)、可視化效果佳的方格距離點(diǎn)聚合算法作為多重重要防護(hù)目標(biāo)專題圖可視化表達(dá)的方法。

空間點(diǎn)聚合；專題圖表達(dá)；點(diǎn)聚合算法

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

針對多重重要防護(hù)目標(biāo)專題圖制作過程中遇到的大規(guī)?？臻g點(diǎn)表達(dá)與可視化問題，本文研究分析了4 種常用的點(diǎn)聚合算法；并結(jié)合專題圖中重要目標(biāo)數(shù)據(jù)量的規(guī)模，進(jìn)行了空間點(diǎn)聚合模擬測試。根據(jù)測試橫向比較結(jié)果，選擇了性能相對較優(yōu)、顯示效果較佳的聚合算法作為城市多重重要防護(hù)目標(biāo)專題圖的可視化表達(dá)方法之一。

1 空間點(diǎn)聚合算法

1.1 基于網(wǎng)格的點(diǎn)聚合算法

其算法原理為先將地圖可視區(qū)域劃分為固定尺寸的正方形，每個(gè)縮放級別對應(yīng)相應(yīng)的正方形大?。蝗缓髮⒃谕痪W(wǎng)格中的點(diǎn)聚合至該正方形，默認(rèn)設(shè)定聚合點(diǎn)為該正方形的中心；最終聚合后的每個(gè)正方形內(nèi)僅顯示一個(gè)聚合點(diǎn)，且在該點(diǎn)上顯示正方形區(qū)域內(nèi)所包含特征點(diǎn)的數(shù)量及其他屬性信息等[3-4]。本文將網(wǎng)格大小設(shè)為100 px×100 px，以視口區(qū)域左上角為起始點(diǎn)，按照矩陣計(jì)算各個(gè)點(diǎn)所對應(yīng)的區(qū)間，將同一區(qū)間的點(diǎn)聚合顯示。

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

1.2 基于距離的點(diǎn)聚合算法

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

圖1 基于網(wǎng)格的點(diǎn)聚合算法聚合過程

圖2 基于網(wǎng)格的點(diǎn)聚合算法聚合結(jié)果

圖3 基于距離的點(diǎn)聚合算法聚合過程

圖4 基于距離的點(diǎn)聚合算法聚合結(jié)果

1.3 基于方格距離的點(diǎn)聚合算法

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

圖5 基于方格距離的點(diǎn)聚合算法聚合過程

圖6 基于方格距離的點(diǎn)聚合算法聚合結(jié)果

1.4 基于K-means的點(diǎn)聚合算法

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

圖7 基于K-means的點(diǎn)聚合算法模擬演示

圖8 基于K-means的點(diǎn)聚合算法聚合過程

圖9 基于K-means的點(diǎn)聚合算法聚合結(jié)果

2 算法實(shí)驗(yàn)與對比測試

2.1 測試對象

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

2.2 測試環(huán)境

在Windows Server 2012網(wǎng)絡(luò)環(huán)境下開發(fā)，構(gòu)建B/ S服務(wù)方式，數(shù)據(jù)點(diǎn)以Json本地化存儲(chǔ)與網(wǎng)絡(luò)傳輸，算法聚合采用JS腳本實(shí)現(xiàn)。通過該技術(shù)可方便地操作頁面對象，對傳輸?shù)奖镜氐目臻g點(diǎn)進(jìn)行實(shí)時(shí)運(yùn)算，從而可忽略服務(wù)器或網(wǎng)絡(luò)等因素對實(shí)驗(yàn)結(jié)果的影響。

2.3 測試內(nèi)容

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

圖10 聚合前的空間點(diǎn)目標(biāo)分布圖

2.4 測試結(jié)果

從圖11中可以看出，當(dāng)在大比例尺下可視區(qū)域內(nèi)待聚合空間點(diǎn)的數(shù)量較少時(shí)，各算法在聚合性能上無明顯差異，當(dāng)比例尺逐步減小，顯示區(qū)域內(nèi)需要聚合的數(shù)據(jù)量變大時(shí)，各算法的實(shí)時(shí)聚合性能出現(xiàn)明顯差異?；诰W(wǎng)格的點(diǎn)聚合算法，聚合性能好、效率高，聚合后的形態(tài)分布規(guī)整；但展現(xiàn)出的分布形態(tài)和聚合后的密集性存在失真現(xiàn)象。基于距離的點(diǎn)聚合算法，計(jì)算時(shí)間較長，性能比其他算法滯后?；诰嚯x的點(diǎn)聚合算法，時(shí)間復(fù)雜度呈線性增加?；贙-means的點(diǎn)聚合算法，時(shí)間復(fù)雜度呈幾何級數(shù)增長，隨著聚合量的大幅增加，其聚合效率最低，對系統(tǒng)資源占用和損耗也最大?；诜礁窬嚯x的聚合算法與基于K-means的點(diǎn)聚合算法相比，在時(shí)間損耗、性能表現(xiàn)上基于方格距離的算法有優(yōu)勢，而在主觀感受上基于K-means的點(diǎn)聚合算法計(jì)算后的空間點(diǎn)聚合形態(tài)較好，且該算法可根據(jù)顯示級別調(diào)整聚合的密集度，能根據(jù)地圖顯示比例以及可視區(qū)域的大小動(dòng)態(tài)變化聚合度，即通過調(diào)整種子參數(shù)獲得更優(yōu)化的動(dòng)態(tài)聚合閾值。

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

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

圖12 基于方格距離的點(diǎn)聚合后的渲染效果

3 結(jié) 語

在多重重要防護(hù)目標(biāo)專題圖制作過程中，使用聚合技術(shù)對地圖上空間點(diǎn)進(jìn)行合理可視化表達(dá)是一種較優(yōu)的方案，其實(shí)質(zhì)上是聚合算法在數(shù)字專題地圖上的應(yīng)用創(chuàng)新，不僅減輕了系統(tǒng)渲染海量數(shù)據(jù)的負(fù)荷，而且可以讓用戶從整體上感知海量目標(biāo)對象的分布特征，為用戶提供了良好的交互體驗(yàn)。

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

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

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

[3] 田啟明,王麗珍,尹群.基于網(wǎng)格距離的聚類算法的設(shè)計(jì)、實(shí)現(xiàn)和應(yīng)用[J].計(jì)算機(jī)應(yīng)用,2005,25(2)：294-296

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

[5] 戴鳳嬌,肖林華,楊琭,等.基于百度地圖的標(biāo)記點(diǎn)聚合算法研究[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].計(jì)算機(jī)技術(shù)與發(fā)展,2011,21(2)：62-65

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

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

P208

B

1672-4623（2017）05-0006-04

10.3969/j.issn.1672-4623.2017.0050.2

丁立國，博士研究生，工程師，研究方向?yàn)樽鲬?zhàn)環(huán)境學(xué)，主要從事GIS網(wǎng)絡(luò)服務(wù)與專題數(shù)據(jù)可視化方面研究工作。

2016-07-15。

項(xiàng)目來源：國家自然科學(xué)基金資助項(xiàng)目（41271393）；地理信息工程國家重點(diǎn)實(shí)驗(yàn)室重點(diǎn)基金資助項(xiàng)目（SKLGIE2014-Z-4-1）。