导航引擎
据笔者所知,导航软件的开发多以eVC+WinCE或者C++ + Linux等开发环境为主，核心算法为Dijkstra最短路径算法，需要解决路径分析，行车规划与引导等功能。Djkstra算法是经典的数学算法，其地位不容动摇。
在导航界有个比较奇特的现象。在某次汽车展览会上，各厂家的导航仪齐聚一堂，大家说咱们比一比吧，看谁从输入地点和终点信息后，谁的导航仪规划时间最短……于是，导航仪按路径规划时间排座了。笔者一直奇怪，路径分析算法颠来覆去也就是那么几种，为什么就有这点差别呢？别认为几秒的差距算不得什么，当汽车高速行驶时，1秒就能错过一个路口，有时候还不能掉头回来重新走。
这几年，笔者有幸阅读过KIWI、GDF等国外标准。由于专业词汇理解不到位，两个标准无法深入理解。虽然后来蒋捷等人编写了一部导航标准相关的书籍，奈何忙于其他事情，未曾拜读。最近，在阅读ESRI的关于geometric network的开发帮助时，发现这份帮助就是一个导航地图的模型，不仅可以指导导航地图制作也可以指导开发。猛然间，发现GDF的概念与ESRI的诸多概念如出一辙。
导航地图规格与对应的导航引擎是不可分割的整体。通常，道路规划会在中心线层加上相关的权值进行计算。如果是简单的道路十字相交，这种思路用于解决规划功能不成问题。网上流行的Djkstra算法所提供的数据也是解决简单的十字相交问题。对于复杂问题怎么办？只能借助于地图数据。
ESRI的network由junction和edge构成，在Arcgis的toolbox中创建network后，会自动生成新图层用于保存相关的junction和edge等信息。junction由线段的起点，终点生成，edge则由起点和终点之间的弧段生成。同时将每个junction、edge的拓扑结构都保存起来。笔者暂时只在geodatabase里面对一线层创建过network，在arcmap里做最短路径分析时速度是不言而喻。另外，KIWI里也将路口、交叉口等视为地物信息，不仅可以将空间数据存放于某一图层，而且还有详细的属性信息，包括相关的拓扑结构。
软件算法上的不足应该可以在地图数据上弥补。但是导航地图采用通用gis平台，以及软件从底层开发等策略也限制了功能的完善。国内的企业多采用通过gis平台进行地图加工，有mapinfo、arcgis等，如果软件采用二次开发，可以直接使用到平台的最短路径分析接口。可是，导航引擎多以从底层开发为主，所有的功能，包括最短路径算法都得自己写，而且地图规格也是依照引擎规定的标准而制定。引擎对于地图的读取性较差，只能识别单一标准数据，引擎变则导航地图也得变。
所以，笔者认为，导航仪规划时间长短引擎得承担主要责任，因为所有的地图规范都是依照引擎的要求制定。但是，导航地图数据的结构组织也有不可推卸的责任，这种组织不是指行政区划如何分层，道路如何分层等类似的逻辑结构，而是关乎道路信息的组织，比如是否将路口、交叉路口等视为地物要素，以及如何存放、读取等。笔者认为，导航引擎要上一个台阶，必须在这类问题上得到结论。
（待续）
=====版权所有,转帖请保留作者信息=====
=====汽车导航电子地图及其引擎(3)=====
email:skyforbird@yahoo.com.cn
msn:skyforbird@hotmail.com
==================================
撰稿日期:2006年7月16日
