劉澤邦,陳 犖,馬夢宇,楊岸然,鐘志農(nóng),景 寧

(國防科技大學(xué) 電子科學(xué)學(xué)院, 湖南 長沙 410073)

地理矢量數(shù)據(jù)模型通常以點、線、面等離散對象來描述地理表面空間要素的形狀和位置,以及刻畫地理空間現(xiàn)象的范圍與分布,是全空間地理信息系統(tǒng)描述時空實體的核心數(shù)據(jù)模型[1]。地理矢量線數(shù)據(jù)作為地理矢量數(shù)據(jù)的重要組成部分,通過一系列順序排列的點來實現(xiàn)對現(xiàn)實世界的表達,被廣泛用于道路、行政區(qū)劃、河流水系、建筑物輪廓等多種線狀地物的描述和表達。隨著地理空間數(shù)據(jù)采集技術(shù)的快速發(fā)展,地理矢量線數(shù)據(jù)的規(guī)模呈現(xiàn)爆炸性增長態(tài)勢。根據(jù)2021年交通運輸行業(yè)發(fā)展統(tǒng)計公報數(shù)據(jù)顯示,截至2021年底全國公路總里程已達5.280 7×107km,涉及的道路矢量數(shù)量規(guī)模達到了千萬級[2];截至2022年,OSM(OpenStreetMap)中的地理矢量線要素的規(guī)模已達到億級[3]。這些體量龐大且不斷增長的地理矢量線數(shù)據(jù)不僅數(shù)據(jù)量巨大,而且絕大部分的數(shù)據(jù)僅僅以表格或文本形式呈現(xiàn),用戶需耗費大量的時間和精力進行數(shù)據(jù)的處理和分析。

空間數(shù)據(jù)可視化作為空間分析的重要手段,是探索挖掘空間數(shù)據(jù)的基礎(chǔ)[4-5],有助于用戶直觀地對空間數(shù)據(jù)進行總結(jié)、分析和推理[6-7]。隨著網(wǎng)絡(luò)信息技術(shù)的快速發(fā)展,基于瓦片金字塔技術(shù)[8]的網(wǎng)絡(luò)瓦片地圖服務(wù)被提出并用于在互聯(lián)網(wǎng)瀏覽地理矢量數(shù)據(jù),大規(guī)模地理矢量數(shù)據(jù)的高效可視化成為當(dāng)前地理信息科學(xué)領(lǐng)域的研究熱點[9-13]。

在可視過程中,需要遵循經(jīng)典的可視分析探索流程[14]:既能以鷹眼視角瀏覽數(shù)據(jù)的總體分布,又可進行縮放瀏覽數(shù)據(jù)的個體細節(jié)。為提升可視化效率,單機上的可視化方法通過數(shù)據(jù)采樣、聚合、簡化等一系列減少數(shù)據(jù)規(guī)模的方法來實現(xiàn)快速可視化響應(yīng)[15-20]。一些研究利用GPU的圖形處理優(yōu)勢來加速地理矢量數(shù)據(jù)可視化處理過程[21-23]。矢量瓦片技術(shù)作為近期流行的可視化技術(shù)[24-25],可支持在客戶端直接對數(shù)據(jù)進行樣式渲染。文獻[26]實現(xiàn)了大規(guī)模衛(wèi)星點數(shù)據(jù)的多分辨率的熱區(qū)分布圖展示。Eldawy等[27]實現(xiàn)了散點圖、路網(wǎng)圖、熱力圖等多種可視化效果。YU等[28-29]實現(xiàn)了億級規(guī)?？臻g數(shù)據(jù)的地圖可視化。文獻[30-31]采用預(yù)先生成部分可視化結(jié)果的思想實現(xiàn)了高分辨率的地圖實時可視化。然而,上述可視化方法采用數(shù)據(jù)導(dǎo)向的計算方式,以單個矢量要素作為計算單元進行可視化計算。隨著數(shù)據(jù)規(guī)模的急劇增長,會產(chǎn)生地圖瓦片數(shù)據(jù)集生成耗時長,規(guī)模大,樣式難以交互更改等問題,即使采用高性能并行計算技術(shù)也難以滿足無縫數(shù)據(jù)瀏覽、高效實時渲染等可視化需求[32]。

