摘 要：為解決GPS軌跡數(shù)據(jù)動(dòng)態(tài)可視化效率低下問(wèn)題，本文通過(guò)引入LOD（Level Of Detail，LOD）技術(shù)從海量軌跡中提取能夠代表原始數(shù)據(jù)的空間特征點(diǎn)，保留原有空間分布特征，壓縮數(shù)據(jù)量?，F(xiàn)有LOD模型構(gòu)建算法雖壓縮了數(shù)據(jù)量，但時(shí)間復(fù)雜度高，不能顯著提高可視化效率。本文提出了一種基于四叉樹的點(diǎn)LOD構(gòu)建算法。實(shí)驗(yàn)表明：本文提出的點(diǎn)LOD算法與基于Voronoi圖的點(diǎn)LOD算法相比，具有時(shí)間復(fù)雜度低，LOD構(gòu)建速度快，無(wú)符號(hào)壓蓋等優(yōu)點(diǎn)。

關(guān)鍵詞：動(dòng)態(tài)可視化；GPS軌跡；LOD

中圖分類號(hào)：TP274 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract：To address the challenge to visualization of GPS trajectory data，this paper integrates Level Of Detail（LOD）technology into GPS data visualization in order to improve visualization efficiency while maintaining visualization quality.Although the existing LOD algorithms compress the quantity of GPS Data，it cannot significantly improve the visualization efficiency because of high time complexity.This paper proposes a quadtree-based point LOD algorithm.Experiments shows that the quadtree-based point LOD algorithm has lower time complexity，higher performance and better visualization quality than the widely used Voronoi-based LOD algorithm.

Keywords：online visualization；GPS trajectory；LOD

1 引言（Introduction）

隨著空間定位技術(shù)的成熟發(fā)展，可用于記錄位置信息的設(shè)備越來(lái)越普及，手機(jī)、平板等移動(dòng)終端及汽車大都內(nèi)嵌了GPS芯片或安裝了GPS接收機(jī)，這些設(shè)備每天產(chǎn)生大量的GPS軌跡數(shù)據(jù)[1]。GPS軌跡數(shù)據(jù)富含運(yùn)動(dòng)主體的群體分布特征，其動(dòng)態(tài)可視化有助于用戶快速直觀地理解分析這些特征[2，3]。以出租車為例，出租車GPS數(shù)據(jù)動(dòng)態(tài)可視化，可直觀反映出租車群體的空間分布變化情況。GPS軌跡數(shù)據(jù)作為一種高動(dòng)態(tài)性的時(shí)空序列數(shù)據(jù)，與傳統(tǒng)靜態(tài)空間數(shù)據(jù)相比，具有海量、更新速度快、時(shí)空密集度高等特點(diǎn)。因此，如何高效、準(zhǔn)確地可視化GPS軌跡數(shù)據(jù)，使用戶能夠快速直觀地獲取GPS軌跡蘊(yùn)含的信息，是GPS數(shù)據(jù)可視化研究中亟待解決的問(wèn)題。

2 常見(jiàn)LOD算法綜述（Summary of common LOD algorithm）

為解決GPS軌跡數(shù)據(jù)動(dòng)態(tài)可視化效率低下問(wèn)題，本文通過(guò)引入LOD技術(shù)從海量軌跡中提取能夠代表原始數(shù)據(jù)的空間特征點(diǎn)，縮短數(shù)據(jù)傳輸時(shí)間，以提高可視化效率。目前，國(guó)內(nèi)外針對(duì)LOD技術(shù)在電子地圖顯示中的研究取得了一些顯著成果。對(duì)于點(diǎn)狀要素LOD可視化研究，文獻(xiàn)[4]重點(diǎn)研究了電子地圖顯示中點(diǎn)狀要素LOD模型的建立，提出了一種基于Voronoi圖和Delaunay三角網(wǎng)綜合相關(guān)因素影響建立點(diǎn)狀要素LOD模型的算法，實(shí)現(xiàn)了不同比例尺下都能得到盡量合理的地圖外觀。文獻(xiàn)[5]結(jié)合聚類方法，在Voronoi圖的基礎(chǔ)上提取聚類中心點(diǎn)，同時(shí)利用層次Voronoi圖結(jié)構(gòu)逐步細(xì)化地表達(dá)聚類中心點(diǎn)，進(jìn)而實(shí)現(xiàn)點(diǎn)群由繁到簡(jiǎn)的綜合。文獻(xiàn)[6]針對(duì)聚集分布的點(diǎn)群，借助凸殼算法形成多層嵌套，以反映點(diǎn)群的逐層分布特征。

