引言

近年來，嵌入式Linux得到了快速發(fā)展，它被廣泛應用在移動電話、個人數(shù)字助理（PDA）、媒體播放器、消費性電子產品以及航空航天等領域中。車輛導航系統(tǒng)是空間信息產業(yè)中衛(wèi)星導航產業(yè)的一個重要的發(fā)展領域。導航電子地圖數(shù)據(jù)是導航系統(tǒng)的基礎，其存儲和組織策略是嵌入式導航系統(tǒng)中最基本和重要的一部分。導航是集GIS、GPS、通信、嵌入式軟硬件技術為一體的高度綜合性的高技術產品。在導航系統(tǒng)中電子地圖數(shù)據(jù)量比較大，而嵌入式設備資源比較有限，所以電子地圖數(shù)據(jù)組織的好壞，決定了導航系統(tǒng)本身的成敗。

1 數(shù)據(jù)的分塊的邊界問題

嵌入式設備的LCD一般都比較小，本文使用的LCD大小是480×272。嵌入式設備內存也較小，不能一次把所有電子地圖數(shù)據(jù)讀入內存，即使能夠把全部數(shù)據(jù)讀入到內存，在LCD屏幕上也不能完全顯示，這樣大大浪費了有限的內存資源。把嵌入式電子地圖數(shù)據(jù)分塊組織，節(jié)省了嵌入式設備的CPU和內存資源。數(shù)據(jù)地圖數(shù)據(jù)分塊后，原來數(shù)據(jù)的拓撲關系被破壞，數(shù)據(jù)塊的邊界可能出現(xiàn)問題。比如一條線從一數(shù)據(jù)塊中射出，因為數(shù)據(jù)塊的不同，跨越多個數(shù)據(jù)塊的線會出現(xiàn)線的斷點情況，此時需要重新求得數(shù)據(jù)塊邊界與線的交點，重建拓撲。再者，地圖中的線并不是規(guī)則的折線，可能從一個數(shù)據(jù)塊中射出，而后經過彎轉重新進入該數(shù)據(jù)塊，數(shù)據(jù)分塊的時候不考慮這個問題，就會出現(xiàn)拓撲錯誤。

本文提出了一種數(shù)據(jù)分塊組織方法。即把一幅地圖按照行列分成行×列個規(guī)則矩形網格（Grid）。為了便于數(shù)據(jù)的讀取，給格網的每個網格進行編碼。如圖1所示把幾條線路分割成4×5個網格。

地圖分割成一定數(shù)量的規(guī)則網格后，為便于讀取格網數(shù)據(jù)，需要對不同的網格編碼組織。規(guī)則格網是一種普遍應用的分塊方法，只需指定在行、列方向上的分塊數(shù)m、n，就可以按照相等的間隔把圖像區(qū)域分為m×n個子塊。假如地圖被分割成i×j個網格的格網，格網中的網格用“mn”、“m，n”或Grid（m，n）表示，其中m表示網格行號，n表示網格列號。簡單按照行列進行編碼，比較方便數(shù)據(jù)組織。如上圖：從左上角開始，第一行的網格編碼為00、01、02、03。這種簡單的網格編碼，可以很容易找到其相鄰的網格，如用m表示網格的行號，用n表示網

格的列號，則編碼為Grid（m，n）的網格，其左邊的網格編碼為Grid（m，n-1），右邊相鄰的網格編碼為Grid（m，n+1），如果找其上方下方的網格，只需行號保持不變列號加1或者減1即可。如果一節(jié)點x在網格mn中，則點x屬于網格mn，即x∈Grid（m，n）；如果一條線L在網格mn中，則線L屬于網格mn，即L∈Grid（m，n）。

規(guī)則的格網是按照一定的長寬劃分的，假如每個網格的長為272、寬為480，一個長為816寬為960的地圖，就被分成3×2個規(guī)則網格。

