基于四叉樹算法的地理信息數(shù)據(jù)管理研究

張 達

(天津大學 管理與經(jīng)濟學部，天津300072)

地理信息數(shù)據(jù)生產(chǎn)管理系統(tǒng)是測繪行業(yè)數(shù)據(jù)生產(chǎn)管理的核心工具.在測繪行業(yè)中，作業(yè)員如同流水線上的工人一樣，按照一定的工序和步驟，對地理影像數(shù)據(jù)進行加工、處理和編輯，這些工序和成果都在地理信息數(shù)據(jù)生產(chǎn)管理系統(tǒng)中管理.［1］但是測繪行業(yè)的生產(chǎn)管理具有一定的特殊性，因此生產(chǎn)管理一般都以圖幅為單位，在地理信息數(shù)據(jù)生產(chǎn)管理系統(tǒng)中引進Web地圖管理接合表是地理信息數(shù)據(jù)生產(chǎn)行業(yè)發(fā)展的一種趨勢.Web地圖的加載和顯示往往受到瀏覽器和網(wǎng)絡(luò)帶寬的限制，因此為了提高系統(tǒng)的易用性，提升用戶體驗，地理信息數(shù)據(jù)生產(chǎn)管理系統(tǒng)中應(yīng)用了瓦片式地圖的加載方式加載Web地圖，并應(yīng)用四叉樹算法對瓦片金字塔建立索引［2－6］.

1 瓦片式地圖模型

圖1展示了瓦片金字塔在地圖數(shù)據(jù)生成、存儲與調(diào)用過程中的作用.圖中所示模型可分為兩個部分看待:服務(wù)器端的瓦片金字塔地圖庫以及客戶端支持 AJAX(Asynchronous JavaScript and XML，異步JavaScript與XML)技術(shù)的Web瀏覽器.為了構(gòu)建服務(wù)器端的瓦片金字塔地圖庫，首先需要對采集到的原始地理信息數(shù)據(jù)實施顯示符號化，并分層切割成“瓦片”.瓦片(Tile)是一種特殊的圖形文件，因其大多為按行列有序排列正方形柵格圖片，故形象地稱其為瓦片.在一定范圍內(nèi)，在不同比例尺下對地理信息圖片數(shù)據(jù)進行切割，即生成了不同層次的地圖瓦片，形成了一個“瓦片金字塔”.金字塔的一“層”即是一個數(shù)據(jù)集，對應(yīng)著一個特定縮放尺寸下的瓦片圖像數(shù)據(jù)(或其一部分)，越向下則比例尺越大.對于生成的瓦片圖像數(shù)據(jù)，需要采用數(shù)據(jù)庫系統(tǒng)或文件目錄方式進行存儲;為方便管理、調(diào)用、對數(shù)據(jù)進行增刪改等操作，還需要在數(shù)據(jù)上建立索引，由于地圖數(shù)據(jù)是二維圖像數(shù)據(jù)，所可以利用四叉樹結(jié)構(gòu)創(chuàng)建索引.從客戶端的角度來看，瓦片式圖像存儲與管理可以實現(xiàn)僅返回用戶請求層次的圖像數(shù)據(jù)的功能，縮短了加載時間，提高了用戶體驗.為方便用戶在Web瀏覽器上的操作，可以利用AJAX創(chuàng)建的客戶端Web交互功能，滿足其對于瓦片圖像層次及其他地理信息多樣性的顯示需求.

圖1 瓦片式地圖模型

2 瓦片式地圖實現(xiàn)的關(guān)鍵技術(shù)

2.1 瓦片金字塔的四叉樹結(jié)構(gòu)

如上文所述，瓦片金字塔模型常使用四叉樹結(jié)構(gòu)實現(xiàn)，這是由地圖數(shù)據(jù)是二維圖像數(shù)據(jù)這一特性決定的.四叉樹是一種每個節(jié)點最多有四個子樹的數(shù)據(jù)結(jié)構(gòu)，可以用來在數(shù)據(jù)庫中放置與定位文件.金字塔的四叉樹結(jié)構(gòu)簡介如下:定義樹的層數(shù)為n(n∈N，n=0，1，2…)，每層的節(jié)點數(shù)最多不超過bb22n個，第0層的惟一結(jié)點成為根節(jié)點.由于在二維圖像中一個圖元可以被重復地劃分成四部分，所以利用四叉樹表示的金字塔結(jié)構(gòu)非常適合用來描述圖像數(shù)據(jù)在不同比例尺和顯示分辨率下的分割.例如，0層金字塔的圖像數(shù)據(jù)顯示整個區(qū)域內(nèi)的地圖，1層金字塔的四個節(jié)點所包含的數(shù)據(jù)分別顯示整個區(qū)域內(nèi)地圖的1/4，即東北、西北、西南、東南四個區(qū)域.2層金字塔的每個節(jié)點包含的數(shù)據(jù)為整個區(qū)域的1/16，以此類推，如圖2、3所示.

