傅晨恩,陳 瓊
中電??导瘓F有限公司,杭州 311100
隨著物聯(lián)網(wǎng)應(yīng)用技術(shù)的發(fā)展,廣泛使用的移動設(shè)備和傳感器每時每刻都產(chǎn)生海量的地理空間數(shù)據(jù)[1],如何從海量數(shù)據(jù)中提取出有用、可靠、可知識化的綜合信息,并通過信息可視化的方式表達、展示和分析,成為研究者們關(guān)注的一個熱點[2]。
在基于B/S架構(gòu)的Web GIS系統(tǒng)中,海量數(shù)據(jù)的可視化,指的是在電子地圖有限的顯示區(qū)域內(nèi)展示海量的地圖標(biāo)記物。這里涉及既要看到全局信息,又要能夠明晰細節(jié),看全局需要點聚合,看細節(jié)需要散開。
對于空間點聚合算法,有基于網(wǎng)格的[3-5]、基于距離的[6]、基于方格距離的,還有基于K-means的[7]。丁立國等人[8]針對上述四種算法進行了研究,并從海量空間點的聚合性能和聚合形態(tài)兩個方面進行測試和對比,最終選取了方格距離點聚合算法。但是丁立國等人僅僅是從聚合計算過程來分析算法的優(yōu)劣,其實一個計算方法包含時間復(fù)雜度和空間復(fù)雜度,現(xiàn)如今計算存儲設(shè)備是如此普惠,以至于可以利用空間換時間的方式,通過增加空間索引來提高時間運行效率。事實上,空間索引技術(shù)是解決海量數(shù)據(jù)快速檢索、查詢和訪問的重要手段[9]。另外,在實時交互性[10]場景下,分析可能需要實時,計算不一定要實時,所以可通過預(yù)處理來進一步提高計算效率。Habibullayevich等人[11]描述了一種基于網(wǎng)格和點密度的在線Google地圖的點聚合方案,通過網(wǎng)格進行劃分點集,通過點密度算法處理重疊問題,但是需要對所有的點逐一計算進行聚合,如果聚合點的數(shù)量較大時,計算量是呈幾何級數(shù)增加的。對于空間點散開顯示的算法,章鵬等人[12]給出了一種利用網(wǎng)格實現(xiàn)的算法用于大規(guī)模點的可視化展示,采用基于排序的思想進行過濾重疊點,但忽略了可以利用的空間信息。Kwon等人[13]提出采樣算法來消除重疊,但是缺少聚合的處理過程。
針對現(xiàn)有研究的不足,本文提出了一種采用分層的網(wǎng)格劃分來實現(xiàn)對海量地圖標(biāo)記物的聚合算法以及基于網(wǎng)格過濾方法實現(xiàn)對散開重疊點去重。
在電子地圖展示海量地圖標(biāo)記物時,隨著比例尺的縮放,在小比例尺下,海量的地圖標(biāo)記物會擠壓堆疊在一起,如圖1所示,用戶體驗很差,而且很難從這里面分析出有效信息。通常這時會選擇點聚合方案,但是純粹的點聚合運算隨著比例尺的縮小,待聚合點會越來越多,計算開銷顯著增加。此外,在大比例尺下,需要散開展示時,海量的地圖標(biāo)記物也會存在重疊現(xiàn)象,這對于用戶交互帶來了麻煩,譬如,點擊重疊的標(biāo)記物,到底誰先響應(yīng)。
圖1 海量標(biāo)記物堆疊Fig.1 Massive markers stacking
本文假設(shè)海量地圖標(biāo)記物是靜態(tài)的點要素,基于該假設(shè)提出一種采用分層的網(wǎng)格劃分來實現(xiàn)對海量地圖標(biāo)記物的聚散可視化方法。
圖2給出了方法的總體流程圖,主要概括為4個步驟:
圖2 方法整體流程Fig.2 Overall process of method
(1)對設(shè)定區(qū)域進行網(wǎng)格劃分,并定義網(wǎng)格屬性;
(2)確定聚散層級計算規(guī)則;
(3)獲取當(dāng)前地圖的縮放等級zoom,并根據(jù)聚散層級計算規(guī)則確定當(dāng)前為高層級聚合展示、低層級聚合展示或散開展示;
(4)條件判斷:
①若為高層級聚合展示,則獲取高層級聚合信息并進行展示;
②若為低層級聚合展示,則獲取低層級聚合信息并進行展示;
③若為散開展示,則過濾將要展示的重疊點,進行優(yōu)化后展示。
在海量地圖標(biāo)記物的聚散可視化展示中,必不可少的是獲取海量空間點信息,進行相應(yīng)處理后再存儲,為后期搜索建立基礎(chǔ)。
在建立搜索基礎(chǔ)時,首先對設(shè)定區(qū)域進行分層的網(wǎng)格劃分,網(wǎng)格可以不規(guī)則,根據(jù)劃分所得的網(wǎng)格的層級和中心點進行編碼,同時對網(wǎng)格的中心點信息建立靜態(tài)索引。當(dāng)然,網(wǎng)格的構(gòu)造要以顯示器分辨率和地圖標(biāo)記物可清晰分辨為原則,拆分網(wǎng)格要取整。
在網(wǎng)格劃分中,層級最低是1層,若層級為大于1級,則需將層級劃分為與高級聚合展示對應(yīng)的高層級,以及與低級聚合展示對應(yīng)的低層級,不同的層級中包含有不同的網(wǎng)格中心點信息。需要說明的是,此處所述的高層級與低層級僅為相對概念,用于區(qū)別聚合程度的不同。高層級應(yīng)理解為聚合程度較高的一類層級,即高層級中可包含多個不同級別的層級;同理,低層級應(yīng)理解為聚合程度較低的一類層級,即低層級中可包含多個不同級別的層級。
在進行編碼時,編碼規(guī)則推薦但不限于“層級代碼+網(wǎng)格代碼”的形式;網(wǎng)格中心點所建立的靜態(tài)索引為K-D樹[14]索引。
而后獲取所述設(shè)定區(qū)域內(nèi)的標(biāo)記物信息,按照網(wǎng)格的編碼進行統(tǒng)計,并將統(tǒng)計信息(Key-Value形式)保存至Key-Value數(shù)據(jù)庫(例如Redis),同時對獲取的標(biāo)記物信息建立動態(tài)索引,該動態(tài)索引為四叉樹索引[15]。
為了便于理解,本文以常見的電子地圖,譬如百度為例進行說明。百度地圖縮放等級zoom有19級(3~21),確定3~4級為高層級聚合(世界地圖范圍)、5~11級為低層級聚合(中國區(qū)域范圍),12~21級(城市區(qū)域范圍)為散開展示等,需要說明的是,聚散層級計算規(guī)則可以根據(jù)實際采用的電子地圖以及應(yīng)用場景需要進行確定。
在進行地圖標(biāo)記物的聚散可視化展示時,獲取地圖當(dāng)前的縮放等級zoom,并結(jié)合預(yù)設(shè)的聚散層級計算規(guī)則確定當(dāng)前為聚合展示或散開展示,若為聚合展示,還需明確是高級聚合展示或低級聚合展示,以便于獲取對應(yīng)的展示信息。
在根據(jù)當(dāng)前地圖的縮放級別zoom計算得到聚散層級之后,若為聚合展示,則執(zhí)行如下算法。
算法1
輸入:當(dāng)前地圖的縮放級別zoom和可視區(qū)域的像素坐標(biāo)范圍(左上角到右下角所框定的矩形區(qū)域)ViewRectArea;
1.按照2.1節(jié)中的網(wǎng)格定義,進行分層網(wǎng)格中心點的獲取和存儲,中心點信息存儲到數(shù)據(jù)庫中,譬如MySQL,網(wǎng)格的中心點信息包括網(wǎng)格對應(yīng)的層級Level和網(wǎng)格中心點的經(jīng)緯度信息Pos;
2.對存儲的中心點信息建立K-D樹索引,該索引為靜態(tài)的;
3.獲取海量地圖標(biāo)記物信息,包含位置信息,所屬網(wǎng)格編碼等,并存儲到數(shù)據(jù)庫中,同時在入庫過程中,對海量地圖標(biāo)記物進行分類,以鍵值對(Key-Value)形式,即“網(wǎng)格編碼-統(tǒng)計數(shù)量”存到Key-Value數(shù)據(jù)庫,譬如Redis;
4.對存儲的海量地圖標(biāo)記物信息建立四叉樹索引,該索引為動態(tài)的,每次有標(biāo)記物增刪改時,會動態(tài)更新(可選);
5.根據(jù)zoom和確定的聚散層級計算規(guī)則Rule,可以確定要展示的對應(yīng)層級Level;
6.按照瓦片地圖的坐標(biāo)轉(zhuǎn)換算法[16-18],可以得到ViewRect-Area對應(yīng)的可視區(qū)域的經(jīng)緯度范圍LonlatRectArea;
7.根據(jù)LonlatRectArea和靜態(tài)索引(K-D樹),可以快速查詢到可視區(qū)域內(nèi)對應(yīng)層級Level下的網(wǎng)格的中心點信息集合Slevel,Slevel={Pos1,Pos2,…,Posn},Posi為第i個中心點信息,其中包含網(wǎng)格編碼和經(jīng)緯度信息;
8.對于Slevel中的每一個中心點,查詢Key-Value數(shù)據(jù)庫,Key為中心點的編碼,Value為該中心點對應(yīng)的聚合點數(shù)量的統(tǒng)計值,綜合可以得到聚合點集合Saggregation,Saggregation={APos1,APos2,…,APosn},APosi為第i個聚合點信息,其中包含經(jīng)緯度和統(tǒng)計量。
下面結(jié)合服務(wù)器和瀏覽器的交互,如圖3所示,對算法進行詳述。
圖3 聚合展示交互時序圖Fig.3 Clustering display interactive sequence diagram
算法1的輸入是當(dāng)前地圖的縮放級別和可視區(qū)域的像素坐標(biāo)范圍,輸出是聚合點集合。具體是瀏覽器發(fā)送區(qū)域查詢請求,服務(wù)器返回聚合結(jié)果,然后在瀏覽器頁面展示。
第1~4步運行在服務(wù)器端。第1步是初始化網(wǎng)格信息,并進行持久化存儲,網(wǎng)格信息只需初始化一次;第2步是數(shù)據(jù)預(yù)處理過程,即對已有的網(wǎng)格數(shù)據(jù)構(gòu)建K-D樹索引,便于快速查詢,這里選擇采用K-D樹,原因有二,其一是K-D樹非常適合于空間點集數(shù)據(jù)。其二,相比于四叉樹、R樹[19],K-D樹在空間復(fù)雜度和時間復(fù)雜度上都是比較折中的。此外,構(gòu)建K-D樹不需要動態(tài)構(gòu)建,可以預(yù)先進行構(gòu)建,構(gòu)建時注意選擇空間點中的中位數(shù)作為切分點,這樣構(gòu)建出來的K-D樹是平衡的;前兩步可以統(tǒng)稱為“構(gòu)建索引”。第3步是統(tǒng)計預(yù)處理過程,即存儲海量地圖標(biāo)記物的同時,按照網(wǎng)格編碼進行統(tǒng)計并持久化到Key-Value數(shù)據(jù)庫,可以稱為“分類統(tǒng)計”;“構(gòu)建索引”和“分類統(tǒng)計”可以并行;第4步是對數(shù)據(jù)進行預(yù)處理,便于后續(xù)散開展示時快速查詢,這里選擇采用四叉樹,是出于性能上考慮,因為面對需要數(shù)據(jù)動態(tài)更新的場景,要求索引能夠快速構(gòu)建,K-D樹需要打破重建,而四叉樹可以增量構(gòu)建。這一步也可以在散開展示算法中進行(見算法2步驟2),所以可選,在圖3中沒有列出;第5~6步運行在瀏覽器端,第5步是確定層級Level,即是高層級聚合還是低層級聚合;第6步是可視區(qū)域像素坐標(biāo)轉(zhuǎn)化為經(jīng)緯度坐標(biāo);第7~8步運行在服務(wù)器端,第7步是區(qū)域查詢,輸出為可視區(qū)域內(nèi)對應(yīng)層級Level下的網(wǎng)格的中心點信息集合Slevel。在預(yù)先構(gòu)建K-D樹索引的基礎(chǔ)上,可以快速查詢指定區(qū)域下包含哪些空間點(Slevel={Pos1,Pos2,…,Posn}),但是這些空間點僅僅包含位置信息,沒有統(tǒng)計量(該位置包含的點數(shù)量);第8步是合并查詢結(jié)果,即對Slevel中的每個點進行遍歷,根據(jù)每個點中的網(wǎng)格編碼,查詢第3步中存儲在Key-Value數(shù)據(jù)庫中的信息,得到每個Key(網(wǎng)格編碼),對應(yīng)的Value(統(tǒng)計數(shù)量),合并結(jié)果,即得到每個點的統(tǒng)計量,輸出目標(biāo)結(jié)果聚合點集合Saggregation。最后返回給瀏覽器進行展示。
在根據(jù)當(dāng)前地圖的縮放級別zoom計算得到聚散層級之后,若為散開展示,則執(zhí)行如下算法。
算法2
輸入:當(dāng)前地圖的縮放級別zoom和可視區(qū)域的像素坐標(biāo)范圍ViewRectArea;
1.獲取海量地圖標(biāo)記物信息,包含經(jīng)緯度、圖標(biāo)、屬性信息(可選);
2.對地圖標(biāo)記物信息進行持久化到數(shù)據(jù)庫,包含經(jīng)緯度和基本信息,在錄入的同時建立四叉樹索引,該索引為動態(tài)索引;
3.根據(jù)zoom和確定的聚散層級計算規(guī)則Rule,可以確定要散開展示;
4.按照瓦片地圖的坐標(biāo)轉(zhuǎn)換算法,可以得到ViewRectArea對應(yīng)的可視區(qū)域的經(jīng)緯度范圍LonlatRectArea;
5.根據(jù)LonlatRectArea和動態(tài)索引(四叉樹),可以快速查詢到可視區(qū)域內(nèi)地圖標(biāo)記物中心點位置信息集合Smarkers,Smarkers={M1,M2,…,Mn},其中Mi為第i個標(biāo)記物;
6.利用網(wǎng)格過濾算法,依據(jù)后進先出的原則,對地圖標(biāo)記物集合Smarkers進行篩選,具體的網(wǎng)格過濾算法,采用如下步驟:
(1)假設(shè)展示區(qū)域的標(biāo)記物圖標(biāo)的尺寸為P×Q像素單位,且該像素的坐標(biāo)點位于標(biāo)記物圖標(biāo)的中心位置;
(2)假設(shè)展示區(qū)域的分辨率為S×T像素單位,結(jié)合圖標(biāo)緩存為P×Q像素單位,將展示區(qū)域劃分為(S/2P)×(T/2Q)個網(wǎng)格;
(3)對于每一個網(wǎng)格,采用基于幾何拓撲關(guān)系的點與面相交運算[20],選出位于同一網(wǎng)格中的標(biāo)記物信息,依據(jù)后進先出原則去除重疊的標(biāo)記物信息,得到篩選后的標(biāo)記物信息。
輸出:篩選后的地圖標(biāo)記物集合Sfilter_markers,Sfilter_markers={M1,M2,…,Mm},m≤n。
下面結(jié)合服務(wù)器和瀏覽器的交互,如圖4所示,對算法進行詳述。
圖4 散開展示交互時序圖Fig.4 Scattering display interactive sequence diagram
算法2的輸入和算法1一樣,輸出是經(jīng)過篩選后的地圖標(biāo)記物集合。第1~2步運行在服務(wù)器端,第1步是獲取海量數(shù)據(jù),可以通過在線采集或者客戶提供,這一過程可以在聚合展示階段進行(見算法1步驟3),所以可選,在圖4中沒有列出;第2步是數(shù)據(jù)持久化和預(yù)處理,這里對海量數(shù)據(jù)點構(gòu)建的數(shù)據(jù)結(jié)構(gòu)為四叉樹,便于動態(tài)更新;第3~4步運行在瀏覽器端,第3步是確定為散開展示;第4步是可視區(qū)域像素坐標(biāo)轉(zhuǎn)化為經(jīng)緯度坐標(biāo);第5步是區(qū)域查詢,運行在服務(wù)器端,輸出為可視區(qū)域內(nèi)地圖標(biāo)記物中心點位置信息集合Smarkers;第6步是過濾重疊,運行在瀏覽器端,主要是針對圖標(biāo)堆疊,核心是利用幾何拓撲關(guān)系的點面相交運算,開源代碼庫turf.js里面提供了booleanPointInPolygon方法[21]。即地圖標(biāo)記物坐標(biāo)(點)與圖標(biāo)緩存區(qū)域(面)相交超過兩次,只算第一次,后進的先出。最終可以得到不含重疊的地圖標(biāo)記物集合Sfilter_markers。最后在瀏覽器頁面進行展示。
本實驗的主要目的是評價海量地圖標(biāo)記物聚散可視化算法的有效性,主要圍繞以下兩個問題展開:(1)測試算法對于海量地圖標(biāo)記物展示的可行性;(2)與已有聚合算法的性能進行對比,以及在散開展示時增加網(wǎng)格過濾對性能有無影響。
本文利用在線百度地圖開放平臺提供的行政區(qū)查詢接口[22],可以獲得全國23個省、4個直轄市、5個自治區(qū)和2個特別行政區(qū)的本級以及向下三級(到街道級)的行政區(qū)中心點信息(行政區(qū)劃碼、經(jīng)緯度),并持久化到MySQL數(shù)據(jù)庫,將行政區(qū)劃作為一種網(wǎng)格劃分,網(wǎng)格編碼為行政區(qū)劃碼,該網(wǎng)格劃分具有分層的屬性(省級、市級、區(qū)縣級、街道級)。通過模擬,在浙江省范圍內(nèi)隨機生成100萬的地圖標(biāo)記物,將這100萬的地圖標(biāo)記物數(shù)據(jù)作為測試數(shù)據(jù)。
采用如下規(guī)則計算聚散層級:當(dāng)前的地圖縮放級別zoom取值為3~21,其中3~9級為省級聚合,10~12級為市級聚合,12~14級為區(qū)縣級聚合,15以上為散開展示。在聚合層級中,省級聚合和市級聚合可理解為高層級聚合,區(qū)縣級聚合可理解為低層級聚合。
本次實驗在Windows 10系統(tǒng)進行。采用主流的Chrome瀏覽器,數(shù)據(jù)庫為MySQL,Key-Value數(shù)據(jù)庫為Redis,構(gòu)建B/S服務(wù)方式,算法運行在JVM環(huán)境。依據(jù)上述計算聚散層級規(guī)則和網(wǎng)格劃分,對100萬測試數(shù)據(jù)進行展示。實驗配置環(huán)境如表1所示。
表1 實驗環(huán)境配置Table 1 Experimental environment configuration
首先對MySQL中分層的網(wǎng)格劃分數(shù)據(jù)庫表,也就是省級、市級和區(qū)縣級的行政區(qū)中心點數(shù)據(jù),構(gòu)建K-D樹索引,持久化100萬地圖標(biāo)記測試數(shù)據(jù)到MySQL數(shù)據(jù)庫,同時將地圖標(biāo)記物的分類計數(shù)統(tǒng)計信息按照行政區(qū)劃,以鍵值對形式(網(wǎng)格編碼-統(tǒng)計個數(shù))存到Redis數(shù)據(jù)庫。然后對100萬地圖標(biāo)記測試數(shù)據(jù)構(gòu)建四叉樹索引。最后在Chrome瀏覽器中進行交互查詢。
對于不同的地圖縮放級別zoom,對應(yīng)的聚合信息也會顯示不同,高級別的縮放等級,對應(yīng)的是較高等級的行政級別聚合信息,譬如市級聚合信息,如圖5所示即為市級的聚合在百度地圖上渲染,圖中A點的展示信息為市1∶87 864家,圖中B點的展示信息為市2∶912 109家。
圖5 市級聚合Fig.5 City-level clustering
低級別的縮放等級,對應(yīng)的是較低等級的行政級別聚合信息,譬如區(qū)縣聚合信息,如圖6所示即為區(qū)縣級的聚合在百度地圖上渲染,圖中C點的展示信息為縣1∶329 984家,圖中D點的展示信息為區(qū)1∶296 122家,圖中E點的展示信息為區(qū)2∶286 003家。
圖6 區(qū)縣級聚合Fig.6 District and county level clustering
當(dāng)達到散開展示的縮放等級時,對比兩種情況,未使用和已使用網(wǎng)格過濾算法,展示效果如圖7、8所示。
圖7 散開展示未過濾Fig.7 Scattering display without filtering
圖8 散開展示已過濾Fig.8 Scattering display with filtering
通過上述實驗過程,可以看出,分層的網(wǎng)格劃分聚散可視化方法對于100萬數(shù)據(jù)的海量地圖標(biāo)記物是可行的,效果有效。
接下來,還需要對比已有算法的性能,本文選擇文獻[8]中涉及的算法,即距離點聚合算法和K-means點聚合算法在相同數(shù)量級、相同縮放級別(顯示比例)下的響應(yīng)時間進行對比。
表2展示了縮放等級和顯示比例的對應(yīng)關(guān)系。表3展示了不同的縮放等級下最多包含的地圖標(biāo)記物數(shù)量。
表2 縮放等級和顯示比例尺對應(yīng)關(guān)系Table 2 Correspondence between zoom level and display scale
表3 縮放等級和地圖點數(shù)量Table 3 Zoom level and number of map points
結(jié)合表2和表3可以看出,隨著縮放等級的增加,比例尺也增加,對應(yīng)的可視區(qū)域所含地圖點數(shù)量在減少,而且這里的數(shù)量是針對本實驗案例的數(shù)量,可以用作數(shù)量級參考,比如縮放等級zoom為17,即對應(yīng)的顯示比例尺為1∶500,所含地圖點為900左右數(shù)量級。本實驗選擇zoom為12~17作為參照對比的對象。
從圖9、10可以看出,在大比例尺下可視區(qū)域內(nèi)待聚合空間點的數(shù)量較少時,本文所提算法和其他算法相比并無明顯優(yōu)勢,當(dāng)比例尺逐步減少,顯示區(qū)域內(nèi)需要聚合的數(shù)據(jù)量變大時,本文所提算法相較其他算法,體現(xiàn)出明顯優(yōu)勢。觀察走勢,基于距離的點聚合算法,時間復(fù)雜度呈線性增加,基于K-means的點聚合算法,時間復(fù)雜度呈幾何級數(shù)增加,本文所提算法,依靠索引,穩(wěn)定在固定值左右,幾乎不會增加。
圖9 與基于距離的點聚合對比Fig.9 Comparison with distance-based points clustering
表4可以看出,在散開展示時增加過濾算法,對整體性能影響不是很大,整體延時(100 ms以內(nèi))在用戶體驗可接受的范圍之內(nèi)。
圖10 與基于K-means的點聚合對比Fig.10 Comparison with points clustering based on K-means
表4 散開過濾算法耗時對比Table 4 Time-consuming comparison of diffuse filtering algorithms
在海量空間標(biāo)記物的場景下,地圖可視化技術(shù)提供了一種直觀和全面的展示和分析手段,用于觀測海量數(shù)據(jù)下的整體趨勢和分布以及某些特定區(qū)域的細節(jié)數(shù)據(jù)?,F(xiàn)有的可視化手段,仍然存在一些問題。本文提出了一種分層的網(wǎng)格劃分方法來實現(xiàn)海量空間標(biāo)記物的聚散一體可視化解決方案,主要利用了索引技術(shù)和存儲,加快了整體查詢效率,利用空間拓撲運算,實現(xiàn)了重疊標(biāo)記物的去重,從而為用戶提供了良好的交互體驗。
然而在實驗過程中發(fā)現(xiàn)仍有一些地方可以改進:一是分層機制沒有統(tǒng)一的標(biāo)準(zhǔn),目前都是基于實際場景需求而定,譬如同一個zoom級別下,有些場景是聚合,有些場景就要散開;二是網(wǎng)格劃分的好壞沒有統(tǒng)一的批判標(biāo)準(zhǔn),目前常用的基于地形邊界和基于行政區(qū)劃的網(wǎng)格劃分都是依據(jù)經(jīng)驗和工程效果來確定的;三是索引技術(shù)還有進一步提升的空間,譬如增加二級索引或稱輔助索引(secondary index)[23],同時還可以增加布隆過濾器。但是這里面就涉及性能和效率的權(quán)衡問題。以上這些在實驗中暴露的問題,后續(xù)將進一步進行研究。