1 可視化模型描述

當(dāng)前主流可視化方法以數(shù)據(jù)為計算導(dǎo)向,如圖1所示,其核心思想是以單個矢量要素作為計算單元,將其轉(zhuǎn)換為便于屏幕顯示的柵格對象,最后合并得到可視化結(jié)果。

圖1 傳統(tǒng)數(shù)據(jù)導(dǎo)向的可視化模型Fig.1 Traditional data-driven visualization model

顯示導(dǎo)向的可視化模型[33-36]如圖2所示。該模型以屏幕像元為計算單元,將依賴矢量要素規(guī)模的計算復(fù)雜度轉(zhuǎn)換為依賴像元規(guī)模的計算復(fù)雜度,大幅提升了計算效率。

圖2 顯示導(dǎo)向的可視化模型Fig.2 Display-driven visualization model

在可視瀏覽時,可視瓦片的屬性不盡相同,如顯示層級或高或低,要素數(shù)量或多或少,導(dǎo)致繪制效率差異較大。為實現(xiàn)各顯示層級上的實時可視化,提出面向多層級瓦片繪制的自適應(yīng)可視化模型。如圖3所示,模型對瓦片繪制任務(wù)進行自適應(yīng)判定,選擇最優(yōu)方式繪制可視結(jié)果。當(dāng)采用顯示導(dǎo)向可視化算法,進行像元生成判定;當(dāng)采用數(shù)據(jù)導(dǎo)向可視化算法,檢索瓦片內(nèi)矢量要素進行柵格化。在模型中,地理矢量數(shù)據(jù)需轉(zhuǎn)換成特定的空間索引用以支撐多層級瓦片繪制,該索引一方面能為瓦片繪制算法的自適應(yīng)選取提供支撐,另一方面能兼顧顯示導(dǎo)向與數(shù)據(jù)導(dǎo)向兩種可視化算法的計算需求。最后,在自適應(yīng)判定器中設(shè)定判定因子,根據(jù)瓦片繪制任務(wù)的判定結(jié)果來選取可視化算法。判定因子包括:瓦片顯示層級,即顯示層級越低,則線要素越多,可視化耗時長;瓦片內(nèi)矢量線要素數(shù)量,即線要素越多,可視化耗時越長;瓦片內(nèi)矢量線要素總長度,即線要素總長度越長,可視化耗時越長。

圖3 面向多層級瓦片繪制的自適應(yīng)可視化模型Fig.3 Adaptive visualization model for multilevel tile drawing

2 像元四叉R樹索引

2.1 索引結(jié)構(gòu)設(shè)計

在面向多層級瓦片繪制的自適應(yīng)可視化模型中,為繪制任意顯示層級上的一張瓦片圖,數(shù)據(jù)導(dǎo)向的可視化方法需快速檢索與該瓦片對應(yīng)空間范圍拓撲相交的矢量線要素;顯示導(dǎo)向的可視化方法需要判斷像元對應(yīng)空間范圍是否與任一矢量線要素拓撲相交。

為實現(xiàn)快速可視化所需的拓撲相交和數(shù)據(jù)檢索的計算需求,設(shè)計了一種PQR樹空間索引。如圖4所示,PQR樹是由多個索引結(jié)點連接的類四叉樹結(jié)構(gòu),有別于常規(guī)四叉樹以數(shù)據(jù)集最小外包框作為根結(jié)點索引范圍,PQR樹將全球空間范圍作為根結(jié)點索引范圍,再不斷向下進行遞歸四分得到索引結(jié)點,索引結(jié)點共五種類型:根結(jié)點、左上結(jié)點、右上結(jié)點、左下結(jié)點、右下結(jié)點。在索引結(jié)點中,記錄結(jié)點的空間范圍、地理編碼、結(jié)點屬性與結(jié)點指針等信息。當(dāng)達到預(yù)先設(shè)定的最高層級后則不再進行劃分,在PQR樹的最高層級上,每個索引結(jié)點連接一個R樹,對與索引結(jié)點索引范圍拓撲相交的矢量線要素進行高效組織。