無(wú)論是Voronoi圖法還是凸殼法，都存在這樣一個(gè)問(wèn)題：算法時(shí)間復(fù)雜度高。這對(duì)于大數(shù)據(jù)可視化來(lái)說(shuō)，雖進(jìn)行了數(shù)據(jù)抽稀，縮短了前端可視化時(shí)間，但由于服務(wù)器端計(jì)算量大、耗時(shí)久，導(dǎo)致操作延時(shí)長(zhǎng)、用戶體驗(yàn)差等問(wèn)題。因此，針對(duì)大數(shù)據(jù)量的點(diǎn)群可視化需要一種更為快速的LOD模型構(gòu)建算法。

3 基于空間密度約束的LOD模型構(gòu)建方法（A LOD construction method for GPS trajectory data with constraints in spatial density）

基于空間密度約束的點(diǎn)狀要素LOD模型構(gòu)建算法借鑒了四叉樹的思想，邏輯上分為兩步，即空間劃分與編碼?？臻g劃分是將空間區(qū)域分別沿經(jīng)度方向和緯度方向遞歸中分，終止條件與比例尺有關(guān)。編碼是把劃分后的格網(wǎng)都賦予一個(gè)唯一的編碼。

3.1 空間劃分與編碼

空間劃分是對(duì)可視化區(qū)域的范圍沿經(jīng)緯度方向不斷地交替進(jìn)行二分，每四次二分作為一個(gè)層次，即兩次四叉劃分作為一個(gè)層次。用0和1表示每次二分產(chǎn)生的區(qū)域，即當(dāng)沿緯度方向進(jìn)行二分時(shí)，上面區(qū)域的編碼為1，下面區(qū)域的編碼為0；當(dāng)沿經(jīng)度方向進(jìn)行二分時(shí)，右側(cè)區(qū)域的編碼為1，左側(cè)區(qū)域的編碼為0；進(jìn)而，每四次二分的二進(jìn)制編碼轉(zhuǎn)換為16進(jìn)制編碼，即為某一層網(wǎng)格的編碼，如圖1所示。16進(jìn)制編碼由數(shù)字0—9和英文小寫字母a—f組成。

經(jīng)過(guò)編碼之后，空間每塊區(qū)域都對(duì)應(yīng)唯一的一個(gè)編碼，且同一區(qū)域內(nèi)的點(diǎn)要素具有相同的編碼。編碼具有這樣一個(gè)特性：字符串越短，代表空間范圍越大，且具有包含關(guān)系，比如編碼為ab的區(qū)域包含編碼為abc的區(qū)域?；诖颂匦裕址幋a就代表著空間的金字塔結(jié)構(gòu)，即LOD?；诳臻g劃分的LOD模型如圖2所示。

3.2 空間劃分閾值

本文提出的點(diǎn)LOD模型構(gòu)建算法是一個(gè)遞歸劃分的過(guò)程，遞歸劃分并不是無(wú)限進(jìn)行，當(dāng)格網(wǎng)被劃分到一定大小就應(yīng)該終止劃分。本文提出的點(diǎn)狀要素LOD的構(gòu)建基本思想是在當(dāng)前比例尺下，一個(gè)可視化符號(hào)所覆蓋的區(qū)域內(nèi)的點(diǎn)群要素只顯示一個(gè)，因此空間劃分的終止條件與可視化符號(hào)大小和比例尺有關(guān)。設(shè)可視化符號(hào)寬度為d，當(dāng)前比例尺為1：x，則屏幕長(zhǎng)度對(duì)應(yīng)地圖上的實(shí)際距離是z，且1：x=d：z。z即為格網(wǎng)劃分的閾值。因此，空間劃分的終止條件為格網(wǎng)寬度小于等于z。閾值z(mì)與比例尺的關(guān)系公式如下：

