分層網格劃分實現(xiàn)海量地圖標記物聚散可視化

傅晨恩，陳 瓊

中電?？导瘓F有限公司，杭州 311100

隨著物聯(lián)網應用技術的發(fā)展，廣泛使用的移動設備和傳感器每時每刻都產生海量的地理空間數據[1]，如何從海量數據中提取出有用、可靠、可知識化的綜合信息，并通過信息可視化的方式表達、展示和分析，成為研究者們關注的一個熱點[2]。

在基于B/S架構的Web GIS系統(tǒng)中，海量數據的可視化，指的是在電子地圖有限的顯示區(qū)域內展示海量的地圖標記物。這里涉及既要看到全局信息，又要能夠明晰細節(jié)，看全局需要點聚合，看細節(jié)需要散開。

對于空間點聚合算法，有基于網格的[3-5]、基于距離的[6]、基于方格距離的，還有基于K-means的[7]。丁立國等人[8]針對上述四種算法進行了研究，并從海量空間點的聚合性能和聚合形態(tài)兩個方面進行測試和對比，最終選取了方格距離點聚合算法。但是丁立國等人僅僅是從聚合計算過程來分析算法的優(yōu)劣，其實一個計算方法包含時間復雜度和空間復雜度，現(xiàn)如今計算存儲設備是如此普惠，以至于可以利用空間換時間的方式，通過增加空間索引來提高時間運行效率。事實上，空間索引技術是解決海量數據快速檢索、查詢和訪問的重要手段[9]。另外，在實時交互性[10]場景下，分析可能需要實時，計算不一定要實時，所以可通過預處理來進一步提高計算效率。Habibullayevich等人[11]描述了一種基于網格和點密度的在線Google地圖的點聚合方案，通過網格進行劃分點集，通過點密度算法處理重疊問題，但是需要對所有的點逐一計算進行聚合，如果聚合點的數量較大時，計算量是呈幾何級數增加的。對于空間點散開顯示的算法，章鵬等人[12]給出了一種利用網格實現(xiàn)的算法用于大規(guī)模點的可視化展示，采用基于排序的思想進行過濾重疊點，但忽略了可以利用的空間信息。Kwon等人[13]提出采樣算法來消除重疊，但是缺少聚合的處理過程。

針對現(xiàn)有研究的不足，本文提出了一種采用分層的網格劃分來實現(xiàn)對海量地圖標記物的聚合算法以及基于網格過濾方法實現(xiàn)對散開重疊點去重。

1 問題描述

在電子地圖展示海量地圖標記物時，隨著比例尺的縮放，在小比例尺下，海量的地圖標記物會擠壓堆疊在一起，如圖1所示，用戶體驗很差，而且很難從這里面分析出有效信息。通常這時會選擇點聚合方案，但是純粹的點聚合運算隨著比例尺的縮小，待聚合點會越來越多，計算開銷顯著增加。此外，在大比例尺下，需要散開展示時，海量的地圖標記物也會存在重疊現(xiàn)象，這對于用戶交互帶來了麻煩，譬如，點擊重疊的標記物，到底誰先響應。

圖1 海量標記物堆疊Fig.1 Massive markers stacking

2 研究方法

本文假設海量地圖標記物是靜態(tài)的點要素，基于該假設提出一種采用分層的網格劃分來實現(xiàn)對海量地圖標記物的聚散可視化方法。

圖2給出了方法的總體流程圖，主要概括為4個步驟：

圖2 方法整體流程Fig.2 Overall process of method

（1）對設定區(qū)域進行網格劃分，并定義網格屬性；

（2）確定聚散層級計算規(guī)則；

（3）獲取當前地圖的縮放等級zoom，并根據聚散層級計算規(guī)則確定當前為高層級聚合展示、低層級聚合展示或散開展示；

（4）條件判斷：

①若為高層級聚合展示，則獲取高層級聚合信息并進行展示；

②若為低層級聚合展示，則獲取低層級聚合信息并進行展示；

③若為散開展示，則過濾將要展示的重疊點，進行優(yōu)化后展示。

2.1 定義網格

在海量地圖標記物的聚散可視化展示中，必不可少的是獲取海量空間點信息，進行相應處理后再存儲，為后期搜索建立基礎。