圖4 PQR樹索引結(jié)構(gòu)設(shè)計Fig.4 PQR-tree index layout

PQR樹索引結(jié)點說明如下:①基于Geohash的編碼方法來獲取索引結(jié)點編碼。如圖4所示,從根結(jié)點向下編碼,每向下遞歸劃分一層:左上、右上、左下、右下結(jié)點的編碼分別為“00”,“10”,“01”和“11”,不同層級結(jié)點的編碼長度不一致,最終得到二進制形式的編碼作為索引結(jié)點編碼。②對于矢量線數(shù)據(jù),選取要素數(shù)量count、顯示層級level、要素長度length三個判定因子作為結(jié)點屬性。③結(jié)點指針包括四個子結(jié)點指針LU-ptr、RU-ptr、LB-ptr、RB-ptr和一個R樹指針R-ptr。非葉子結(jié)點的四個子結(jié)點指針分別指向該結(jié)點索引范圍四分后的四個子區(qū)域所對應(yīng)的子索引結(jié)點,R樹指針為空;葉子結(jié)點的四個子結(jié)點指針均為空,R樹指針指向該索引結(jié)點所連接的R樹。

PQR樹的索引結(jié)點的索引范圍與瓦片/像素對應(yīng)空間范圍是唯一映射的,這一特性使其可同時滿足自適應(yīng)判定、數(shù)據(jù)導(dǎo)向與顯示導(dǎo)向可視化方法的計算需求:①只需快速找到瓦片對應(yīng)的索引結(jié)點,并對其中記錄的判定因子進行比較,即可完成自適應(yīng)判定;②對于瓦片對應(yīng)的索引結(jié)點,對該結(jié)點連接的R樹執(zhí)行空間檢索獲取瓦片對應(yīng)空間范圍內(nèi)的矢量要素,即可完成數(shù)據(jù)導(dǎo)向可視化方法的計算需求;③對于瓦片對應(yīng)的索引結(jié)點,只需從該結(jié)點向下判斷像素對應(yīng)的索引結(jié)點是否存在,即可完成顯示導(dǎo)向可視化方法的計算需求。

2.2 索引構(gòu)建

地理矢量線數(shù)據(jù)的PQR樹索引構(gòu)建算法的核心思想是從根結(jié)點“自頂而下”地將矢量線要素與全球地理空間范圍遞歸四分的結(jié)果進行拓撲相交判斷(“位于”和“疊置”)來生成索引結(jié)點,在達到最高層級后,將矢量線要素組織生成R樹結(jié)構(gòu)。由于像元對應(yīng)空間范圍是由瓦片對應(yīng)空間范圍遞歸劃分八次得到,為滿足顯示導(dǎo)向可視化方法的計算需求,PQR樹的層級不低于8。

在創(chuàng)建索引結(jié)點時,最常采用近似表達的方式將矢量線要素的最小外包框(minimum boundary box, MBB)與空間范圍框進行判定?？紤]當(dāng)在低顯示層級時,矢量線要素完全位于空間范圍框內(nèi),而在高顯示層級時,矢量要素只與部分空間范圍框相交。為提高計算效率,將線要素表示為雙層外包框結(jié)構(gòu),如圖5所示,其包含了線要素的MBB和線要素中每條線段的MBB。在相交判斷時,依次采用線要素的MBB和每條子段的MBB用于計算,兩層過濾后再判斷每條子段與空間范圍框是否空間拓撲相交。

圖5 地理矢量線要素的雙層級最小外包框結(jié)構(gòu)Fig.5 Double MBB structure of geographic vector linestring features