2.2 瓦片金字塔的存儲結(jié)構(gòu)

如第1節(jié)所述，在服務(wù)器端瓦片金字塔圖像數(shù)據(jù)可用數(shù)據(jù)庫或文件目錄的方式存儲與管理.以文件目錄方式為例說明瓦片數(shù)據(jù)存儲結(jié)構(gòu)，在這種方式下，瓦片文件被直接存儲并組織在磁盤的文件目錄中.瓦片金字塔中不同層級上的數(shù)據(jù)被分配到不同的目錄中存儲，該目錄在被命名時除了要體現(xiàn)對應(yīng)的金字塔層數(shù)，還應(yīng)將圖像比例尺、對應(yīng)原始地圖.隨著金字塔層數(shù)增長，低層次瓦片圖像文件的數(shù)量也越來越多，存儲大量文件于單個目錄中的方式不利于瓦片文件的管理與維護.為了解決此類問題，可以引入建立子目錄的思路.例如，對于每一層的瓦片文件再按照瓦片所在的行數(shù)建立二級目錄——由于地圖數(shù)據(jù)切割時是按照行列矩陣的方式進行的，所以二級目錄可以按行數(shù)命名.二級目錄中的瓦片文件名按地圖切片時的列數(shù)排布.例如，二級目錄m中的各瓦片文件命名為m0.jpg、m1.jpg、……、mn.jpg，如圖3 所示.

圖2 四叉樹和瓦片金字塔的對應(yīng)關(guān)系

圖3 瓦片金字塔的存儲結(jié)構(gòu)

當用戶從客戶端提出數(shù)據(jù)請求時，服務(wù)器端將用戶請求中包含的地圖范圍信息進行換算，并定位至對應(yīng)目錄下的瓦片文件，然后將其返回到客戶端.使用文件目錄組織和管理瓦片圖像數(shù)據(jù)有如下優(yōu)點:思路理解直觀，系統(tǒng)設(shè)計與實現(xiàn)簡便，系統(tǒng)響應(yīng)速度快，系統(tǒng)穩(wěn)定性好.但是這種管理方式有其局限性，僅適用于中小型地理信息數(shù)據(jù)生產(chǎn)管理系統(tǒng).在實踐工作中，數(shù)量龐大、來源各異的瓦片圖像數(shù)據(jù)沒有經(jīng)過檢查、清洗與重載的過程，缺乏標準化的統(tǒng)一管理，維護和更新的成本較高.對于大規(guī)模的Web GIS平臺系統(tǒng)，最安全、最具可持續(xù)性的管理方式還是使用地圖數(shù)據(jù)庫技術(shù).地圖數(shù)據(jù)庫管理系統(tǒng)可以快捷高效地實現(xiàn)瓦片圖像數(shù)據(jù)的更新、維護并建立索引.當然，對各個金字塔層的瓦片圖像數(shù)據(jù)建立索引，并且實現(xiàn)瓦片數(shù)據(jù)的清洗、入庫、查詢、發(fā)布等功能都需要通過編寫代碼、查詢語句和存儲過程實現(xiàn)，工作有一定復雜度.地圖數(shù)據(jù)庫管理系統(tǒng)提高了地理信息數(shù)據(jù)管理維護工作的自動化程度，在索引已建立的前提下，系統(tǒng)響應(yīng)速度快，能夠同時兼顧平衡后臺管理和前臺發(fā)布工作，在大多數(shù)應(yīng)用場合中都能適用.

2.3 瓦片矩陣數(shù)據(jù)結(jié)構(gòu)

瓦片圖像數(shù)據(jù)是按行列矩陣方式切割的，每塊瓦片包含了一定經(jīng)緯度范圍內(nèi)的地理信息數(shù)據(jù)，所以首先可以定義二維數(shù)組用以存儲瓦片索引鍵值，一個二維數(shù)組對應(yīng)著金字塔的某一層瓦片，標記為Tile n，其中 n 表示金字塔層數(shù)(n∈N，n=0，1，2…).其數(shù)組中的每個元素對應(yīng)著相應(yīng)瓦片圖像數(shù)據(jù)的存儲路徑，其下標等于其對應(yīng)的瓦片圖像在矩陣格柵坐標中的坐標值.然后再定義一維數(shù)組用以存儲瓦片矩陣的層數(shù)索引鍵值，標記為Layer Tile，該一維數(shù)組中元素值等于其所對應(yīng)的瓦片矩陣層數(shù).上述索引布局如圖4所示.

圖4 基于四叉樹算法的瓦片矩陣布局

上述數(shù)據(jù)結(jié)構(gòu)可以簡便地建立起瓦片圖像數(shù)據(jù)的存儲路徑索引.例如，設(shè)第n層中，某塊瓦片的行號為x，列號為y，則該瓦片的存儲路徑可記為Layer Tile［n］［x］［y］.其中 Layer Tile［n］即 Tile n的起始存儲位置.