在建立搜索基礎時，首先對設定區(qū)域進行分層的網格劃分，網格可以不規(guī)則，根據劃分所得的網格的層級和中心點進行編碼，同時對網格的中心點信息建立靜態(tài)索引。當然，網格的構造要以顯示器分辨率和地圖標記物可清晰分辨為原則，拆分網格要取整。

在網格劃分中，層級最低是1層，若層級為大于1級，則需將層級劃分為與高級聚合展示對應的高層級，以及與低級聚合展示對應的低層級，不同的層級中包含有不同的網格中心點信息。需要說明的是，此處所述的高層級與低層級僅為相對概念，用于區(qū)別聚合程度的不同。高層級應理解為聚合程度較高的一類層級，即高層級中可包含多個不同級別的層級；同理，低層級應理解為聚合程度較低的一類層級，即低層級中可包含多個不同級別的層級。

在進行編碼時，編碼規(guī)則推薦但不限于“層級代碼+網格代碼”的形式；網格中心點所建立的靜態(tài)索引為K-D樹[14]索引。

而后獲取所述設定區(qū)域內的標記物信息，按照網格的編碼進行統(tǒng)計，并將統(tǒng)計信息（Key-Value形式）保存至Key-Value數據庫（例如Redis），同時對獲取的標記物信息建立動態(tài)索引，該動態(tài)索引為四叉樹索引[15]。

2.2 確定聚散層級計算規(guī)則

為了便于理解，本文以常見的電子地圖，譬如百度為例進行說明。百度地圖縮放等級zoom有19級（3~21），確定3~4級為高層級聚合（世界地圖范圍）、5~11級為低層級聚合（中國區(qū)域范圍），12~21級（城市區(qū)域范圍）為散開展示等，需要說明的是，聚散層級計算規(guī)則可以根據實際采用的電子地圖以及應用場景需要進行確定。

2.3 獲取zoom

在進行地圖標記物的聚散可視化展示時，獲取地圖當前的縮放等級zoom，并結合預設的聚散層級計算規(guī)則確定當前為聚合展示或散開展示，若為聚合展示，還需明確是高級聚合展示或低級聚合展示，以便于獲取對應的展示信息。

2.4 聚合展示

在根據當前地圖的縮放級別zoom計算得到聚散層級之后，若為聚合展示，則執(zhí)行如下算法。

算法1

輸入：當前地圖的縮放級別zoom和可視區(qū)域的像素坐標范圍（左上角到右下角所框定的矩形區(qū)域）ViewRectArea；

1.按照2.1節(jié)中的網格定義，進行分層網格中心點的獲取和存儲，中心點信息存儲到數據庫中，譬如MySQL，網格的中心點信息包括網格對應的層級Level和網格中心點的經緯度信息Pos；

2.對存儲的中心點信息建立K-D樹索引，該索引為靜態(tài)的；

3.獲取海量地圖標記物信息，包含位置信息，所屬網格編碼等，并存儲到數據庫中，同時在入庫過程中，對海量地圖標記物進行分類，以鍵值對（Key-Value）形式，即“網格編碼-統(tǒng)計數量”存到Key-Value數據庫，譬如Redis；

4.對存儲的海量地圖標記物信息建立四叉樹索引，該索引為動態(tài)的，每次有標記物增刪改時，會動態(tài)更新（可選）；

5.根據zoom和確定的聚散層級計算規(guī)則Rule，可以確定要展示的對應層級Level；

6.按照瓦片地圖的坐標轉換算法[16-18]，可以得到ViewRect-Area對應的可視區(qū)域的經緯度范圍LonlatRectArea；

7.根據LonlatRectArea和靜態(tài)索引（K-D樹），可以快速查詢到可視區(qū)域內對應層級Level下的網格的中心點信息集合Slevel，Slevel={Pos1,Pos2,…,Posn}，Posi為第i個中心點信息，其中包含網格編碼和經緯度信息；

8.對于Slevel中的每一個中心點，查詢Key-Value數據庫，Key為中心點的編碼，Value為該中心點對應的聚合點數量的統(tǒng)計值，綜合可以得到聚合點集合Saggregation，Saggregation={APos1,APos2,…,APosn}，APosi為第i個聚合點信息，其中包含經緯度和統(tǒng)計量。