PQR樹索引構(gòu)建流程包括:①創(chuàng)建根結(jié)點,對于任一地理矢量數(shù)據(jù)集,根結(jié)點的空間范圍均為全球地理空間范圍。②逐一遍歷數(shù)據(jù)集中地理矢量線要素,將其表示為雙層級外包框結(jié)構(gòu)。③將根結(jié)點的空間范圍劃分為四個子空間,分別與線要素的MBB進行空間關(guān)系判定,若線要素位于某個子空間內(nèi),則創(chuàng)建相應(yīng)的索引結(jié)點,并從該索引結(jié)點繼續(xù)向下進行遞歸判定,直至生成包含要素MBB的最小索引結(jié)點。④依次選取要素的每條子段的MBB,將其分別與最小索引結(jié)點的空間范圍劃分后所得的四個子空間進行空間關(guān)系判定。⑤若子段的MBB位于某個子空間內(nèi),則創(chuàng)建相應(yīng)的索引結(jié)點;若子段的MBB與某些子空間相疊置,則再精細判定子段與這些子空間是否相疊置來創(chuàng)建相應(yīng)的索引結(jié)點;繼續(xù)從新創(chuàng)建的索引結(jié)點向下遞歸判定,直至設(shè)定的最高層級。⑥分別將要素子段插入與其相交的索引結(jié)點所連接的R樹中。⑦當(dāng)所有的矢量線要素判定完畢后,構(gòu)建得到最終的PQR樹索引。

3 基于像元四叉R樹的自適應(yīng)可視化

在面向多層級瓦片繪制的自適應(yīng)可視化模型中,為快速繪制各個顯示層級上的瓦片圖,設(shè)計基于PQR樹的自適應(yīng)可視化(PQR-tree-based adaptive visualization, PAV)算法。PAV對判定因子的判定流程進行了設(shè)定:當(dāng)采用顯示導(dǎo)向可視化方法,核心是判定像元對應(yīng)的索引結(jié)點在PQR樹中是否存在;當(dāng)采用數(shù)據(jù)導(dǎo)向可視化方法,核心是從PQR樹中快速檢索瓦片對應(yīng)空間范圍內(nèi)的矢量線要素。

根據(jù)2.2節(jié),對線數(shù)據(jù)集構(gòu)建PQR樹后,與線要素存在空間拓撲相交的空間范圍框會生成對應(yīng)的索引結(jié)點。所以對于待繪制的瓦片任務(wù),需要判斷瓦片對應(yīng)的索引結(jié)點在PQR樹中是否存在來決定瓦片是否需要被繪制。同時,在顯示導(dǎo)向的可視化繪制時,也需要判斷像元對應(yīng)的索引結(jié)點在PQR樹中是否存在來決定像元值是否需要被生成。基于此,設(shè)計了索引結(jié)點查找函數(shù)SEARCHNODE,如算法1所示,“自頂而下”地從設(shè)定索引結(jié)點向下查找對應(yīng)的索引結(jié)點。函數(shù)輸入包括開始查詢的索引結(jié)點sNode和瓦片/像元對應(yīng)空間范圍框的地理編碼rCode,當(dāng)查詢到對應(yīng)的索引結(jié)點時進行輸出,反之輸出為空。算法主要步驟為:①逐個遍歷初始結(jié)點的子結(jié)點指針,判斷子結(jié)點cNode是否存在;②當(dāng)子結(jié)點存在時,獲取cNode的地理編碼cCode;③判斷cCode與rCode長度是否相等;若兩者不等,取兩者的前綴對應(yīng)位數(shù)進行異或操作,稱為前綴匹配;④若操作結(jié)果為0,將cNode與rCode作為函數(shù)輸入,遞歸執(zhí)行索引結(jié)點生成函數(shù);⑤直至當(dāng)rCode與cCode完全相等,輸出cNode為與空間范圍框相對應(yīng)的索引結(jié)點,其余情況下均輸出為空。

算法1 索引結(jié)點查找函數(shù)Alg.1 Searching function of index node

當(dāng)瓦片對應(yīng)的索引結(jié)點存在時,則說明瓦片需要被繪制。此時,PAV獲取到該瓦片對應(yīng)的索引結(jié)點中的屬性信息(顯示層級level、線要素數(shù)量count、線要素總長度length),并與三個判定因子的閾值進行比較,具體的判定流程如下:①判斷層級信息level與δlevel的大小,當(dāng)level大于δlevel時,則選擇數(shù)據(jù)導(dǎo)向的可視化方法;反之繼續(xù)判斷。②判斷count與δcount的大小,當(dāng)count大于δcount時,選擇顯示導(dǎo)向的可視化方法;反之繼續(xù)判斷。③判斷l(xiāng)ength與δlength的大小,當(dāng)length大于δlength時,選擇顯示導(dǎo)向的像素生成策略;反之選擇數(shù)據(jù)導(dǎo)向的可視化方法。

