地图导航项目,道路数据通常如何存储/表示？

像Garmin和TomTom这样的导航系统一直让我着迷.我想实现小型地图/导航应用程序来尝试各种路径算法,并扩展我对它们的了解.

这是一个两部分问题:

1.)地图数据是如何存储的？ - 当您拥有道路网络时,这些数据通常如何存储？保留哪些数据以便以后重现地图？每条道路是否存储为一系列改变方向的点？这些数据存储在哪种文件格式中？是否有公开可用的库来轻松解析这些文件？有没有人有关于如何存储/表示地图/道路数据的具体信息,这将非常有帮助.

2.)导航/路径 - 当在这个地图上做基本路径时(la Garmin),我的假设是正确的,它被转换为有向图？每个道路交叉点是一个顶点与边缘权重顶点之间的距离？这就是我正在考虑的事情,所以我可以尝试一些基本的众所周知的路径算法,看看我得到了什么.

我在美国看到了这个公开可用的地图数据,但我不确定它是如何表示的,如果它足够详细,我可以用它来构建我的有向图.

如果有人有任何信息我会很感激.你拥有的知识越多越好.

之前的回复都涉及GIS系统.这不是PND(便携式导航设备)的工作方式.它们太简单了,无法运行桌面/工作站级GIS软件.

相反,PND存储的信息几乎与Simucal假设的一样.道路分为几个部分.这使模型更加简单.在段内,最大速度等属性不会更改.

出于规划目的,路段充当图表中的边缘.对于每个节点,都存储传入和传出节点.然后使用修改的A*算法完成计划.边缘权重通常不是距离,而是估计的行程时间(或在TomTom的情况下,实际的,测量的时间).

然而,道路网络通常是静态的,正常的A*是一个缓慢的起点.当从一个城镇到另一个城镇旅行时,A*将花费过多的时间在整个城镇中爬行.然而,我们人类知道在长途旅行时最好使用高速公路.这就是他们为之而建的.PND同样喜欢高速公路.由于高速公路很少见,这可以节省大量内存.

另一个优化是前向和后向搜索; 你计划从两边走向某个中间点.这样做的最大好处是,如果你转弯错误,你可以从一个新的起点再次搜索.向后搜索树未更改,因为您的目标未移动.

我不知道有关导航系统单元的细节,但在标准GIS世界中,地图数据基本上存储为多边形,线和点的集合,每个都由其坐标(以及使用的投影和一些其他参数)描述.例如,最常见的格式,shape文件之一,描述在这里,和基于数据库格式标准是这里.

我已成功使用此存储模型进行道路显示和路线计算,使用PostgreSQL,PostGIS和PGRouting.使用通常的图算法进行计算,并且以通用格式存储的数据也作为图形存储以允许其应用.我无法将这种体验推断到嵌入式设备,因为它们的计算能力有限,因此它们的可能性非常不同.他们很可能会预先计算很多东西.

有关不同的存储方法,请查看OpenStreetMap