下面結合服務器和瀏覽器的交互，如圖3所示，對算法進行詳述。

圖3 聚合展示交互時序圖Fig.3 Clustering display interactive sequence diagram

算法1的輸入是當前地圖的縮放級別和可視區(qū)域的像素坐標范圍，輸出是聚合點集合。具體是瀏覽器發(fā)送區(qū)域查詢請求，服務器返回聚合結果，然后在瀏覽器頁面展示。

第1~4步運行在服務器端。第1步是初始化網格信息，并進行持久化存儲，網格信息只需初始化一次；第2步是數據預處理過程，即對已有的網格數據構建K-D樹索引，便于快速查詢，這里選擇采用K-D樹，原因有二，其一是K-D樹非常適合于空間點集數據。其二，相比于四叉樹、R樹[19]，K-D樹在空間復雜度和時間復雜度上都是比較折中的。此外，構建K-D樹不需要動態(tài)構建，可以預先進行構建，構建時注意選擇空間點中的中位數作為切分點，這樣構建出來的K-D樹是平衡的；前兩步可以統(tǒng)稱為“構建索引”。第3步是統(tǒng)計預處理過程，即存儲海量地圖標記物的同時，按照網格編碼進行統(tǒng)計并持久化到Key-Value數據庫，可以稱為“分類統(tǒng)計”；“構建索引”和“分類統(tǒng)計”可以并行；第4步是對數據進行預處理，便于后續(xù)散開展示時快速查詢，這里選擇采用四叉樹，是出于性能上考慮，因為面對需要數據動態(tài)更新的場景，要求索引能夠快速構建，K-D樹需要打破重建，而四叉樹可以增量構建。這一步也可以在散開展示算法中進行（見算法2步驟2），所以可選，在圖3中沒有列出；第5~6步運行在瀏覽器端，第5步是確定層級Level，即是高層級聚合還是低層級聚合；第6步是可視區(qū)域像素坐標轉化為經緯度坐標；第7~8步運行在服務器端，第7步是區(qū)域查詢，輸出為可視區(qū)域內對應層級Level下的網格的中心點信息集合Slevel。在預先構建K-D樹索引的基礎上，可以快速查詢指定區(qū)域下包含哪些空間點（Slevel={Pos1,Pos2,…,Posn}），但是這些空間點僅僅包含位置信息，沒有統(tǒng)計量（該位置包含的點數量）；第8步是合并查詢結果，即對Slevel中的每個點進行遍歷，根據每個點中的網格編碼，查詢第3步中存儲在Key-Value數據庫中的信息，得到每個Key（網格編碼），對應的Value（統(tǒng)計數量），合并結果，即得到每個點的統(tǒng)計量，輸出目標結果聚合點集合Saggregation。最后返回給瀏覽器進行展示。

2.5 散開展示

在根據當前地圖的縮放級別zoom計算得到聚散層級之后，若為散開展示，則執(zhí)行如下算法。

算法2

輸入：當前地圖的縮放級別zoom和可視區(qū)域的像素坐標范圍ViewRectArea；

1.獲取海量地圖標記物信息，包含經緯度、圖標、屬性信息（可選）；

2.對地圖標記物信息進行持久化到數據庫，包含經緯度和基本信息，在錄入的同時建立四叉樹索引，該索引為動態(tài)索引；

3.根據zoom和確定的聚散層級計算規(guī)則Rule，可以確定要散開展示；

4.按照瓦片地圖的坐標轉換算法，可以得到ViewRectArea對應的可視區(qū)域的經緯度范圍LonlatRectArea；

5.根據LonlatRectArea和動態(tài)索引（四叉樹），可以快速查詢到可視區(qū)域內地圖標記物中心點位置信息集合Smarkers，Smarkers={M1,M2,…,Mn}，其中Mi為第i個標記物；

6.利用網格過濾算法，依據后進先出的原則，對地圖標記物集合Smarkers進行篩選，具體的網格過濾算法，采用如下步驟：

（1）假設展示區(qū)域的標記物圖標的尺寸為P×Q像素單位，且該像素的坐標點位于標記物圖標的中心位置；

