嵌入式GIS中矢量數據的快速顯示方法研究

黃雁，馮艷杰，孟慶祥

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

嵌入式GIS中矢量數據的快速顯示方法研究

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

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

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

嵌入式GIS；矢量數據；網格索引

1 引 言

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

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

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

2 矢量數據網格索引

2.1 多層網格索引

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

圖1 網格索引示意圖

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

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

針對網格空間索引的優點和不足，本文引入了多層網格索引。多層網格索引是對網格索引改進，它在充分利用和發揮網格索引簡單、高效、易實現等優勢的基礎上，彌補了網格索引所存在的不足，從而更有效率地實現空間檢索。

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

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

2.2 改進的多層網格索引

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

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

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

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

圖2 多層網格索引的編碼示意圖

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

3 基于改進索引的矢量數據快速顯示

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

3.1 矢量數據分級顯示

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

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

圖3 使用和未使用數據分級技術的顯示效果圖

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

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

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

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

3.2 雙緩存顯示機制

通過對矢量數據建立索引和分級，可以實現對數據的快速訪問和調用，但是，要滿足矢量數據的實時和快速顯示，還需要對顯示過程進行研究。在地圖瀏覽過程中，漫游響應速度是衡量系統實時性能的一項重要指標。

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

圖4 雙緩存原理圖

圖5 雙緩存內存分配示意圖

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

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

4 結 語

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

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

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

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

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

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

[6] 馬文帥.嵌入式GIS開發方法的研究與實現[D].中國海洋大學碩士學位論文，2008

Study on Fast Displaying Vector Data in Embedded GIS

Huang Yan1，Feng 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應用研究工作。

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

1672－8262(2012)01－20－04

P208.1

A