分層網格劃分實現海量地圖標記物聚散可視化

傅晨恩，陳 瓊

中電海康集團有限公司，杭州 311100

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

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

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

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

1 問題描述

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

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

2 研究方法

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

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

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

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

（2）確定聚散層級計算規則；

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

（4）條件判斷：

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

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

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

2.1 定義網格

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

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

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

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

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

2.2 確定聚散層級計算規則

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

2.3 獲取zoom

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

2.4 聚合展示

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

算法1

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

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

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

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

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

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

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

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

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

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

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

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

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

2.5 散開展示

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

算法2

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

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

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

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

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

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

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

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

（2）假設展示區域的分辨率為S×T像素單位，結合圖標緩存為P×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步是數據持久化和預處理，這里對海量數據點構建的數據結構為四叉樹，便于動態更新；第3~4步運行在瀏覽器端，第3步是確定為散開展示；第4步是可視區域像素坐標轉化為經緯度坐標；第5步是區域查詢，運行在服務器端，輸出為可視區域內地圖標記物中心點位置信息集合Smarkers；第6步是過濾重疊，運行在瀏覽器端，主要是針對圖標堆疊，核心是利用幾何拓撲關系的點面相交運算，開源代碼庫turf.js里面提供了booleanPointInPolygon方法[21]。即地圖標記物坐標（點）與圖標緩存區域（面）相交超過兩次，只算第一次，后進的先出。最終可以得到不含重疊的地圖標記物集合Sfilter_markers。最后在瀏覽器頁面進行展示。

3 實驗評估

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

3.1 實驗案例

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

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

3.2 實驗環境

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

表1 實驗環境配置Table 1 Experimental environment configuration

3.3 實驗過程

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

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

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

低級別的縮放等級，對應的是較低等級的行政級別聚合信息，譬如區縣聚合信息，如圖6所示即為區縣級的聚合在百度地圖上渲染，圖中C點的展示信息為縣1∶329 984家，圖中D點的展示信息為區1∶296 122家，圖中E點的展示信息為區2∶286 003家。

圖6 區縣級聚合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可以看出，隨著縮放等級的增加，比例尺也增加，對應的可視區域所含地圖點數量在減少，而且這里的數量是針對本實驗案例的數量，可以用作數量級參考，比如縮放等級zoom為17，即對應的顯示比例尺為1∶500，所含地圖點為900左右數量級。本實驗選擇zoom為12~17作為參照對比的對象。

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

圖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 結束語

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

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