（2）假設展示區(qū)域的分辨率為S×T像素單位，結合圖標緩存為P×Q像素單位，將展示區(qū)域劃分為(S/2P)×(T/2Q)個網格；

（3）對于每一個網格，采用基于幾何拓撲關系的點與面相交運算[20]，選出位于同一網格中的標記物信息，依據后進先出原則去除重疊的標記物信息，得到篩選后的標記物信息。

輸出：篩選后的地圖標記物集合Sfilter_markers，Sfilter_markers={M1,M2,…,Mm}，m≤n。

下面結合服務器和瀏覽器的交互，如圖4所示，對算法進行詳述。

圖4 散開展示交互時序圖Fig.4 Scattering display interactive sequence diagram

算法2的輸入和算法1一樣，輸出是經過篩選后的地圖標記物集合。第1~2步運行在服務器端，第1步是獲取海量數據，可以通過在線采集或者客戶提供，這一過程可以在聚合展示階段進行（見算法1步驟3），所以可選，在圖4中沒有列出；第2步是數據持久化和預處理，這里對海量數據點構建的數據結構為四叉樹，便于動態(tài)更新；第3~4步運行在瀏覽器端，第3步是確定為散開展示；第4步是可視區(qū)域像素坐標轉化為經緯度坐標；第5步是區(qū)域查詢，運行在服務器端，輸出為可視區(qū)域內地圖標記物中心點位置信息集合Smarkers；第6步是過濾重疊，運行在瀏覽器端，主要是針對圖標堆疊，核心是利用幾何拓撲關系的點面相交運算，開源代碼庫turf.js里面提供了booleanPointInPolygon方法[21]。即地圖標記物坐標（點）與圖標緩存區(qū)域（面）相交超過兩次，只算第一次，后進的先出。最終可以得到不含重疊的地圖標記物集合Sfilter_markers。最后在瀏覽器頁面進行展示。

3 實驗評估

本實驗的主要目的是評價海量地圖標記物聚散可視化算法的有效性，主要圍繞以下兩個問題展開：（1）測試算法對于海量地圖標記物展示的可行性；（2）與已有聚合算法的性能進行對比，以及在散開展示時增加網格過濾對性能有無影響。

3.1 實驗案例

本文利用在線百度地圖開放平臺提供的行政區(qū)查詢接口[22]，可以獲得全國23個省、4個直轄市、5個自治區(qū)和2個特別行政區(qū)的本級以及向下三級（到街道級）的行政區(qū)中心點信息（行政區(qū)劃碼、經緯度），并持久化到MySQL數據庫，將行政區(qū)劃作為一種網格劃分，網格編碼為行政區(qū)劃碼，該網格劃分具有分層的屬性（省級、市級、區(qū)縣級、街道級）。通過模擬，在浙江省范圍內隨機生成100萬的地圖標記物，將這100萬的地圖標記物數據作為測試數據。

采用如下規(guī)則計算聚散層級：當前的地圖縮放級別zoom取值為3~21，其中3~9級為省級聚合，10~12級為市級聚合，12~14級為區(qū)縣級聚合，15以上為散開展示。在聚合層級中，省級聚合和市級聚合可理解為高層級聚合，區(qū)縣級聚合可理解為低層級聚合。

3.2 實驗環(huán)境

本次實驗在Windows 10系統(tǒng)進行。采用主流的Chrome瀏覽器，數據庫為MySQL，Key-Value數據庫為Redis，構建B/S服務方式，算法運行在JVM環(huán)境。依據上述計算聚散層級規(guī)則和網格劃分，對100萬測試數據進行展示。實驗配置環(huán)境如表1所示。

表1 實驗環(huán)境配置Table 1 Experimental environment configuration

3.3 實驗過程

首先對MySQL中分層的網格劃分數據庫表，也就是省級、市級和區(qū)縣級的行政區(qū)中心點數據，構建K-D樹索引，持久化100萬地圖標記測試數據到MySQL數據庫，同時將地圖標記物的分類計數統(tǒng)計信息按照行政區(qū)劃，以鍵值對形式（網格編碼-統(tǒng)計個數）存到Redis數據庫。然后對100萬地圖標記測試數據構建四叉樹索引。最后在Chrome瀏覽器中進行交互查詢。

