野外激情视频,麻豆视频在线

手繪地圖制作的關(guān)鍵點(diǎn)之“實(shí)時導(dǎo)航”

發(fā)布時間：2022/08/18 點(diǎn)擊數(shù)：3091

接上文《手繪地圖制作的關(guān)鍵點(diǎn)之“圖層覆蓋”》，繼續(xù)來聊聊手繪地圖另外一個關(guān)鍵點(diǎn)。

那就是“實(shí)時導(dǎo)航”。

作者：輕輕的煙霧（z281099678）

之前在《景區(qū)手繪地圖（電子地圖、智慧導(dǎo)覽系統(tǒng)）如何制作》說過：

如果說手繪圖本身是面子，讓人對地圖有第一印象和直觀感受，那么實(shí)時導(dǎo)航功能則是地圖的靈魂和里子。沒有實(shí)時定位和動態(tài)路徑規(guī)劃導(dǎo)航功能的地圖，只是一個可觀而不可用的花瓶，沒有使用價值。沒有準(zhǔn)確的而高效的實(shí)時導(dǎo)航算法，就不能把地圖價值在游客手里發(fā)揮到最大。

實(shí)時導(dǎo)航的手繪地圖

一、實(shí)時導(dǎo)航的最短路徑算法

但凡與地圖相關(guān)的產(chǎn)品，都有一個重要的核心，那就是最短路徑的計(jì)算。手繪地圖當(dāng)然也不例外，甚至說更是其中的典型。

最短路徑問題，是圖論研究中的一個經(jīng)典算法問題。這里的“圖”的概念，和通常意義的圖不一樣，而是由結(jié)點(diǎn)和路徑組成的一組數(shù)據(jù)，而最短路徑則旨在尋找圖中兩結(jié)點(diǎn)之間的最短路徑。

最短路算法常見的幾種：bellman-ford、、spfa、floyd。每種算法的思想都有所差異甚至完全不同，適用的場景也各不相同。這里簡略聊聊各自的特點(diǎn)。

bellman-ford：可以用于邊權(quán)為負(fù)的圖，圖中如果有負(fù)環(huán)，算法會檢測出負(fù)環(huán)。時間復(fù)雜度O（VE）。

spfa：bellman-ford的優(yōu)化算法，本質(zhì)是bellman-ford，所以適用性和bellman-ford一樣。時間復(fù)雜度O（KE）。

dijkstra：只能用于邊權(quán)都為正的圖中。時間復(fù)雜度O（n2）。

floyd：也可以用于有負(fù)權(quán)的圖中，即使有負(fù)環(huán)，算法也可以檢測出來?？梢郧笕我恻c(diǎn)的最短路徑，有向圖和無向圖的最小環(huán)和最大環(huán)。時間復(fù)雜度O（n3）。

帶權(quán)圖

我們的手繪地圖的路徑規(guī)劃算法，則主要用到了dijkstra和floyd。因?yàn)閐ijkstra算法較為高效，而地圖里的點(diǎn)，每兩個點(diǎn)的距離，一定是正數(shù)，不可能兩點(diǎn)之間的距離為負(fù)。而floyd算法雖然效率較慢，但是他很強(qiáng)大，他可以直接計(jì)算出一個地圖里所有點(diǎn)之間的路徑。

所以針對不同場景，我們采取了兩者結(jié)合的方案。

二、實(shí)時導(dǎo)航的方向指引

在手繪地圖里，用戶的實(shí)時方向，是導(dǎo)航的基礎(chǔ)。

用戶根據(jù)自己面對的方向，才能確定導(dǎo)航點(diǎn)位的方向。換言之，才知道當(dāng)前應(yīng)該往哪個方向前進(jìn)。

而這一點(diǎn)至關(guān)重要的功能的實(shí)現(xiàn)，則需要接觸HTML5的陀螺儀接口?，F(xiàn)在絕大部分的設(shè)備都支持此接口。當(dāng)然，是細(xì)節(jié)上，安卓設(shè)備和蘋果設(shè)備有一些差異，我們在實(shí)現(xiàn)的時候注意兼容即可。

實(shí)現(xiàn)了方向的指引，則手繪地圖導(dǎo)航功能的基礎(chǔ)已經(jīng)具備。

指北針指示方向

三、實(shí)時導(dǎo)航的路徑信息

當(dāng)前實(shí)時的道路信息主要包括：前方的轉(zhuǎn)向以及距離。

類似于地圖APP的導(dǎo)航功能，直行、轉(zhuǎn)向等方向提示可以極大的增加導(dǎo)航的使用體驗(yàn)和實(shí)用效果。對于這一點(diǎn)，也可以通過設(shè)計(jì)算法實(shí)現(xiàn)。簡單來說，可以通過用戶前進(jìn)的方向，結(jié)合規(guī)劃的路徑，來判斷前方應(yīng)當(dāng)如何轉(zhuǎn)向。當(dāng)然，這里的細(xì)節(jié)比較復(fù)雜，就不展開贅述。而還需要注意的一點(diǎn)就是，判斷用戶是否已經(jīng)偏移路線。

導(dǎo)航提示信息

四、實(shí)時導(dǎo)航的智能糾偏

手機(jī)的定位不可能十分精確，總是在一個區(qū)間范圍內(nèi)隨機(jī)的跳躍。如果按照手機(jī)返回的經(jīng)緯度來定位，則用戶會非?；钴S的在一個范圍內(nèi)跳躍。這容易讓人感覺很迷茫，也非常影響體驗(yàn)，降低實(shí)用效果。

因此，我們這里需要設(shè)計(jì)方案來進(jìn)行智能糾偏。結(jié)合導(dǎo)航的規(guī)劃路徑，以及當(dāng)前的定位，還參考前進(jìn)的速度、方向等參數(shù)，把用戶的位置控制在比較真實(shí)而友好的位置。

當(dāng)然，對于確實(shí)偏移過大的情況，也不能強(qiáng)行糾偏。因?yàn)檫@種情況，我們其實(shí)是不知道到底是用戶確實(shí)已經(jīng)偏離太大，還是手機(jī)定位出現(xiàn)的較大誤差。這時可以根據(jù)實(shí)際情況提示用戶已經(jīng)偏移路線，或者待手機(jī)定位自動恢復(fù)正常。

糾偏信息

五、演示案例

視頻展示一個示例。

手繪地圖制作的關(guān)鍵點(diǎn)之“實(shí)時導(dǎo)航”

一、實(shí)時導(dǎo)航的最短路徑算法

二、實(shí)時導(dǎo)航的方向指引

三、實(shí)時導(dǎo)航的路徑信息

四、實(shí)時導(dǎo)航的智能糾偏

五、演示案例

一、實(shí)時導(dǎo)航的最短路徑算法

三、實(shí)時導(dǎo)航的路徑信息

四、實(shí)時導(dǎo)航的智能糾偏

五、演示案例