Garmin 和 TomTom 等导航系统一直让我着迷。我想实现小型 map /导航应用程序来尝试各种路径算法并扩展我对它们的了解。
这是一个两部分的问题:
1.) map 数据如何存储？ - 当您拥有道路网络时，这些数据通常如何存储？保留哪些部分数据以便以后重现 map ？每条道路是否存储为一系列改变方向的点？这些数据以何种文件格式存储？是否有公开可用的库来轻松解析这些文件？有没有人有关于如何存储/表示 map /道路数据的细节，这将非常有帮助。
2.) 导航/路径 - 在此 map 数据(la Garmin)上执行基本路径时，我的假设是否正确，即它被转换为有向图？每个道路交叉点是否是一个顶点，边缘加权顶点之间的距离？这就是我正在考虑做的，所以我可以尝试一些基本的众所周知的路径算法，看看我得到了什么。
我看过this美国公开可用的 map 数据，但我不确定它是如何表示的，以及它是否足够详细，让我能够从中构建我的有向图。
如果有人有任何信息，我将不胜感激。掌握的知识越详细越好。
最佳答案
前面的回复都是指 GIS 系统。这不是 PND(可移植导航设备)的工作方式。它们太简单了，无法运行桌面/工作站级别的 GIS 软件。
相反，PND 存储信息的方式与 Simucal 推测的差不多。道路被分成几段。这使模型更加简单。在一个段内，诸如最大速度之类的属性不会改变。
出于规划目的，路段充当图中的边。对于每个节点，传入和传出节点都被存储。然后使用修改后的 A* 算法进行规划。边缘权重通常不是距离，而是估计的旅行时间(或在 TomTom s 的情况下，实际的测量时间)。
但是，道路网络通常是分层的，正常的 A* 启动速度较慢。当从一个城镇到另一个城镇时，A* 将花费过多的时间在起始城镇爬行。然而，我们人类知道在长途旅行时最好使用高速公路。这就是他们的目的。 PND同样更喜欢高速公路。而且由于高速公路很少见，这可以节省大量内存。
另一个优化是前向和后向搜索；你从两边计划到某个中间点。这样做的一大好处是，如果你走错了路，你可以从新的起点重新搜索。向后搜索树没有改变，因为您的目的地没有移动。
关于navigation - Map-Navigation Project，道路数据通常如何存储/表示？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/177343/