黃雁，馮艷杰，孟慶祥

(1.武漢市測繪研究院，湖北武漢 430022； 2.深圳供電規(guī)劃設(shè)計院有限公司，廣東深圳 518054；3.武漢大學(xué)，湖北武漢 430079)

嵌入式GIS中矢量數(shù)據(jù)的快速顯示方法研究

黃雁1?，馮艷杰2，孟慶祥3

(1.武漢市測繪研究院，湖北武漢 430022； 2.深圳供電規(guī)劃設(shè)計院有限公司，廣東深圳 518054；3.武漢大學(xué)，湖北武漢 430079)

嵌入式GIS是近年來一個蓬勃興起的領(lǐng)域，由于嵌入式設(shè)備內(nèi)存小，外設(shè)容量小，CPU的運算能力較弱，致使電子地圖顯示時常出現(xiàn)延遲和抖動的現(xiàn)象。本文針對嵌入式GIS海量矢量數(shù)據(jù)，提出了一種改進(jìn)的多層網(wǎng)格索引技術(shù)對矢量數(shù)據(jù)進(jìn)行檢索，在矢量數(shù)據(jù)的顯示方面，本文采用了雙緩存顯示機制代替了系統(tǒng)默認(rèn)的顯示機制，主緩存用于數(shù)據(jù)的顯示，備用緩存用于組織下一個畫面的數(shù)據(jù)，如此提高顯示效率。

嵌入式GIS；矢量數(shù)據(jù)；網(wǎng)格索引

1 引 言

嵌入式地理信息系統(tǒng)(Embedded Geographic Information System，嵌入式GIS)是新一代地理信息系統(tǒng)發(fā)展的代表方向之一，它是運行在嵌入式設(shè)備(PDA、掌上電腦、智能手機)上的高度濃縮、高度精簡的GIS軟件系統(tǒng)。就目前而言，嵌入式GIS已經(jīng)在城市智能交通系統(tǒng)(ITS)、物流配送系統(tǒng)、車輛導(dǎo)航系統(tǒng)和信息化武器裝備中等得到廣泛應(yīng)用，取得了巨大的經(jīng)濟(jì)效益。

當(dāng)前，“縱向分層，橫向分幅”和基于擴(kuò)展關(guān)系數(shù)據(jù)庫技術(shù)管理矢量地圖數(shù)據(jù)在硬件資源豐富的桌面GIS系統(tǒng)中相對成熟，但由于嵌入式設(shè)備具有存儲空間小、內(nèi)存小、存取速度慢，隨機訪問的速度遠(yuǎn)低于順序訪問的速度等缺點，使得桌面GIS系統(tǒng)中成熟技術(shù)無法很好地應(yīng)用在資源受限的嵌入式GIS系統(tǒng)中，特別是海量矢量空間數(shù)據(jù)的嵌入式存儲、訪問、調(diào)度和顯示等，因此需要對其進(jìn)行深入的研究。為提高地圖操作速度，嵌入式GIS平臺上管理矢量地圖數(shù)據(jù)可以采用數(shù)據(jù)分塊和分級的策略，減少人機交互時地圖數(shù)據(jù)讀取量，從而改善系統(tǒng)響應(yīng)性能。

同時，加速矢量數(shù)據(jù)在嵌入式GIS中的快速顯示，主要從矢量數(shù)據(jù)的預(yù)處理和顯示機制這兩個方面著手，此外還可以通過選擇合適的嵌入式空間索引技術(shù)、采用緩存機制等方法加速矢量數(shù)據(jù)的顯示與響應(yīng)。本文就是在充分研究嵌入式海量矢量數(shù)據(jù)的存儲、調(diào)度和顯示機制的基礎(chǔ)上提出快速顯示方法的。

2 矢量數(shù)據(jù)網(wǎng)格索引

2.1 多層網(wǎng)格索引

網(wǎng)格索引是一種常用的空間索引技術(shù)，其算法較為簡單，便于實現(xiàn)。網(wǎng)格索引的基本思想是將一幅地圖數(shù)據(jù)的地理范圍劃分成m行、n列，得到m×n個小矩形網(wǎng)格，每個網(wǎng)格代表一個索引項，并分配動態(tài)存儲區(qū)，記錄該網(wǎng)格中的地理要素的概要信息，包括要素標(biāo)識、存儲地址和外接矩形等。通過對地圖數(shù)據(jù)進(jìn)行網(wǎng)格劃分，為網(wǎng)格內(nèi)多個地理要素建立索引，檢索時檢索區(qū)域僅為原來的1/(m×n)，從而提高了數(shù)據(jù)訪問速度。

