接上文《手绘地图制作的关键点之“图层覆盖”》,继续来聊聊手绘地图另外一个关键点。那就是“实时导航”。作者:轻轻的烟雾(z281099678)之前在《景区手绘地图(电子地图、智慧导览系统)如何制作》说过:

如果说手绘图本身是面子,让人对地图有第一印象和直观感受,那么实时导航功能则是地图的灵魂和里子。没有实时定位和动态路径规划导航功能的地图,只是一个可观而不可用的花瓶,没有使用价值。没有准确的而高效的实时导航算法,就不能把地图价值在游客手里发挥到最大。

实时导航的手绘地图一、实时导航的最短路径算法但凡与地图相关的产品,都有一个重要的核心,那就是最短路径的计算。手绘地图当然也不例外,甚至说更是其中的典型。最短路径问题,是图论研究中的一个经典算法问题。这里的“图”的概念,和通常意义的图不一样,而是由结点和路径组成的一组数据,而最短路径则旨在寻找图中两结点之间的最短路径。最短路算法常见的几种:bellman-ford、、spfa、floyd。每种算法的思想都有所差异甚至完全不同,适用的场景也各不相同。这里简略聊聊各自的特点。

bellman-ford:可以用于边权为负的图,图中如果有负环,算法会检测出负环。时间复杂度O(VE)。

spfa:bellman-ford的优化算法,本质是bellman-ford,所以适用性和bellman-ford一样。时间复杂度O(KE)。

dijkstra:只能用于边权都为正的图中。时间复杂度O(n2)。

floyd:也可以用于有负权的图中,即使有负环,算法也可以检测出来。可以求任意点的最短路径,有向图和无向图的最小环和最大环。时间复杂度O(n3)。

带权图我们的手绘地图的路径规划算法,则主要用到了dijkstra和floyd。因为dijkstra算法较为高效,而地图里的点,每两个点的距离,一定是正数,不可能两点之间的距离为负。而floyd算法虽然效率较慢,但是他很强大,他可以直接计算出一个地图里所有点之间的路径。所以针对不同场景,我们采取了两者结合的方案。二、实时导航的方向指引在手绘地图里,用户的实时方向,是导航的基础。用户根据自己面对的方向,才能确定导航点位的方向。换言之,才知道当前应该往哪个方向前进。而这一点至关重要的功能的实现,则需要接触HTML5的陀螺仪接口。现在绝大部分的设备都支持此接口。当然,是细节上,安卓设备和苹果设备有一些差异,我们在实现的时候注意兼容即可。

实现了方向的指引,则手绘地图导航功能的基础已经具备。


指北针指示方向

三、实时导航的路径信息当前实时的道路信息主要包括:前方的转向以及距离。

类似于地图APP的导航功能,直行、转向等方向提示可以极大的增加导航的使用体验和实用效果。对于这一点,也可以通过设计算法实现。简单来说,可以通过用户前进的方向,结合规划的路径,来判断前方应当如何转向。当然,这里的细节比较复杂,就不展开赘述。而还需要注意的一点就是,判断用户是否已经偏移路线。


导航提示信息

四、实时导航的智能纠偏手机的定位不可能十分精确,总是在一个区间范围内随机的跳跃。如果按照手机返回的经纬度来定位,则用户会非常活跃的在一个范围内跳跃。这容易让人感觉很迷茫,也非常影响体验,降低实用效果。因此,我们这里需要设计方案来进行智能纠偏。结合导航的规划路径,以及当前的定位,还参考前进的速度、方向等参数,把用户的位置控制在比较真实而友好的位置。

当然,对于确实偏移过大的情况,也不能强行纠偏。因为这种情况,我们其实是不知道到底是用户确实已经偏离太大,还是手机定位出现的较大误差。这时可以根据实际情况提示用户已经偏移路线,或者待手机定位自动恢复正常。


纠偏信息

五、演示案例

展示一个示例。