對于不同的地圖縮放級別zoom，對應的聚合信息也會顯示不同，高級別的縮放等級，對應的是較高等級的行政級別聚合信息，譬如市級聚合信息，如圖5所示即為市級的聚合在百度地圖上渲染，圖中A點的展示信息為市1∶87 864家，圖中B點的展示信息為市2∶912 109家。

圖5 市級聚合Fig.5 City-level clustering

低級別的縮放等級，對應的是較低等級的行政級別聚合信息，譬如區(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

當達到散開展示的縮放等級時，對比兩種情況，未使用和已使用網格過濾算法，展示效果如圖7、8所示。

圖7 散開展示未過濾Fig.7 Scattering display without filtering

圖8 散開展示已過濾Fig.8 Scattering display with filtering

3.4 實驗結果

通過上述實驗過程，可以看出，分層的網格劃分聚散可視化方法對于100萬數據的海量地圖標記物是可行的，效果有效。

接下來，還需要對比已有算法的性能，本文選擇文獻[8]中涉及的算法，即距離點聚合算法和K-means點聚合算法在相同數量級、相同縮放級別（顯示比例）下的響應時間進行對比。

表2展示了縮放等級和顯示比例的對應關系。表3展示了不同的縮放等級下最多包含的地圖標記物數量。

表2 縮放等級和顯示比例尺對應關系Table 2 Correspondence between zoom level and display scale

表3 縮放等級和地圖點數量Table 3 Zoom level and number of map points

結合表2和表3可以看出，隨著縮放等級的增加，比例尺也增加，對應的可視區(qū)域所含地圖點數量在減少，而且這里的數量是針對本實驗案例的數量，可以用作數量級參考，比如縮放等級zoom為17，即對應的顯示比例尺為1∶500，所含地圖點為900左右數量級。本實驗選擇zoom為12~17作為參照對比的對象。

從圖9、10可以看出，在大比例尺下可視區(qū)域內待聚合空間點的數量較少時，本文所提算法和其他算法相比并無明顯優(yōu)勢，當比例尺逐步減少，顯示區(qū)域內需要聚合的數據量變大時，本文所提算法相較其他算法，體現(xiàn)出明顯優(yōu)勢。觀察走勢，基于距離的點聚合算法，時間復雜度呈線性增加，基于K-means的點聚合算法，時間復雜度呈幾何級數增加，本文所提算法，依靠索引，穩(wěn)定在固定值左右，幾乎不會增加。

圖9 與基于距離的點聚合對比Fig.9 Comparison with distance-based points clustering

表4可以看出，在散開展示時增加過濾算法，對整體性能影響不是很大，整體延時（100 ms以內）在用戶體驗可接受的范圍之內。

圖10 與基于K-means的點聚合對比Fig.10 Comparison with points clustering based on K-means

表4 散開過濾算法耗時對比Table 4 Time-consuming comparison of diffuse filtering algorithms

4 結束語

在海量空間標記物的場景下，地圖可視化技術提供了一種直觀和全面的展示和分析手段，用于觀測海量數據下的整體趨勢和分布以及某些特定區(qū)域的細節(jié)數據。現(xiàn)有的可視化手段，仍然存在一些問題。本文提出了一種分層的網格劃分方法來實現(xiàn)海量空間標記物的聚散一體可視化解決方案，主要利用了索引技術和存儲，加快了整體查詢效率，利用空間拓撲運算，實現(xiàn)了重疊標記物的去重，從而為用戶提供了良好的交互體驗。

然而在實驗過程中發(fā)現(xiàn)仍有一些地方可以改進：一是分層機制沒有統(tǒng)一的標準，目前都是基于實際場景需求而定，譬如同一個zoom級別下，有些場景是聚合，有些場景就要散開；二是網格劃分的好壞沒有統(tǒng)一的批判標準，目前常用的基于地形邊界和基于行政區(qū)劃的網格劃分都是依據經驗和工程效果來確定的；三是索引技術還有進一步提升的空間，譬如增加二級索引或稱輔助索引（secondary index）[23]，同時還可以增加布隆過濾器。但是這里面就涉及性能和效率的權衡問題。以上這些在實驗中暴露的問題，后續(xù)將進一步進行研究。