圖1 網(wǎng)格索引示意圖

圖1為網(wǎng)格索引圖，空間要素可能在某一個網(wǎng)格內(nèi)，也可能同時跨越多個網(wǎng)格。在建立網(wǎng)格索引時，先將空間要素抽象成點、線、面三種類型，并按照點、線、面分別存入其相應(yīng)的索引數(shù)組。

網(wǎng)格索引具有的優(yōu)點包括:速度快、可以調(diào)整、算法簡單、查詢方式多樣等。但也存在各種不足，如網(wǎng)格索引對點要素索引時較為有效，每個點都會唯一地落入某個網(wǎng)格中。而對于線要素、面要素，則有可能落入多個網(wǎng)格之中，特別是其幾何形狀很大時，會有許多索引項中記錄了該要素的索引信息，從而造成重復(fù)存儲；網(wǎng)格索引適應(yīng)性差；對劃分后的網(wǎng)格作進(jìn)一步劃分時，存在不一致性的情況，這會影響對地理要素的查找效率等。

針對網(wǎng)格空間索引的優(yōu)點和不足，本文引入了多層網(wǎng)格索引。多層網(wǎng)格索引是對網(wǎng)格索引改進(jìn)，它在充分利用和發(fā)揮網(wǎng)格索引簡單、高效、易實現(xiàn)等優(yōu)勢的基礎(chǔ)上，彌補了網(wǎng)格索引所存在的不足，從而更有效率地實現(xiàn)空間檢索。

多層網(wǎng)格索引的基本思想是將一個圖層規(guī)則地劃分h次:將第一次劃分作為第一層，將圖層劃分成m1×n1大小相等的網(wǎng)格，每個網(wǎng)格的長寬分別為l1和w1，為每個網(wǎng)格分配一個動態(tài)存儲區(qū)，將完全落入該網(wǎng)格的地理要素的外接矩形MBR及標(biāo)識號ID存入動態(tài)存儲區(qū)，若地理要素的外接矩形與網(wǎng)格重合或者在網(wǎng)格的邊界上，則認(rèn)為該地理要素沒有完全包含在這個網(wǎng)格中；第二次劃分圖層時，選取l2和w2為網(wǎng)格的長寬(其中l(wèi)2和w2分別比l1和w1大，一般選擇K＝l2:l1＝w2:w1＞2)，重復(fù)第一次劃分時的操作，將滿足條件的要素放入相應(yīng)的網(wǎng)格中；依此循環(huán)往復(fù)，最后一次的1 ×1劃分為第h層。分析可知，多層網(wǎng)格索引最多需劃分層數(shù)h＝logKMax(m1，n1)＋1。然后開始對各層劃分得到的小網(wǎng)格進(jìn)行統(tǒng)一的編號，從0開始，每個編號對應(yīng)一個小網(wǎng)格，落入同一個小網(wǎng)格內(nèi)的地理要素有著相同的編號，即網(wǎng)格索引號。

這樣，每一個地理要素都屬于某一層某個特定的小網(wǎng)格，不存在索引信息重復(fù)存儲的情況，這樣節(jié)省了索引的存儲空間，減少了做重復(fù)運算的時間開銷。因此，多層網(wǎng)格索引技術(shù)不僅可以提高矢量數(shù)據(jù)的存取訪問效率，而且可以提高空間查詢、空間分析等操作的效率。

2.2 改進(jìn)的多層網(wǎng)格索引

多層網(wǎng)格索引實現(xiàn)過程中最關(guān)鍵的兩個問題是劃分步長K的確定和第一層網(wǎng)格數(shù)m1×n1的確定。但要確定這幾個參數(shù)，要考慮的因素也很多，包括系統(tǒng)內(nèi)存大小、內(nèi)存頁面大小等系統(tǒng)因素以及要素類型、要素外接矩形MBR的長度比例分布、圖層的空間范圍、要素的平均占用空間、要素的分布情況等GIS相關(guān)因素，這些因素都會對多層網(wǎng)格索引的效率產(chǎn)生影響。本節(jié)將圍繞這兩個問題，對多層網(wǎng)格空間索引技術(shù)進(jìn)行改進(jìn)。改進(jìn)過程中，本文暫不考慮硬件因素，僅考慮GIS相關(guān)因素的影響。

在實際建立海量矢量數(shù)據(jù)多層網(wǎng)格索引時，首先考慮的是網(wǎng)格索引參數(shù)的調(diào)配。盡管可以在多層網(wǎng)格索引中允許用戶自行設(shè)置空間索引參數(shù)(K和m1×n1)，用戶可以選取不同的值，并從中選擇效率較高的參數(shù)，來提高空間索引的效率，但這也給用戶造成了很大的困難。因此，一種理想的方法是，系統(tǒng)能夠根據(jù)圖層的特點與查詢的效率，自動給出合適的空間索引參數(shù)，從而得到高效的網(wǎng)格劃分。

