嵌入式電子地圖數(shù)據(jù)分塊組織研究

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

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

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

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

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