PAV的具體實現(xiàn)主要分為五步:①調(diào)用算法1的索引結(jié)點查找函數(shù),判斷待繪制瓦片對應(yīng)的索引結(jié)點在索引中是否存在,若不存在則直接輸出空白的瓦片圖;反之繼續(xù)執(zhí)行。②獲取索引結(jié)點的結(jié)點屬性信息(level,count,length),與設(shè)定的判定因子閾值進行判定,自適應(yīng)地選取可視化方法。③若選取顯示導(dǎo)向的可視化方法,則遍歷瓦片的每個像元,繼續(xù)調(diào)用算法1的索引結(jié)點查找函數(shù),判斷像元對應(yīng)的索引結(jié)點是否存在,若存在則直接在瓦片圖上生成像元值。④若選取數(shù)據(jù)導(dǎo)向的可視化方法,則對該索引結(jié)點連接的R樹執(zhí)行空間范圍檢索操作,得到地理矢量線要素,并逐一進行柵格化處理生成像元值。⑤最后輸出得到瓦片圖。

PAV的優(yōu)勢在于:采用顯示導(dǎo)向的可視化方法時,查找像素對應(yīng)的索引結(jié)點是否存在只有唯一的判斷路徑,采用簡單的二進制運算即可快速生成瓦片圖;采用數(shù)據(jù)導(dǎo)向的可視化方法時,在查找瓦片對應(yīng)的索引結(jié)點是否存在同樣只有唯一的判斷路徑,進而快速檢索到矢量要素并進行柵格化生成瓦片圖。最終可實現(xiàn)各個顯示層級上瓦片圖的快速繪制。

4 實驗與分析

實驗數(shù)據(jù)集如表1所示,來自開源志愿者網(wǎng)絡(luò)地圖服務(wù)平臺OSM。從L1至L7,數(shù)據(jù)規(guī)模逐漸增大。L7包含OSM全球所有線要素數(shù)據(jù),其中線要素的規(guī)模達到了10億級別。實驗環(huán)境:內(nèi)存為256 GB,核數(shù)為32的2.6 GHz的Inter處理器,且處理系統(tǒng)為Ubuntu 20.04。

表1 實驗數(shù)據(jù)集Tab.1 Datasets used in the experiments

為確立PAV中判定因子的閾值,實驗一選取L1～L6作為測試數(shù)據(jù)集,對比顯示導(dǎo)向的可視化方法(display-driven visualization, DiDV)和數(shù)據(jù)導(dǎo)向的可視化方法(data-driven visualization, DaDV)在不同的判定因子取值下的瓦片繪制性能,為PAV中的自適應(yīng)判定提供依據(jù)。實驗二在所有線數(shù)據(jù)集上分析PAV算法的可視化性能,其中L7作為測試集用以驗證算法的泛化能力,最終驗證PAV算法可以支撐大規(guī)模地理矢量數(shù)據(jù)集的多層級實時交互式可視化。實驗三將PAV與當(dāng)前主流可視化方法進行比較,驗證PAV算法的優(yōu)勢。在實驗中所有數(shù)據(jù)集均被預(yù)先轉(zhuǎn)換成PQR索引以支撐PAV算法。同時,由于每個瓦片的繪制任務(wù)間相互獨立,故采用多進程消息傳遞框架(message passing interface, MPI)與OpenMp混合并行的方式來提升瓦片繪制的性能,在所有實驗中均啟動了8個MPI進程(每個進程中包含4個OpenMp線程)用于繪制瓦片。

4.1 實驗一:判定因子閾值設(shè)定

本實驗用于獲取判定因子的閾值。采用DiDV與DaDV繪制瓦片圖,統(tǒng)計每張瓦片判定因子的值,評估瓦片的顯示層級、線要素數(shù)量、線要素總長度對兩種方法性能的影響。

