嵌入式電子地圖數據分塊組織研究

摘要：文章研究了基于嵌入式地圖數據分塊組織。嵌入式設備相對于PC機，CPU運算速度較慢，內存較??；而嵌入式設備處理大量的數據時(shí)，CPU和內存資源相對來(lái)說(shuō)比較緊張。實(shí)現基于嵌入式電子地圖的功能，數據存取策略比較重要。本文提出了一種電子地圖數據分塊組織的方法，并且使用雙緩沖技術(shù)在QT／Embcdded平臺上實(shí)現了嵌入式地圖在設備上的漫游，放縮等功能。
關(guān)鍵詞：嵌入式地圖；數據分塊組織；QT／Embedded

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

1 數據的分塊的邊界問(wèn)題
嵌入式設備的LCD一般都比較小，本文使用的LCD大小是480×272。嵌入式設備內存也較小，不能一次把所有電子地圖數據讀入內存，即使能夠把全部數據讀入到內存，在LCD屏幕上也不能完全顯示，這樣大大浪費了有限的內存資源。把嵌入式電子地圖數據分塊組織，節省了嵌入式設備的CPU和內存資源。數據地圖數據分塊后，原來(lái)數據的拓撲關(guān)系被破壞，數據塊的邊界可能出現問(wèn)題。比如一條線(xiàn)從一數據塊中射出，因為數據塊的不同，跨越多個(gè)數據塊的線(xiàn)會(huì )出現線(xiàn)的斷點(diǎn)情況，此時(shí)需要重新求得數據塊邊界與線(xiàn)的交點(diǎn)，重建拓撲。再者，地圖中的線(xiàn)并不是規則的折線(xiàn)，可能從一個(gè)數據塊中射出，而后經(jīng)過(guò)彎轉重新進(jìn)入該數據塊，數據分塊的時(shí)候不考慮這個(gè)問(wèn)題，就會(huì )出現拓撲錯誤。
本文提出了一種數據分塊組織方法。即把一幅地圖按照行列分成行×列個(gè)規則矩形網(wǎng)格(Grid)。為了便于數據的讀取，給格網(wǎng)的每個(gè)網(wǎng)格進(jìn)行編碼。如圖1所示把幾條線(xiàn)路分割成4×5個(gè)網(wǎng)格。

地圖分割成一定數量的規則網(wǎng)格后，為便于讀取格網(wǎng)數據，需要對不同的網(wǎng)格編碼組織。規則格網(wǎng)是一種普遍應用的分塊方法，只需指定在行、列方向上的分塊數m、n，就可以按照相等的間隔把圖像區域分為m×n個(gè)子塊。假如地圖被分割成i×j個(gè)網(wǎng)格的格網(wǎng)，格網(wǎng)中的網(wǎng)格用“mn”、“m，n”或Grid(m,n)表示，其中m表示網(wǎng)格行號，n表示網(wǎng)格列號。簡(jiǎn)單按照行列進(jìn)行編碼，比較方便數據組織。如上圖：從左上角開(kāi)始，第一行的網(wǎng)格編碼為00、01、02、03。這種簡(jiǎn)單的網(wǎng)格編碼，可以很容易找到其相鄰的網(wǎng)格，如用m表示網(wǎng)格的行號，用n表示網(wǎng)
格的列號，則編碼為Grid(m,n)的網(wǎng)格，其左邊的網(wǎng)格編碼為Grid(m，n-1)，右邊相鄰的網(wǎng)格編碼為Grid(m,n+1)，如果找其上方下方的網(wǎng)格，只需行號保持不變列號加1或者減1即可。如果一節點(diǎn)x在網(wǎng)格mn中，則點(diǎn)x屬于網(wǎng)格mn，即x∈Grid(m，n)；如果一條線(xiàn)L在網(wǎng)格mn中，則線(xiàn)L屬于網(wǎng)格mn，即L∈Grid(m，n)。
規則的格網(wǎng)是按照一定的長(cháng)寬劃分的，假如每個(gè)網(wǎng)格的長(cháng)為272、寬為480，一個(gè)長(cháng)為816寬為960的地圖，就被分成3×2個(gè)規則網(wǎng)格。
電子地圖數據包括很多元素，其中包括點(diǎn)、線(xiàn)、區域等。對于地圖上的點(diǎn)來(lái)說(shuō)，可以很容易判斷其屬于哪個(gè)網(wǎng)格。比如點(diǎn)p(242,400)，網(wǎng)格的長(cháng)如果為272，寬為480，則點(diǎn)p屬于第一個(gè)網(wǎng)格，其編碼為00。線(xiàn)或區域分布在很多網(wǎng)格里面，這樣就會(huì )與不同的網(wǎng)格邊界有交點(diǎn)，實(shí)際上這個(gè)交點(diǎn)不一定存在。比如一條線(xiàn)Line，由4個(gè)節點(diǎn)P1、P2、P3、P4組成。Line分布在三個(gè)網(wǎng)格中，如圖2所示。

讀取格網(wǎng)數據時(shí)，如果沒(méi)有讀取到網(wǎng)格10和11的數據，只顯示網(wǎng)格00的數據，那么Line會(huì )出現斷點(diǎn)，如圖3所示：