手绘地图制作的关键点之“实时导航”

接上文《手绘地图制作的关键点之“图层覆盖”》，继续来聊聊手绘地图另外一个关键点。

那就是“实时导航”。

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

导航提示信息

四、实时导航的智能纠偏

手机的定位不可能十分精确，总是在一个区间范围内随机的跳跃。如果按照手机返回的经纬度来定位，则用户会非常活跃的在一个范围内跳跃。这容易让人感觉很迷茫，也非常影响体验，降低实用效果。

因此，我们这里需要设计方案来进行智能纠偏。结合导航的规划路径，以及当前的定位，还参考前进的速度、方向等参数，把用户的位置控制在比较真实而友好的位置。

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

纠偏信息

五、演示案例

展示一个示例。