地圖匹配算法設計 - 基于Android的車載導航系統(tǒng)的研究與設計

　　3.2　地圖匹配算法設計

　　地圖匹配以某個車輛位置點或某段車行軌跡曲線作為待匹配樣本，以該點或該軌跡曲線附近的所有道路上的位置點或道路曲線作為模板，通過待匹配樣本或模板間的匹配，選擇相似度最高的匹配樣本或模板作為匹配結(jié)果。最后根據(jù)匹配結(jié)果校正定位模塊的定位誤差。車載導航系統(tǒng)中將車輛定位顯示在電子地圖上時，應該根據(jù)車輛的行駛方向，將車輛定位顯示于某一道路上。但是，由于各種誤差（主要是定位技術(shù)的誤差），電子地圖上顯示的車輛會偏離實際的道路，失去其導航的功能；而地圖匹配這一軟件技術(shù)能校正定位技術(shù)的誤差，使車輛位置準確地顯示在電子地圖上。

　　可用來判斷車輛當前可能在哪條路段上行駛的信息主要有3個：當前車輛定位點距候選路段的投影距離、車輛當前行駛方向與候選路段方向的夾角以及候選路段與前一匹配路段的幾何拓撲關(guān)系。一般來講，投影距離和方向夾角越小的候選路段成為匹配路段的可能性越大，反之亦然。此外，與前一匹配路段相同或拓撲相連的候選路段成為匹配路段的可能性大，其余的可能性小。車輛在行駛的過程中，把GPS原始定位點向各待匹配路段作投影，可計算GPS原始定位點與待匹配路段之間的最短距離ri（i=1，…，n）；另外車輛行駛方向與各待匹配路段之間的夾角θi（i=1，…，n）也可以得到，進而計算各待匹配路段的匹配值 λi（i=1，…，n）。

　　地圖匹配算法在進行匹配時的步驟如下：

　　① 通過特征提取把所有的待匹配路段分析、描述，提取出相應的匹配因子。

　　圖2　距離與夾角示意圖

　　② 計算定位點P到各個待匹配路段的最短距離。距離與夾角示意圖如圖2所示。其中r1、r2為要求的最短距離；α1、α2為所求夾角。根據(jù)匹配規(guī)則，依次計算定點P到各個待匹配路段的匹配值。

　?、?把匹配值中最小的路段作為最終匹配路段，并把在此路段上距離原始定位點最近的點作為最終匹配點。

　　3.3　電子地圖顯示模塊設計

　　利用Android平臺開發(fā)導航地圖過程中，主要采用Android提供的MapView和MapActivity兩個類實現(xiàn)。其中 MapView是一個展示地圖的視圖，它可以獲取鍵盤事件來支持地圖的移動和縮放功能，地圖可以以不同的形式來顯示，如街景模式、衛(wèi)星模式等，通過 setSatellite（boolean） 、setTraffic（boolean）和setStreetView（boolean） 方法，同時也支持多層Overlay的使用?？梢栽诘貓D上畫坐標、寫地名、畫圖片等。

　　MapView只能通過MapActivity來建立，因為MapView需要在后臺使用文件系統(tǒng)和網(wǎng)絡。所有這些線程需要在Activity的生命周期中被控制。

　　如何利用電子地圖功能將GPS模塊定位得到的經(jīng)緯度信息在地圖上顯示出來呢？地球上的任何一個地點都可以利用經(jīng)緯度來表示。在Android的類庫中，Point類代表了一個地點的經(jīng)緯度，函數(shù)格式為：Pointment（int latitudeE6，int longitudeE6）。E6是微度，即度數(shù)乘以1000 000。如果要指定地圖地點，須傳遞一個Point類到地圖中。然后調(diào)用setMapLocationCenter方法將地圖移動到合適的位置，最后調(diào)用 MapController對象的animateTo方法將該坐標位置設置為地圖的中心點。在實際應用中，可以使用zoomTo（int）縮放到需要的級別，同時利用mapView.toggleSatellite（）和mapView.toggleTraffic（）來獲得衛(wèi)星圖和路況圖。

　　3.4　最短導航路徑規(guī)劃算法設計

　　求解最短路徑問題的算法中，Dijkstra算法是國內(nèi)外公認的比較成功的算法，該算法通用性強，而且編程實現(xiàn)簡單，是目前理論上比較完善、應用最廣泛的最短路徑分析算法。Dijkstra算法按路徑長度的遞增次序，逐條產(chǎn)生最短路徑。

　　Dijkstra算法的基本思想是：設從頂點V0出發(fā)，搜索從它到其他頂點的最短路徑。把有向圖中的頂點集V分為兩個集合，已求出最短路徑的頂點集合S，尚未確定最短路徑的頂點集合V-S（定義為T）；按最短路徑長度遞增的順序逐個把集合T中的頂點加到集合S中，直到和出發(fā)點V0有路徑相通的所有頂點都包含在集合S中。在整個過程中，V0到集合S中各頂點的最短路徑長度都不大于V0到集合T中的任意頂點的最短路徑長度。

　　設帶權(quán)有向圖G={V，E}，V={V0，V1，…，Vn-1}，用帶權(quán)的鄰接矩陣Arcs表示圖G；Arcs［i］［j］表示弧《 Vi，Vj》上的權(quán)值，S表示已求得的從V0出發(fā)的最短路徑終點的集合；向量D的每個分量D［i］表示當前求得的從始點V0到每個終點Vi的最短路徑的長度，算法描述如下：

　?、?初始化集合S、向量D。S={V0}，D［i］=Arcs［0］［i］（i=0，1，…，n-1）。

　?、?選擇Vj，使得D［j］=min{D［i］|Vi∈V-S}，S=S∪{Vi}。

　?、?修改從V0出發(fā)到集合V-S上任意節(jié)點Vk的最短路徑長度。若D［k］》D［j］+Arcs［j］［k］，則修改D［k］為D［k］=D［j］+Arcs［j］［k］。

　　④ 重復②、③操作n-1次，即可求得從V0到其余各頂點Vi的最短路徑長度。

　　Dijkstra算法的時間復雜度是O（n2）。

　　在實際應用中往往只需要搜素從某一源點到某一或某幾個特定終點的最短路徑，用Dijkstra算法求解，此問題與求源點到其余各頂點的最短路徑的時間復雜度相同，也為O（n2）。