嵌入式電子地圖的實現及路徑查詢優化

摘要:該文主要對桌面電子地圖數據到嵌入式電子地圖數據的轉換進行分析，完成了MIF格式地圖數據的解析，并引入Dijkstra最短路徑算法，實現了路徑查詢優化。

關鍵詞:電子地圖;MIF數據;路徑優化;Dijkstra算法

中圖分類號: TP368.1文獻標識碼:A文章編號:1009-3044(2009)26-7511-02

The Realization of Embedded Electronic Map and the Path Query Optimization

LI Yun-rui

(Department of Computer and Network Engineering， Yulin College， Yulin 719000， China)

Abstract: The design analysised conversion of the desktop electronic map data to the embedded electronic map data.Completed a MIF map data analysis，and introduced Dijkstra shortest path algorithm for path query optimization.

Key words: electronic map; MIF map data;path query optimization; Dijkstra algorithm

電子地圖是利用計算機技術、GIS(地理信息系統)技術、通信技術實現的一種地圖服務方式。可以分為:網絡電子地圖、桌面電子地圖和嵌入式電子地圖[1]。目前嵌入式電子地圖的市場需求越來越大，如汽車導航、個人導航、智能交通系統、車隊管理、資產跟蹤、3G手機位置服務等。嵌入式電子地圖商業應用領域不斷發展。但是嵌入式電子地圖的實現受限于嵌入式設備、軟件開發平臺、電子地圖數據資源等，成熟的桌面電子地圖軟件不能運行在大多數嵌入式設備上，因此電子地圖嵌入式化已經成為一個重要的課題[2]。桌面電子地圖經過幾十年的發展， 已經有相當成熟的桌面和網絡電子地圖產品和地圖數據，如果再開發針對嵌入式電子地圖軟件的電子地圖數據的話對現有的資源是一種浪費，因此系統選擇對已有的流行電子地圖數據(MIF格式數據)進行數據轉換，提取其中有用的信息，再利用這些數據來實現地圖的繪制和查詢等功能。可以充分利用已有資源，節約軟件開發成本，縮短開發時間。

1 MIF格式電子地圖數據解析

美國MapInfo公司對電子地圖數據的存儲有兩種格式TAB格式和MIF格式。MIF格式是MapInfo公司提供的與外界交換數據的一種機制，文件格式公開，是目前電子地圖中精度較高的一種格式[3]。

MapInfo地圖以MIF格式保存時，每個表的數據都以兩個文件保存:一個是擴展名為.MIF的文件，它主要用來保存空間對象的幾何數據;另一個是擴展名為.MID的文件，它主要用來保存與幾何數據相對應的屬性數據，通常這些屬性數據以特殊的定界符分隔，每條記錄一行，末尾加回車換行符。每個MIF文件包含兩個部分:文件頭和數據區。文件頭主要是對MapInfo如何將這些格式的地圖數據生成電子地圖的一些說明信息，數據區則主要是幾何對象的定義。下面分別介紹文件頭和數據區的定義。MIF文件的文件頭定義如表1所示。

MIF文件的數據區跟在文件頭區后面，且必須以單獨一行DATA關鍵字開頭，MIF文件的數據區一般都保存著數目不定的原始幾何數據，每個數據對應一個幾何數據，同時MID文件與它對應，即MIF文件里的每個對象都順序的對應MID文件里的一個屬性數據，如果MID文件里沒有對應的屬性數據，則以空占位符填充。MIF文件里可以制定的幾何對象有Point、Line、Polyline、Region、Arc、Text、Rectangle、Rounded rectangle、Ellipse、Multipoint、Collection。

2 MIF數據解析模塊的實現

對每一行字符串進行分解，找出用空格或“，”分解的每一個單元，并且對前后兩個單元進行判斷，如果前后單元都是沒有用“，”分割的數字，那么這一對數字就是需要進行轉換的坐標，對其進行從高斯投影到屏幕坐標的變換，若遇到CoordSys NonEarth Units “m” Bounds一行則單獨處理，不同于此的單元，表明是其它參數(如多邊形、畫筆顏色、多邊形的個數等)，則不做處理，直接寫入存儲文件。其流程簡介如下:

1)通過調用Windows對話框CfileDialog，得到用戶需要轉換的MIF的文件名fOpenName以及轉換后要存儲的文件名fSaveName。

2)用文本方式打開fOpenName和fSaveName這兩個文件。

3)調用循環，依次讀取fOpenName的每一行，分解轉換處理后，將轉換后的結果存入fSaveName，直至到文件的末尾，程序成功退出。

關鍵類及函數:

1)CGausTrans類。依據坐標轉換原理，在EVC里，專門寫了一個類CGausTrans用來實現坐標轉換，其接口函數原型為:CPoint GausTrans(float convertX，float convertY)

參數convertX和convertY分別表示要轉換的高斯坐標的X和Y坐標。