為分析顯示層級的影響,在各顯示層級隨機選取2 000張非空瓦片,計算兩種方法在各顯示層級上的繪制速率,實驗結(jié)果如圖6所示,當(dāng)顯示層級較低時,DiDV的可視化性能明顯優(yōu)于DaDV,并且當(dāng)數(shù)據(jù)規(guī)模較大時的性能優(yōu)勢更明顯,在L4數(shù)據(jù)集上當(dāng)顯示層級為6時,DiDV的繪制速率為DaDV的35倍;隨著顯示層級升高,DaDV的效率顯著提升并開始超越DiDV,在L6數(shù)據(jù)集上的最大繪制速率達到563.8張/s。綜上可知,當(dāng)顯示層級較低時應(yīng)選擇DiDV,反之選擇DaDV。在設(shè)定閾值時,將完全包含數(shù)據(jù)集的最小瓦片層級作為其空間尺度值,例如全球空間的數(shù)據(jù)集的空間尺度則為0。當(dāng)數(shù)據(jù)集的空間尺度不同時,顯示層級閾值δlevel也不同,對于L1～L6,δlevel

(a) L1

(b) L2

(d) L4

(e) L5

(f) L6圖6 瓦片繪制速率隨顯示層級變化的對比Fig.6 Comparison of tile drawing speed at different zoom levels

的值比空間尺度的值大8至11,為滿足所有數(shù)據(jù)集在各個顯示層級上的快速可視化,以數(shù)據(jù)集的空間尺度值+11后的值設(shè)為PAV算法中的δlevel。

為分析瓦片空間范圍內(nèi)線要素數(shù)量的影響,設(shè)定六個不同的范圍區(qū)間:0～400、400～800、800～1 200、1 200～1 600、1 600～2 000、>2 000,對于每個范圍區(qū)間隨機選取2 000張非空瓦片,計算DiDV和DaDV的瓦片繪制速率,實驗結(jié)果如圖7所示。DaDV在線要素數(shù)量較小時表現(xiàn)出優(yōu)于DiDV的可視化性能,然而其性能隨線要素數(shù)量的增長而顯著下降,而DiDV的瓦片繪制速率維持著相對穩(wěn)定的水平。對于數(shù)據(jù)集L1～L6,實驗結(jié)果顯示在線要素數(shù)為400～800范圍內(nèi)DiDV的瓦片繪制速率開始超越DaDV,由此以800作為PAV算法中的線要素數(shù)量閾值δcount。

(a) L1

(b) L2

(c) L3

(d) L4

(e) L5

(f) L6圖7 瓦片繪制速率隨線要素數(shù)量變化的對比Fig.7 Comparison of tile drawing speed varies with the number of linestring features

為分析瓦片空間范圍內(nèi)線要素的影響,設(shè)定六個不同的范圍區(qū)間:0～200 km、200～400 km、400～600 km、600～800 km、800～1 000 km、>1 000 km。對于每個范圍區(qū)間隨機選取2 000張非空瓦片,計算DiDV和DaDV的瓦片繪制速率,實驗結(jié)果如圖8所示,DaDV在線要素總長度較小時表現(xiàn)出優(yōu)于DiDV的可視化性能,然而其性能隨線要素總長度的增長而顯著下降,而DiDV的瓦片繪制速率維持著相對穩(wěn)定的水平。對于數(shù)據(jù)集L1～L6,實驗結(jié)果顯示在線要素總長度為200～400 km的范圍區(qū)間上DiDV的瓦片繪制速率開始超越DaDV,由此以400 km作為PAV算法中的線要素總長度閾值δlength。

(a) L1

(b) L2

(c) L3

(d) L4

(e) L5

(f) L6圖8 瓦片繪制速率隨線要素總長度變化的對比Fig.8 Comparison of tile drawing speed varies with the total length of linestring features

4.2 實驗二:支撐多層級實時可視化性能

