基于Android的車載導(dǎo)航系統(tǒng)的研究與設(shè)計(jì)
加入技術(shù)交流群
可用來判斷車輛當(dāng)前可能在哪條路段上行駛的信息主要有3個(gè)：當(dāng)前車輛定位點(diǎn)距候選路段的投影距離、車輛當(dāng)前行駛方向與候選路段方向的夾角以及候選路段與前一匹配路段的幾何拓?fù)潢P(guān)系。一般來講，投影距離和方向夾角越小的候選路段成為匹配路段的可能性越大，反之亦然。此外，與前一匹配路段相同或拓?fù)湎噙B的候選路段成為匹配路段的可能性大，其余的可能性小。車輛在行駛的過程中，把GPS原始定位點(diǎn)向各待匹配路段作投影，可計(jì)算GPS原始定位點(diǎn)與待匹配路段之間的最短距離ri(i=1，…，n)；另外車輛行駛方向與各待匹配路段之間的夾角θi(i=1，…，n)也可以得到，進(jìn)而計(jì)算各待匹配路段的匹配值λi(i=1，…，n)。
地圖匹配算法在進(jìn)行匹配時(shí)的步驟如下：
①通過特征提取把所有的待匹配路段分析、描述，提取出相應(yīng)的匹配因子。
②計(jì)算定位點(diǎn)P到各個(gè)待匹配路段的最短距離。距離與夾角示意圖如圖2所示。其中r1、r2為要求的最短距離；a1、a2為所求夾角。根據(jù)匹配規(guī)則，依次計(jì)算定點(diǎn)P到各個(gè)待匹配路段的匹配值。本文引用地址：http://www.biyoush.com/article/196865.htm
③把匹配值中最小的路段作為最終匹配路段，并把在此路段上距離原始定位點(diǎn)最近的點(diǎn)作為最終匹配點(diǎn)。
3．3 電子地圖顯示模塊設(shè)計(jì)
利用Android平臺(tái)開發(fā)導(dǎo)航地圖過程中，主要采用Androld提供的MapView和MapActivity兩個(gè)類實(shí)現(xiàn)。其中MapView是一個(gè)展示地圖的視圖，它可以獲取鍵盤事件來支持地圖的移動(dòng)和縮放功能，地圖可以以不同的形式來顯示，如街景模式、衛(wèi)星模式等，通過setSatellite(boolean)、setTraffic(boolean)和setStreetView(boolean)方法，同時(shí)也支持多層Overlay的使用?？梢栽诘貓D上畫坐標(biāo)、寫地名、畫圖片等。MapView只能通過MapActivity來建立，因?yàn)镸apView需要在后臺(tái)使用文件系統(tǒng)和網(wǎng)絡(luò)。所有這些線程需要在Activity的生命周期中被控制。
如何利用電子地圖功能將GPS模塊定位得到的經(jīng)緯度信息在地圖上顯示出來呢?地球上的任何一個(gè)地點(diǎn)都可以利用經(jīng)緯度來表示。在Andro id的類庫中，Point類代表了一個(gè)地點(diǎn)的經(jīng)緯度，函數(shù)格式為：Pointment(intIatitudeE6，int longitudeE6)。E6是微度，即度數(shù)乘以1000 000。如果要指定地圖地點(diǎn)，須傳遞一個(gè)Point類到地圖中。然后調(diào)用setMapLocationCenter方法將地圖移動(dòng)到合適的位置，最后調(diào)用MapCont roller對(duì)象的animateTo方法將該坐標(biāo)位置設(shè)置為地圖的中心點(diǎn)。在實(shí)際應(yīng)用中，可以使用zoomTo(int)縮放到需要的級(jí)別，同時(shí)利用mapVie w．toggleSatellite()和mapView．toggle-Traffic()來獲得衛(wèi)星圖和路況圖。
3．4 最短導(dǎo)航路徑規(guī)劃算法設(shè)計(jì)
求解最短路徑問題的算法中，Dijkstra算法是國(guó)內(nèi)外公認(rèn)的比較成功的算法，該算法通用性強(qiáng)，而且編程實(shí)現(xiàn)簡(jiǎn)單，是目前理論上比較完善、應(yīng)用最廣泛的最短路徑分析算法。Dijkstra算法按路徑長(zhǎng)度的遞增次序，逐條產(chǎn)生最短路徑。
Dijkstra算法的基本思想是：設(shè)從頂點(diǎn)V0 出發(fā)，搜索從它到其他頂點(diǎn)的最短路徑。把有向圖中的頂點(diǎn)集V分為兩個(gè)集合，已求出最短路徑的頂點(diǎn)集合S，尚未確定最短路徑的頂點(diǎn)集合V-S(定義為T)；按最短路徑長(zhǎng)度遞增的順序逐個(gè)把集合T中的頂點(diǎn)加到集合S中，直到和出發(fā)點(diǎn)V0有路徑相通的所有頂點(diǎn)都包含在集合S中。在整個(gè)過程中，V0到集合S中各頂點(diǎn)的最短路徑長(zhǎng)度都不大于V0到集合T中的任意頂點(diǎn)的最短路徑長(zhǎng)度。
設(shè)帶權(quán)有向圖G={V，E}，V={V0，V1，…，Vn-1}，用帶權(quán)的鄰接矩陣Arcs表示圖G；Arcs[i][j]表示弧Vi，Vj>上的權(quán)值，S表示已求得的從V0 出發(fā)的最短路徑終點(diǎn)的集合；向量D的每個(gè)分量D[i]表示當(dāng)前求得的從始點(diǎn)V0到每個(gè)終點(diǎn)Vi的最短路徑的長(zhǎng)度，算法描述如下：
①初始化集合S、向量D。S={V0}，D[i]=Arcs[0][i](i=0，1，…，n-1)。
②選擇Vj，使得D[j]=min{D[i]|Vi∈V-S}，S=SU{Vi}。
③修改從V0出發(fā)到集合V-S上任意節(jié)點(diǎn)Vk的最短路徑長(zhǎng)度。若D[k]>D[j]+Arcs[j][k]，則修改D[k]為D[k]=D[j]+Arcs[j][k]。
④重復(fù)②、③操作n-1次，即可求得從V0到其余各頂點(diǎn)Vi的最短路徑長(zhǎng)度。
Dijkstra算法的時(shí)間復(fù)雜度是O(n2)。在實(shí)際應(yīng)用中往往只需要搜素從某一源點(diǎn)到某一或某幾個(gè)特定終點(diǎn)的最短路徑，用Dijkstra算法求解，此問題與求源點(diǎn)到其余各頂點(diǎn)的最短路徑的時(shí)間復(fù)雜度相同，也為O(n2)。
評(píng)論