電子地圖數(shù)據(jù)包括很多元素，其中包括點、線、區(qū)域等。對于地圖上的點來說，可以很容易判斷其屬于哪個網格。比如點p（242，400），網格的長如果為272，寬為480，則點p屬于第一個網格，其編碼為00。線或區(qū)域分布在很多網格里面，這樣就會與不同的網格邊界有交點，實際上這個交點不一定存在。比如一條線Line，由4個節(jié)點P1、P2、P3、P4組成。Line分布在三個網格中，如圖2所示。

讀取格網數(shù)據(jù)時，如果沒有讀取到網格10和11的數(shù)據(jù)，只顯示網格00的數(shù)據(jù)，那么Line會出現(xiàn)斷點，如圖3所示：

可以看出，P2和P3的點之間的連線消失了。因為，在網格00的數(shù)據(jù)里并沒有P3點的信息，Line在網格00中顯示的只是P1到P2的連接線。同樣，如果顯示網格10的數(shù)據(jù)，而不顯示網格00的數(shù)據(jù)和網格11的數(shù)據(jù)，在網格10中，Line只有一個點P3，而P3到P2、P4的連接線消失了。此時需要添加節(jié)點并且斷開原來的線段重建拓撲來處理連接線消失的情況。斷開線段p2p3，并求得p2p3與網格00、網格10邊界的交點p，此時p2p屬于網格00中，pp3屬于網格10。如圖4所示。實際上，路段是不規(guī)則的，可能出現(xiàn)如圖5所示的情況。

從圖5可以看出，一條線從網格射出后，然后再次穿過該網格。并與網格有4個交點。在重建拓撲關系的時候，兩次穿過格網中的線要被分成兩部分重新建立拓撲，因為線是由按照一定順序的節(jié)點以及節(jié)點之間的連線組成。當一條線從一網格射出時，如果不斷開該線重建拓撲，則會出現(xiàn)如圖6所示的情況，出現(xiàn)了拓撲錯誤。圖6中的線段pp1實際上是不存在的。

2 拓撲重構算法

有時路網結構很復雜，一條線可能多次穿過同一網格，即一條線與網格的交點可能不只4個，如果不重建拓撲，可能會造成電子地圖畫面更加混亂。所以在每次求得線與網格邊界交點的時候，判斷該線是否從網格中射出，如果線從網格中射出則斷開該線，并求得交點后重新建立拓撲關系。求得線與網格邊界交點的算法如下：

（1）假設當前網格的編碼為mn。

（2）如果線L上的一個節(jié)點P1屬于當前網格mn，判斷線L上p1的前一個節(jié)點P0是否屬于當前網格mn，如果p1不屬于當前網格mn則轉到（3）；如果p0屬于當前網格mn，則轉到（4）：如節(jié)點p0不屬于當前網格mn，如果p1在格網邊界轉到（4）；如果p1不在網格邊界上則求P0和p1的連線與網格邊界的交點p，并把p的信息保存到網格mn中，轉到（4）。此時p節(jié)點屬于網格mn。

（3）如果線L上的一個節(jié)點P1不屬于當前網格，判斷p1在線L上的前一個點P0是否屬于網格mn，如果p0不屬于網格mn，則轉到（4）。如果節(jié)點p0屬于當前網格mn，此時線L從網格mn射出，如果p0在網格邊界，轉到（4）；如果p0不在網格邊界則求P0和P1的連線與網格mn邊界的交點p，把線L斷開重建拓撲關系。并把p的信息保存到網格mn中，轉到（4）。此時節(jié)點p屬于網格mn。

（4）如果線L上的點處理完畢則返回，否則繼續(xù)（2），直到線L上的所有點處理判斷完畢。

流程圖如圖7所示。

3 數(shù)據(jù)分級組織

導航系統(tǒng)在使用過程中，用戶的興趣點不同，會放大電子地圖查看某個區(qū)域更詳細的信息。把電子地圖數(shù)據(jù)分級適合地圖縮放功能的實現(xiàn)。假如電子地圖最初顯示的地圖為x級，放大一次就是顯示x+1級地圖，縮小一次就顯示x-1級地圖。