2)AfxExtractSubString()函數。可以從字符串中解析出特定的字符串，即從整個字符串中找出用某一個符號(空格或“，”號)分割的幾個單元。

3)MFile類，該類繼承自CFile。在標準MFC類庫中，CFile類中有成員函數CFile::ReadString()，該函數在讀取時如果遇到換行符就停止讀取，因此能夠讀取一行內容。然而，在EVC4.0中，為了減少空間占用，CFile類中的該函數被取消，只留下最基本的CFile::Read(void* lpBuf， UINT nCount)和CFile::Write(void* lpBuf， UINT nCount)函數，其中參數lpBuf表示被讀取(或要保存)數據的存放緩沖區，參數nCount表示被讀取(或保存)的字節數。因此，專門寫了MFile類用來讀取和保存MIF文件，其中ReadLine(void* lpBuf)函數代碼如下:

CString MFile::ReadLine(void* lpBuf)

{ CString res(“”)，temp;

while( (temp=CFile::Read(lpBuf，2))!=_T(“\”) )

res += temp;

return temp; }

數據提取模塊完成讀入MIF格式地圖數據文件，并將數據按照嵌入式電子地圖的數據結構保存至內存，以便后續功能的實現;顯示、縮放模塊主要是在屏幕上顯示讀取的電子地圖數據，并根據用戶的需要，實現地圖的縮小或放大功能;GPS數據解析模塊從GPS接收機端讀取GPS數據，并把它轉換成高斯坐標系下的數據，進而在屏幕上顯示該數據對應的地點。

3 Dijkstra算法最優路徑查詢模塊

Dijkstra最短路徑算法是計算有向圖中某一點到其余各點最短路徑的經典算法[4]。具體算法如下:

首先引進一個輔助向量D，它的每個分量D[i]表示當前所找到的從始點v到每個終點vi的最短路徑的長度。它的初態為:若從v到vi有弧，則D[i]為弧上的權值;否則置D[i]為無窮大。顯然，長度為D[j]=min{D[i] | vi∈V}的路徑就是從v出發的長度最短的一條最短路徑。此路徑為(v，vj) [5]。

1)假設用帶權的鄰接矩陣arcs來表示帶權有向圖，arcs[i][j]表示弧上的權值。若不存在，則置arcs[i][j]為無窮大。S為已找到從v出發的最短路徑的終點的集合，它的初始狀態為空集。那么從v出發到圖上其余個點vi可能達到的最短路徑長度的初值為:

vj就是當前求得的一條從v出發的最短路徑的終點。令

4)重復2)、3)共n-1次。求得從v到圖上其余個點的最短路徑是依路徑長度遞增的序列。

給定帶權有向圖G和源點v，如圖2所示，求從V0到G中其余個點的最短路徑。

從圖2中可見，從V0到V3有兩條不同的路徑:(V0，V2，V3)和(V0，V4，V3)，前者長度為60，后者長度為50。因此后者是從V0到V3的最短路徑;而從V0到V1沒有路徑。

若對G實行Dijkstra算法，則所得從v0到其余各點的最短路徑，以及運算過程中D向量的變化狀況，如表2所示。

在MIF文件中，每個對象都有起始坐標組成。查詢路徑時，首先從MID屬性文件中尋找路徑起始點的索引，再查找對應該索引的坐標，然后利用Dijkstra最短路徑算法計算出路徑起始點之間的一條最優化路徑。地點查詢模塊提示用戶輸入要查詢的地點，然后在MID文件中查詢該地點，再在MIF文件數據中查詢與該地點對應的坐標，并在屏幕上以有區別于地圖背景色的顏色顯示;路徑查詢模塊提示用戶輸入要查詢路徑的起點和終點，根據Dijkstra最短路徑算法查詢一條合適的路徑，并在屏幕上高亮顯示該條路徑。

4 結論

地圖數據來自桌面電子地圖軟件產生的MIF格式地圖數據，經過軟件解析后讀取至內存并顯示;地點查詢充分利用了MIF格式文件和MID格式文件的關聯;路徑查詢采用了圖論中的經典算法—Dijkstra最短路徑算法，完成了嵌入式電子地圖路徑查詢優化。該方法可以充分利用已有資源，節約軟件開發成本，提高開發效率。

參考文獻:

[1] 武雪玲，任福.新技術條件下電子地圖的現狀及發展趨勢分析[J].測繪與空間地理信息，2004，27(6):75-78.

[2] 郭勁兵，郭巧，成學文.基于PDA的電子地圖的研究[J].計算機與數字工程，2005，33(7):21-24.

[3] 張成才，孫喜梅，黃建紅.基于MAPINFO電子地圖制作方法研究[J].水土保持研究，2002，9(4):144-147.

[4] 王景存，張曉彤，等.一種基于Dijkstra算法的啟發式最優搜索路徑算法[J].北京科技大學學報，2002，3:346-349.

[5] 李元臣，劉維群.基于Dijkstra算法的網絡最短路徑分析[J].微計算機應用，2004(5):295-298.