其次是對完全包含要素的重定義。多層網(wǎng)格空間索引中，地理要素的網(wǎng)格索引號按以下規(guī)則分配:先檢查要素的外接矩形是否完全落入第一次劃分的某個小網(wǎng)格中，如不在，則看它是否落在第二次劃分的某個小網(wǎng)格中，一直查找，直到找到一個完全包含它的小網(wǎng)格。常用的網(wǎng)格索引是如果地理要素的外接矩形與網(wǎng)格重合或在網(wǎng)格邊界線上，則認(rèn)為該要素不在該網(wǎng)格中，即沒有完全包含。在改進(jìn)的多層網(wǎng)格索引中，為了檢索方便，重新定義了這個概念，將要素外接矩形與網(wǎng)格分界線重合的情況也歸入了完全包含，這使得落入高層網(wǎng)格的要素數(shù)目減少。

再次是多層網(wǎng)格索引的編碼。網(wǎng)格索引本身有自己的編碼方式，而改進(jìn)的多層網(wǎng)格索引顯然不能采用原有的編碼方式了，本文采用一種螺旋編碼方式，離坐標(biāo)原點越近，標(biāo)識號越小，反之標(biāo)識號越大，如圖2所示。編碼的算法如下，其中row、col、level、mi、ni、start分別表示網(wǎng)格劃分后得到的小網(wǎng)格的行號、列號、當(dāng)前網(wǎng)格層次數(shù)、第i層網(wǎng)格行數(shù)、列數(shù)、低層網(wǎng)格中行列數(shù)中較大值的平方和。

圖2 多層網(wǎng)格索引的編碼示意圖

多層網(wǎng)格空間索引是針對線狀、面狀要素等具有空間范圍的地理要素提出來的，主要是為了解決地理要素占用多個網(wǎng)格導(dǎo)致索引信息存儲重復(fù)的問題。用戶可以很容易通過設(shè)置不同的行列數(shù)，選出較好的網(wǎng)格劃分方法，從而建立索引效率較高的索引結(jié)構(gòu)，提高檢索訪問效率。

3 基于改進(jìn)索引的矢量數(shù)據(jù)快速顯示

針對海量矢量數(shù)據(jù)的快速顯示，本文將從矢量數(shù)據(jù)的預(yù)處理和顯示兩個方面進(jìn)行實現(xiàn)。在預(yù)處理方面，本文采用要素分級顯示的方法，并建立一種改進(jìn)的多層網(wǎng)格空間索引對矢量數(shù)據(jù)進(jìn)行檢索；在矢量數(shù)據(jù)顯示方面，本文采用雙緩存技術(shù)。

3.1 矢量數(shù)據(jù)分級顯示

在GIS的常用矢量文件中，空間數(shù)據(jù)是根據(jù)要素的不同幾何形狀分層存儲的，如包括點層、線層和面層。嵌入式電子地圖繪制時，由于屏幕大小有限，如果把所有的地理要素全部繪制在屏幕上，則會造成屏幕上的要素?fù)頂D，影響顯示效果。而且該方法需把所有數(shù)據(jù)加載到內(nèi)存中，而嵌入式設(shè)備的內(nèi)存有限，海量矢量數(shù)據(jù)的實時顯示就會很難實現(xiàn)。為了解決這個問題，本文引入LOD技術(shù)。

LOD(Levels of Detail)意為多細(xì)節(jié)層次，最初主要用于復(fù)雜的3D場景快速繪制、3D動畫等領(lǐng)域，是根據(jù)物體模型的節(jié)點在顯示環(huán)境中所處的位置和重要度，決定物體渲染的資源分配，降低非重要物體的面數(shù)和細(xì)節(jié)度，從而獲得高效率的渲染運算。根據(jù)這一思想，在進(jìn)行二維矢量地圖的繪制過程中，地圖縮小時，根據(jù)比例系數(shù)的縮小，減少無關(guān)的地理要素的顯示，從而顯示輪廓信息；地圖放大時，根據(jù)放大的比例系數(shù)，加載必要的地理要素，從而顯示更多細(xì)節(jié)的要素。這樣不僅減少了內(nèi)存的負(fù)擔(dān)，也達(dá)到了一種“越近內(nèi)容看得越多、細(xì)節(jié)情況越清楚，越遠(yuǎn)則輪廓看得越清楚”的視覺效果。如圖3為使用和未使用數(shù)據(jù)分級技術(shù)的實驗數(shù)據(jù)的顯示效果圖。