為驗證PAV算法具備支撐大規(guī)模地理矢量線數(shù)據(jù)的多層級實時可視化的能力,將實驗一確定的閾值(δlevel=11、δcount=800、δlength=400 km)代入PAV算法中,對于所有數(shù)據(jù)集L1～L7,在0～20顯示層級上隨機選擇5 000張非空瓦片,分別統(tǒng)計生成5 000張瓦片的總耗時和生成每張可視化瓦片的繪制時間。實驗結(jié)果見圖9,對于所有數(shù)據(jù)集,PAV算法均維持著相對穩(wěn)定高效的可視化性能,瓦片繪制速率最低也能達到366.5張/s,遠高于實時瀏覽數(shù)據(jù)所需的瓦片請求速率(通常不超過100張/s)。在10億規(guī)模測試數(shù)據(jù)集L7上,瓦片生成總耗時僅為13.6 s,瓦片繪制速率達到366.5張/s。同時,從L1～L7數(shù)據(jù)集規(guī)模顯著增長,而算法的瓦片生成總耗時并無明顯的增長,且瓦片繪制速率并無顯著的下降趨勢,說明其具有對數(shù)據(jù)集規(guī)模不敏感的特性,非常適用于對大規(guī)模地理矢量線數(shù)據(jù)的多層級實時可視化。圖10為生成5 000張瓦片的時間分布箱型圖,其中“”表示瓦片的平均生成時間,從結(jié)果可知,對于所有數(shù)據(jù)集,絕大部分的瓦片在30 ms內(nèi)可完成繪制,在10億規(guī)模測試數(shù)據(jù)集L7上,瓦片的最長生成時間僅為44 ms。假設(shè)當(dāng)前瀏覽器發(fā)送了100個瓦片請求,所有任務(wù)通過13輪(100÷8)繪制,最差情況也能在0.57 s((13×44) ms)內(nèi)完成任務(wù),完全可以滿足實時可視化的需求。綜上,結(jié)合圖9和圖10結(jié)果分析可知,PAV算法可以高效地支撐10億級規(guī)模的地理矢量線數(shù)據(jù)的多層級實時可視化。

圖9 生成5 000張瓦片的總耗時和繪制速率Fig.9 Total time and tile drawing speed of drawing 5 000 tiles

圖10 生成5 000張瓦片的時間分布箱型圖Fig.10 Box diagram of time distribution of drawing 5 000 tiles

4.3 實驗三:與主流可視化方法的性能對比

為驗證PAV算法的優(yōu)勢,將其與當(dāng)前兩個主流的空間數(shù)據(jù)可視化方法GeoSparkViz和HadoopViz進行比較,對于所有數(shù)據(jù)集,分別采用3種方法生成0～8顯示層級上的所有可視化瓦片,得到三種方法的總耗時對比,如圖11所示,對于所有數(shù)據(jù)集,GeoSparkViz生成瓦片的耗時少于HadoopViz,GeoSparkViz的瓦片生成性能相較HadoopViz更優(yōu),然而隨著數(shù)據(jù)規(guī)模增長,這兩種方法的瓦片生成性能急劇下降。而PAV生成可視化瓦片的耗時均遠少于GeoSparkViz與HadoopViz,表現(xiàn)出優(yōu)異的可視化性能,對于體量超過億級的數(shù)據(jù)集L4～L7,PAV的瓦片生成耗時分別僅為GeoSparkViz的13.2%、11.6%、8.1%、7.5%,且數(shù)據(jù)規(guī)模越大,PAV相較GeoSparkViz的瓦片生成性能優(yōu)勢越明顯。從L1～L7,隨著數(shù)據(jù)規(guī)模的增長,PAV的耗時并未出現(xiàn)大幅增長,驗證了PAV具有對數(shù)據(jù)規(guī)模不敏感的特性,能夠支撐大規(guī)模地理矢量線數(shù)據(jù)的多層級實時可視化。

圖11 生成可視化瓦片的總耗時Fig.11 Total time to render all tiles in zoom levels 0～8