2.4 建立索引機制

運用四叉樹數(shù)據(jù)結(jié)構(gòu)構(gòu)建瓦片金字塔模型和存儲路徑索引，每塊瓦片在四叉樹中用一個節(jié)點來表示，如此可以快速定位到金字塔任意一層層的任意一塊瓦片圖像數(shù)據(jù)，高效地管理地理信息數(shù)據(jù).在瓦片金字塔模型基礎(chǔ)上建立線性四叉樹瓦片索引，包含邏輯分塊、物理分塊和瓦片節(jié)點編碼等工作.

邏輯分塊，對應(yīng)于與前述瓦片金字塔模型構(gòu)建工作，規(guī)定瓦片的劃分從地理圖像的左上頂點開始，按照從左至右、從上到下的順序依次進行.同時，四叉樹的層編碼與瓦片金字塔的層編碼應(yīng)當保持一致，即四叉樹的0層對應(yīng)金字塔的0層，四叉樹的葉節(jié)點對應(yīng)金字塔的底層.

物理分塊，該工作在邏輯分塊的基礎(chǔ)上對從地理信息數(shù)據(jù)生成的電子地圖圖像文件進行實際上的切割，生成瓦片圖像數(shù)據(jù).邊界瓦片中的空白多余部分需要處理，可以使用缺省像素值填充.生成的地圖瓦片的文件名可按2.1提出的規(guī)則進行命名.

3 測繪生產(chǎn)管理系統(tǒng)中的Web地圖

在B/S架構(gòu)的地理信息數(shù)據(jù)生產(chǎn)管理中，可以控制地圖瓦片的外輪廓線是否顯示，一般情況下，用戶看到的界面是不顯示地圖瓦片的外輪廓線的，這樣在用戶眼里，地圖仿佛是一個整體，但是為了調(diào)試方便，在系統(tǒng)開發(fā)的時候，會設(shè)置一個隱藏進口用于顯示瓦片地圖的外輪廓線，如圖5所示.Web地圖被分為了若干個正方形的小格子，每個格子都是一張圖片，在瀏覽器中通過腳本語言將他們按照瓦片索引拼接起來.

圖5 切割成瓦片的地理信息數(shù)據(jù)生產(chǎn)管理系統(tǒng)

系統(tǒng)實現(xiàn)了Web地圖的平移、拉框放大、選區(qū)縮小、鼠標滾輪縮放、圖幅的點選和框選，以及制作專題地圖的功能，接合表中，圖號、作業(yè)員、檢查員、生產(chǎn)狀態(tài)等信息都分層顯示，可以自由開閉.

4 結(jié)語

在地理信息數(shù)據(jù)生產(chǎn)管理系統(tǒng)中應(yīng)用瓦片金字塔模型是一項較為復雜的系統(tǒng)工程，瓦片金字塔的生成和瓦片的檢索都依賴四叉樹算法.為了分層次地顯示地圖場景中不同細節(jié)，支持不同縮放級別以及不同分辨率的地圖，瓦片金字塔模型實現(xiàn)了直接提供滿足對應(yīng)需求圖像數(shù)據(jù)的功能，而不必再進行實時電子地圖繪制，極大地提高了Web地圖功能響應(yīng)效率.在服務(wù)器端采用瓦片金字塔地圖庫，并在客戶端的配合以AJAX編寫的查詢操作，降低了來自客戶端的數(shù)據(jù)請求量，提高了服務(wù)器的I/O執(zhí)行效率，從而提升系統(tǒng)的整體性能.

［1］姚真凱.瓦片地圖技術(shù)在水利WebGIS系統(tǒng)中的開發(fā)研究與應(yīng)用［J］.浙江水利科技，2009(6):40－42.

［2］張學之，陽 俊，劉 暢.B/S架構(gòu)下地理信息數(shù)據(jù)加工管理系統(tǒng)地圖相關(guān)算法的探討［J］.測繪與空間地理信息，2012，35(1):40－42.

［3］殷福忠，孫立民.基于瓦片金字塔技術(shù)的地圖發(fā)布平臺開發(fā)研究［J］.測繪與空間地理信息，2010，33(5):16－20.

［4］韋 勝.ArcEngine環(huán)境下實現(xiàn)瓦片地圖的訪問與拼接［J］.武漢大學學報:信息科學版，2012，37(6):737－740.

［5］蘇旭明，譚建成.Web GIS中瓦片地圖關(guān)鍵技術(shù)研究［J］.北京測繪，2012(2):9－12.

［6］張 宏，夏洪山.GIS空間數(shù)據(jù)查詢優(yōu)化技術(shù)研究［J］.哈爾濱商業(yè)大學學報:自然科學版，2010，26(5):570－572.