圖3 使用和未使用數(shù)據(jù)分級技術(shù)的顯示效果圖

具體對要素進(jìn)行分級時，先要參考地圖要素的分級規(guī)范，根據(jù)要素的重要程度，將不同的要素劃分為不同的顯示等級，簡單地說，即為矢量地圖中的每種要素設(shè)置一個LOD參數(shù)。這個LOD參數(shù)記錄了要素的顯示級別，根據(jù)顯示級別可以決定地圖在放大或縮小到多大比例尺時才顯示相應(yīng)的要素。通過這種方法，在地圖顯示時，可以根據(jù)當(dāng)前的顯示比例，只顯示特定的要素類。當(dāng)比例尺放大或縮小時，就可以根據(jù)變化的比例尺重新確定需要顯示的要素。使用這種方法，則嵌入式設(shè)備的內(nèi)存中不需要載入所有圖層的要素，只需要保存當(dāng)前顯示級別要求加載的圖層。這樣采用LOD技術(shù)進(jìn)行要素分級，減少了內(nèi)存開銷，提高了系統(tǒng)的顯示性能。

表1列出了地圖分層的顯示順序及LOD參數(shù)作為參考，表中的LOD系數(shù)表示僅當(dāng)顯示區(qū)域的范圍小于或等于“LOD系數(shù)×地圖全圖范圍”時才顯示該圖層，其中LOD參數(shù)可以根據(jù)實際情況進(jìn)行相應(yīng)的修改。在實際操作過程中，根據(jù)ESRI Shapefile文件格式的分層存儲情況，為每個Shapefile文件設(shè)定相應(yīng)的名字，并設(shè)置其顯示順序，然后在不同的地圖比較例尺下調(diào)試程序，通過調(diào)試確定每個圖層的LOD系數(shù)，最后建立各個圖層文件名、顯示順序、LOD系數(shù)、最大顯示比例尺的一一對應(yīng)關(guān)系。

矢量地圖分級顯示順序及其LOD參數(shù) 表1

在地圖繪制時，根據(jù)當(dāng)前地圖的比例尺，計算出要顯示的圖層，然后根據(jù)要顯示的圖層從索引中查找相應(yīng)的地理要素，最后把這些要素繪制出來。在實際操作的時候，用戶可以根據(jù)實際情況自己設(shè)定每個圖層的LOD參數(shù)，以增加系統(tǒng)的靈活性。

3.2 雙緩存顯示機制

通過對矢量數(shù)據(jù)建立索引和分級，可以實現(xiàn)對數(shù)據(jù)的快速訪問和調(diào)用，但是，要滿足矢量數(shù)據(jù)的實時和快速顯示，還需要對顯示過程進(jìn)行研究。在地圖瀏覽過程中，漫游響應(yīng)速度是衡量系統(tǒng)實時性能的一項重要指標(biāo)。

“雙緩存”是在原有的緩存基礎(chǔ)上又增加了一個用于提前組織待顯示的數(shù)據(jù)的緩存，它的目的是將數(shù)據(jù)處理過程隱藏起來，在處理器空閑時進(jìn)行，避免數(shù)據(jù)更新過程可見導(dǎo)致漫游停頓現(xiàn)象。雙緩存包括前主緩存和備用緩存，其原理圖如圖4所示，其運行機制如下:主緩存數(shù)據(jù)用于顯示當(dāng)前畫面，備用緩存組織屏幕下一畫面需要的數(shù)據(jù)，繪制完畢后，備用緩存通過拷貝技術(shù)將后臺緩存畫面顯示在屏幕上，而前臺剛好相反，此時又組織下一個畫面的數(shù)據(jù)。這樣一直循環(huán)往復(fù)，屏幕上總是顯示已經(jīng)繪好的畫面。由于在嵌入式GIS中，兩次人機交互操作的間隔時間比較長，而在這段時間內(nèi)系統(tǒng)后臺通過一定的數(shù)據(jù)調(diào)度方式存取和處理數(shù)據(jù)，預(yù)先完成了人機交互時大量的數(shù)據(jù)讀寫和運算操作，于是用戶從屏幕上看起來系統(tǒng)的響應(yīng)速度會得到提高。而且顯示的時候是將數(shù)據(jù)一次性的拷貝到屏幕，這樣可以解決屏幕閃爍的問題。

圖4 雙緩存原理圖

圖5 雙緩存內(nèi)存分配示意圖