紙質(zhì)地圖上人眼能夠分辨兩點(diǎn)之間的距離最小為0.1mm[7]，因此可視化符號(hào)最小不應(yīng)該小于0.1mm，即d>=0.1mm，且根據(jù)點(diǎn)形狀的不同，此值還應(yīng)適當(dāng)增大。當(dāng)已知可視化符號(hào)d，則空間劃分的終止閾值就可由公式（1）得出。

4 實(shí)驗(yàn)過(guò)程與結(jié)果分析（Experiment process result analysis）

目前點(diǎn)要素化簡(jiǎn)的算法有凸殼化簡(jiǎn)法、相關(guān)系數(shù)控制法、重力模型法和Voronoi圖法，且大都只適用于居民地綜合[8-12]。僅基于Voronoi圖的簡(jiǎn)化算法應(yīng)用范圍較為廣泛，除了針對(duì)居民地，還可以針對(duì)其他呈點(diǎn)狀分布的地物要素[8]。因此，本文以適用性最高的Voronoi圖法作為對(duì)比對(duì)象，比較兩種算法的抽稀效率和可視化效果。

4.1 實(shí)驗(yàn)方法

本文設(shè)計(jì)了一個(gè)基于B/S架構(gòu)GPS數(shù)據(jù)可視化系統(tǒng)，系統(tǒng)架構(gòu)如圖3所示。實(shí)驗(yàn)以武漢市出租車GPS數(shù)據(jù)為可視化對(duì)象，數(shù)據(jù)量大小約200MB。從服務(wù)器響應(yīng)時(shí)間、數(shù)據(jù)傳輸時(shí)間、可視化時(shí)間和可視化效果這四個(gè)指標(biāo)進(jìn)行評(píng)價(jià)，其中可視化效果指數(shù)據(jù)抽稀之后仍能反映點(diǎn)狀要素空間分布特征，且可視化符號(hào)無(wú)壓蓋。實(shí)驗(yàn)環(huán)境見(jiàn)表1?；诳臻g密度約束的點(diǎn)LOD算法空間劃分閾值等于可視化符號(hào)的寬度，為4mm。

4.2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)統(tǒng)計(jì)不同比例尺下服務(wù)器響應(yīng)時(shí)間、數(shù)據(jù)傳輸時(shí)間、可視化時(shí)間這三個(gè)指標(biāo)，并繪制條形圖，即圖4、圖5、圖6。從圖4中可以看出，本文算法效率明顯高于基于Voronoi圖點(diǎn)LOD算法。實(shí)驗(yàn)表明，基于Voronoi圖的點(diǎn)LOD算法會(huì)導(dǎo)致可視化頁(yè)面易出現(xiàn)無(wú)響應(yīng)情形。

如圖5和圖6所示，對(duì)于數(shù)據(jù)傳輸時(shí)間和可視化時(shí)間這兩個(gè)指標(biāo)，本文提出的點(diǎn)LOD算法比基于Voronoi圖的點(diǎn)LOD算法均占優(yōu)。數(shù)據(jù)傳輸時(shí)間和可視化時(shí)間與點(diǎn)數(shù)正相關(guān)，說(shuō)明區(qū)域一定的條件下，本文算法可以抽稀更多的點(diǎn)。

對(duì)于可視化效果這一指標(biāo)并無(wú)量化數(shù)據(jù)，對(duì)比分析圖7、圖8、圖9可以發(fā)現(xiàn)兩種構(gòu)建LOD的算法均可以減緩符號(hào)壓蓋現(xiàn)象，同時(shí)保持點(diǎn)群空間分布特征。但基于Voronoi圖的點(diǎn)LOD算法本身的原因，在點(diǎn)群稀疏的地方也會(huì)進(jìn)行抽稀，這不滿足GPS數(shù)據(jù)動(dòng)態(tài)可視化需求。

