基于四叉樹算法的地理信息數據管理研究

張 達

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

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

1 瓦片式地圖模型

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

圖1 瓦片式地圖模型

2 瓦片式地圖實現的關鍵技術

2.1 瓦片金字塔的四叉樹結構

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

2.2 瓦片金字塔的存儲結構

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

圖2 四叉樹和瓦片金字塔的對應關系

圖3 瓦片金字塔的存儲結構

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

2.3 瓦片矩陣數據結構

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

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

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

2.4 建立索引機制

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

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

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

3 測繪生產管理系統中的Web地圖

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

圖5 切割成瓦片的地理信息數據生產管理系統

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

4 結語

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

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

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

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

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

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

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