如圖8所示，瀏覽x級地圖，假設x級地圖顯示m（m=4）塊格網的數(shù)據(jù)；此時地圖放大一級變成x+1級地圖，如果地圖放大了s倍（s=2），此時重新讀取地圖數(shù)據(jù)，只需讀取m／s2塊網格即可。相反，如果地圖縮小一級，x-1級地圖需讀取的網格數(shù)為m×s2（16塊）。

不同級別的地圖數(shù)據(jù)顯示的內容不同。在縮放最小一級地圖時，只顯示地圖的區(qū)界和背景。假如把地圖放大到某一級別，此時電子地圖顯示地區(qū)名稱、高速公路以及名稱、鐵路等地圖信息；再次把該電子地圖放大一級則顯示當前城市的主要地區(qū)名稱和主要路段。放縮的級別劃分根據(jù)不同的地理情況處理。可以認為，高級別的地圖是對低級別地圖的補充。

電子地圖數(shù)據(jù)包括地物點、線、區(qū)域等。地圖的屬性分為地區(qū)名稱、學校名稱、公司名稱等，線又分層劃分為一級道路、二級道路、三級道路、水系等。基于上述電子地圖數(shù)據(jù)的特點，根據(jù)中國行政單位的劃分，把電子地圖數(shù)據(jù)分層。電子地圖數(shù)據(jù)分層可以加快數(shù)據(jù)的讀取，也方便電子地圖數(shù)據(jù)的存儲。

4 嵌入式電子地圖實現(xiàn)

本文使用的嵌入式開發(fā)平臺為：cpu s3c2440，64M nandflash，64M ram，1Gsd卡，480*272 LCD。本文選擇QT／Embedded作為圖形界面，并結合雙緩沖機制QT／Embedded實現(xiàn)了嵌入式電子地圖。

使用雙緩沖畫圖，是避免地圖在漫游、放縮的時候產生屏幕閃爍比較常見的方法。主要過程如下：

（1）把需要顯示的網格，畫在OPximap上。

（2）通過bitblt（）函數(shù)把QPximap上的圖像拷貝到顯示組件。

根據(jù)LCD的尺寸劃分網格大小，即網格的寬為480，長為272。某一級別的電子地圖每次讀取9個網格數(shù)據(jù)，此時LCD屏幕的大小和格網的大小一樣，每次讀取9個網格數(shù)據(jù)，其中一個網格數(shù)據(jù)顯示在LCD屏幕上，其它8個網格的數(shù)據(jù)為預取數(shù)據(jù)。如圖9所示，網格22部分是LCD屏幕：

如圖10所示，圖像拖至左邊邊界。程序每次讀取9個網格數(shù)據(jù)，LCD屏幕尺寸和一個網格一樣大。根據(jù)LCD屏幕大小規(guī)定邊界，比如圖像向x軸正方向移動480像素時，即到了圖像左邊邊界。每次拖動圖像至邊界，然后讀取相鄰網格數(shù)據(jù)，重新繪制地圖，這樣處理節(jié)省了系統(tǒng)開銷，而且不需每次拖動圖像的時候都要重新繪制地圖而造成屏幕抖動或閃爍。

圖像向x軸正向拖動至邊界如圖10所示，網格21為LCD屏幕。在拖動到邊界后，再次拖動地圖，根據(jù)網格的編碼讀取其相鄰的網格數(shù)據(jù)。拖動后的圖像如圖11所示，格網21區(qū)域是LCD屏幕。

地圖放縮時，根據(jù)放縮級別，讀取相應級別的格網數(shù)據(jù)，重新繪制圖像并把圖像拷貝到屏幕相應位置。在本文中，電子地圖數(shù)據(jù)放在sd卡來讀取。

5 結論

依據(jù)本文的數(shù)據(jù)組織策略，不同級別的電子地圖在嵌入式設備上漫游時，圖像都可以平滑移動，時間延遲可以忽略，達到了嵌入式地圖漫游的要求。而且依據(jù)本文的數(shù)據(jù)組織策略，建立一個合適的格網索引機制，在搜索地圖和路徑規(guī)劃時，結合搜索算法，以網格為單位索引，也可以加快數(shù)據(jù)搜索速度。圖12是地圖數(shù)據(jù)測試界面。