使用雙緩存技術(shù)的內(nèi)存空間分配如圖所5示，首先在系統(tǒng)的內(nèi)存中申請兩塊大小相同的緩存空間，把其中用于組織地圖數(shù)據(jù)的顯存空間作為取圖虛擬屏幕，也稱為主緩存；其中用來組織并繪制下一漫游畫面的顯存空間作為繪圖虛擬屏幕，也稱為備用緩存，則當(dāng)前顯示屏幕可以看做是游動于虛擬屏幕當(dāng)中的一個顯示窗口。與兩個虛擬屏幕對應(yīng)，需要另外開設(shè)兩個數(shù)據(jù)緩存A和B，用于存儲地圖顯示過程中所訪問的數(shù)據(jù)。雙緩存的代碼實現(xiàn)主要通過Mouse Down()函數(shù)、Mouse Move()函數(shù)、Mouse Up()函數(shù)和重寫On Paint ()函數(shù)實現(xiàn)。當(dāng)鼠標(biāo)點擊、移動的時候，在內(nèi)存中開辟一塊空間用來組織數(shù)據(jù)，并繪制在虛擬屏幕上，當(dāng)放開鼠標(biāo)時，將該虛擬屏幕拷貝至顯示窗口上，另一虛擬屏幕則等待下一次操作時使用，如此循環(huán)往復(fù)。

雙緩存是嵌入式GIS中實現(xiàn)地圖平滑的一種比較實用的方法，但該方法是以犧牲系統(tǒng)內(nèi)存為代價提高地圖的顯示速度，以空間換取時間，所以采用這種方法必須有足夠的內(nèi)存和顯示緩存，才能達(dá)到比較理想的狀態(tài)。

4 結(jié) 語

本文針對嵌入式GIS系統(tǒng)中矢量數(shù)據(jù)的海量特點，在分析了網(wǎng)格索引和多層網(wǎng)格索引的基礎(chǔ)上，提出了一種改進(jìn)的多層網(wǎng)格索引方法，改進(jìn)方法在保持了多層網(wǎng)格索引技術(shù)的優(yōu)勢的同時，還提高了自身的自適應(yīng)能力；在矢量數(shù)據(jù)顯示方面，本文參考了LOD思想對矢量數(shù)據(jù)進(jìn)行了分級，根據(jù)屏幕顯示比例尺的大小，加載不同的要素層，同時提出了采用雙緩存顯示機制，從而使用戶感覺瀏覽起來更加流暢。

[1] 文江，朱寶山，蔡文濤，李韶芳.基于PDA的矢量圖形的快速顯示[J].嵌入式軟件應(yīng)用，2007，02(2)75～77

[2] 楊小偉，郭福生，馮軍營.嵌入式GIS矢量數(shù)據(jù)存儲技術(shù)研究[J].科技信息，2009(7):454～455

[3] 張麗芬，王曉華，胡景松.基于網(wǎng)格劃分的幾種空間索引[J].北京理工大學(xué)學(xué)報，2004，24(2):140～144

[4] 張麗芬，王曉華，胡景松等.基于網(wǎng)格劃分的幾種空間索引[J].北京理工大學(xué)學(xué)報，2004，24(2):139～144

[5] 梁浩，吳敏君.兩類典型GIS空間索引技術(shù)的分析與評價[J].安陽工學(xué)院學(xué)報，2006，2(20):51～55

[6] 馬文帥.嵌入式GIS開發(fā)方法的研究與實現(xiàn)[D].中國海洋大學(xué)碩士學(xué)位論文，2008

Study on Fast Displaying Vector Data in Embedded GIS

Huang Yan1，F(xiàn)eng Yanjie2，Meng Qingxiang3
(1.Wuhan Geomatic Institute，Wuhan 430022，China；2.Shenzhen Power Supply Planning Design Institute Co.，Ltd.Shenzhen 518054，China；3.Wuhan University，Wuhan 430079，China)

Embedded Geographic Information System(EGIS)is a new rising and flourishing domain.Because the memory of EGIS is low and small，CPU’s computing capability is weak，and the display screen is small，it would cause delay and jitter when the vector map was displaying.This paper would solve the problem of delay of vector data and present a kind of improved multi－level grid index technology to retrieve vector data.In the respect of data displaying，this paper adopts double buffer display mechanism instead of the default display mechanism of the system，the main buffer is used to display the vector map，while the auxiliary buffer is used to organize the data which would show later，and so on to increase desplaying efficiency.

Embedded GIS；Spatial Vector Data；Grid Index

2011—07—04

黃雁(1977—)，女，工程師，主要從事GIS應(yīng)用研究工作。

國家自然科學(xué)基金青年基金(40801152)

1672－8262(2012)01－20－04

P208.1

A