綜上所述，本文提出的基于空間密度約束的點(diǎn)LOD模型構(gòu)建算法顧及點(diǎn)狀要素空間分布特征的同時(shí)，大大減小了算法時(shí)間復(fù)雜度，進(jìn)而提高了可視化效率，比基于Voronoi圖的點(diǎn)LOD算法更優(yōu)。

5 結(jié)論（Conclusion）

針對(duì)GPS軌跡數(shù)據(jù)動(dòng)態(tài)可視化效率低下問(wèn)題，本文將LOD技術(shù)引入可視化系統(tǒng)中。根據(jù)比例尺自適應(yīng)地?cái)?shù)據(jù)抽稀，保留數(shù)據(jù)原有空間分布特征的同時(shí)，提高了可視化效率。鑒于現(xiàn)有針對(duì)點(diǎn)狀要素LOD算法時(shí)間復(fù)雜度高，本文結(jié)合四叉樹的特點(diǎn)，提出了基于空間密度約束的LOD模型構(gòu)建

算法。該算法與適用性高的基于Voronoi圖LOD算法相比，時(shí)間復(fù)雜度低，減少數(shù)據(jù)量的同時(shí)，縮短了服務(wù)器響應(yīng)時(shí)間，從而提高了GPS軌跡數(shù)據(jù)動(dòng)態(tài)可視化效率。

參考文獻(xiàn)（References）

[1] Mao Y，Zhong H，Qi H，et al.An Adaptive Trajectory Clustering Method Based on Grid and Density in Mobile Pattern Analysis[J].Sensors，2017，17（9）：2013.

[2] Cai L，Zhou Y，Liang Y，et al.Research and Application of GPS Trajectory Data Visualization[J].Annals of Data Science，2017（4）：1-15.

[3] Liu Y，Kang C，Gao S，et al.Understanding intra-urban trip patterns from taxi trajectory data[J].Journal of Geographical Systems，2012，14（4）：463-483.

[4] 賈奮勵(lì)，宋國(guó)民.電子地圖顯示中點(diǎn)狀要素LOD模型的建立[J].測(cè)繪學(xué)院學(xué)報(bào)，2002（01）：62-64.

[5] 李佳田，康順，羅富麗.利用層次Voronoi圖進(jìn)行點(diǎn)群綜合[J].測(cè)繪學(xué)報(bào)，2014（12）：1300-1306.

[6] 毋河海.凸殼原理在點(diǎn)群目標(biāo)綜合中的應(yīng)用[J].測(cè)繪工程，1997（01）：1-6.

[7] Hans-Uli Feldmann.Cartographic Generalisation-Topographic Maps[M].Swiss：Swiss Society of Cartography，2005.

[8] 閆浩文，王家耀.基于Voronoi圖的點(diǎn)群目標(biāo)普適綜合算法[J].中國(guó)圖象圖形學(xué)報(bào)，2005（05）：633-636.

[9] Kreveld M J V，Oostrum R W V，Snoeyink J.Efficient Settlement Selection for Interactive Display[J].In Proc.Auto-Carto 13：ACSM/ASPRS Annual Convention Technical Papers， 1997：287-296.

[10] Sadahiro Y.Cluster Perception in the Distribution of Point Objects[J].Cartographica the International Journal for Geographic Information & Geovisualization，1997（03）：49-62.

[11] 李雯靜，李少寧，龍毅，等.利用重力模型進(jìn)行GIS點(diǎn)群選取[J].武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2013，38（8）：945-949.

[12] 艾廷華，劉耀林.保持空間分布特征的群點(diǎn)化簡(jiǎn)方法[J].測(cè)繪學(xué)報(bào)，2002，31（2）：175-181.

作者簡(jiǎn)介：

孫澤昌（1990-），男，碩士，助理工程師.研究領(lǐng)域：GIS與鐵路選線.