為進一步對比三種方法在不同顯示層級上的可視化性能,圖12對比了三種方法在億級規(guī)模數(shù)據(jù)集L4～L7上第1、3、5、7、9顯示層級上的瓦片繪制速率,從實驗結(jié)果可知:GeoSparkViz和HadoopViz在較高的顯示層級上具有較高的瓦片繪制速率,其中GeoSparkViz的瓦片繪制速率優(yōu)于HadoopViz,GeoSparkViz在L4數(shù)據(jù)集的第9顯示層級上的瓦片繪制速率能達到269.77張/s。然而,隨著顯示層級的降低,GeoSparkViz與HadoopViz的瓦片繪制速率大幅下降,按照可視化瀏覽從整體到精細的原則,GeoSparkViz與HadoopViz無法實現(xiàn)大規(guī)模地理矢量線數(shù)據(jù)的多層級實時可視化。而PAV在所有數(shù)據(jù)集的各個顯示層級上均具有較高的瓦片繪制速率,特別當(dāng)顯示層級較低時,其瓦片繪制速率最差在L7數(shù)據(jù)集上也能達到115.29張/s,大幅優(yōu)于GeoSparkViz(0.01張/s)與HadoopViz(0.001張/s)的可視化性能。

(a) L4

(b) L5

(c) L6

(d) L7圖12 各顯示層級上的瓦片生成速率對比Fig.12 Comparison of tile drawing speed on each zoom level

從上述結(jié)果可知:對于反映可視化效率的兩個主要指標(biāo)瓦片生成總耗時和各顯示層級的瓦片繪制速率,PAV均大幅優(yōu)于主流可視化方法GeoSparkViz和HadoopViz。原因在于:GeoSparkViz和HadoopViz采用數(shù)據(jù)導(dǎo)向的計算方式,從L1至L7,隨著數(shù)據(jù)規(guī)模的增長,這兩種方法的瓦片生成總時間必然會大幅增長;并且對于同一數(shù)據(jù)集,當(dāng)在較高的顯示層級上,瓦片內(nèi)的矢量線要素的規(guī)模較小,所以GeoSparkViz和HadoopViz具備相對較高的瓦片繪制速率,隨著顯示層級的降低,數(shù)據(jù)規(guī)模急劇增長,某張瓦片內(nèi)的矢量線要素可能達到千萬甚至上億量級,從而使得GeoSparkViz和HadoopViz在低顯示層級上的瓦片繪制速率顯著下降。PAV采用顯示導(dǎo)向與數(shù)據(jù)導(dǎo)向相結(jié)合的自適應(yīng)可視化方法,當(dāng)數(shù)據(jù)規(guī)模較小或顯示層級較高時使用數(shù)據(jù)導(dǎo)向的可視化方法能快速繪制瓦片,反之采用顯示導(dǎo)向的可視化方法直接計算像元點的方式能大幅提升可視化效率,由此在較低顯示層級上仍具有較高的瓦片繪制速率,所以PAV在所有數(shù)據(jù)集的各個顯示層級上均具有較高的瓦片繪制速率,并且總的瓦片生成總耗時大幅降低。綜上所述,PAV相較現(xiàn)有主流的數(shù)據(jù)導(dǎo)向的可視化方法GeoSparkViz與HadoopViz具有明顯優(yōu)勢,能夠支撐大規(guī)模地理矢量線數(shù)據(jù)的多層級實時可視化。

5 結(jié)論

針對大規(guī)模地理矢量數(shù)據(jù)可視化這一當(dāng)前GIS領(lǐng)域研究的熱點問題,以大規(guī)模地理矢量線數(shù)據(jù)為研究對象提出高效的多層級可視化技術(shù)。該技術(shù)采用瓦片金字塔模型來展示地理矢量線數(shù)據(jù),以實現(xiàn)高效的瓦片繪制性能為計算目標(biāo),提出面向多層級瓦片繪制的自適應(yīng)可視化模型,在模型中通過自適應(yīng)判定來選擇最優(yōu)的顯示導(dǎo)向或數(shù)據(jù)導(dǎo)向的可視化方法,同時設(shè)計空間索引結(jié)構(gòu)和可視化算法來支撐模型中涉及的數(shù)據(jù)組織和可視化流程。實驗證明該技術(shù)在各個顯示層級上均具有高效的瓦片繪制性能,可在單機條件下支撐億級規(guī)模地理矢量線數(shù)據(jù)的多層級實時可視化,在空間數(shù)據(jù)的可視化探索上具有較好的應(yīng)用前景。