Garmin 和 TomTom 等导航系统一直让我着迷。我想实现小型地图/导航应用程序来尝试各种路径算法并扩展我对它们的了解。
这是一个两部分的问题：
1.) 地图数据如何存储？ - 当您拥有道路网络时，这些数据通常如何存储？保留哪些部分数据以便以后重现地图？每条道路是否存储为一系列改变方向的点？这些数据以何种文件格式存储？是否有公开可用的库来轻松解析这些文件？有没有人有关于如何存储/表示地图/道路数据的细节，这将非常有帮助。
2.）导航/路径 - 在此地图数据（la Garmin）上进行基本路径时，我的假设是否正确，即它被转换为有向图？每个道路交叉点是否是一个顶点，边缘加权顶点之间的距离？这就是我正在考虑做的，所以我可以尝试一些基本的众所周知的路径算法，看看我得到了什么。
我已经在美国看到了这个公开可用的地图数据，但我不确定它是如何表示的，以及它是否足够详细，让我能够从中构建我的有向图。
如果有人有任何信息，我将不胜感激。掌握的知识越详细越好。
前面的回复都是指 GIS 系统。这不是 PND（便携式导航设备）的工作方式。它们太简单了，无法运行桌面/工作站级别的 GIS 软件。
相反，PND 存储信息的方式与 Simucal 推测的差不多。道路被分成几段。这使模型更加简单。在一个段内，诸如最大速度之类的属性不会改变。
出于规划目的，路段充当图中的边。对于每个节点，传入和传出节点都被存储。然后使用修改后的 A* 算法进行规划。边缘权重通常不是距离，而是估计的行程时间（或者在TomTom的情况下，是实际的测量时间）。
但是，道路网络通常是分层的，正常的 A* 启动速度较慢。当从一个城镇到另一个城镇时，A* 将花费过多的时间在起始城镇爬行。然而，我们人类知道在长途旅行时最好使用高速公路。这就是他们的目的。PND同样更喜欢高速公路。而且由于高速公路很少见，这可以节省大量内存。
另一个优化是前向和后向搜索；你从两边计划到某个中间点。这样做的一大好处是，如果你走错了路，你可以从新的起点重新搜索。向后搜索树没有改变，因为您的目的地没有移动。
我不知道导航系统单位的细节，但在标准 GIS 世界中，地图数据基本上存储为多边形、线和点的集合，每个都由其坐标（以及使用的投影和一些其他参数）描述。例如，这里描述了最常见的格式之一 shapefile，基于数据库的格式标准在这里。
我已经成功地将这个存储模型用于道路显示和路线计算，使用PostgreSQL、PostGIS和PGRouting。使用通常的图形算法进行计算，并且以通用格式存储的数据也存储为图形以允许其应用。我无法将这种体验外推到嵌入式设备，因为考虑到它们有限的计算能力，它们可能会以非常不同的方式进行操作。他们很可能预先计算了很多东西。
对于稍微不同的存储方法，请查看OpenStreetMap
存储的确切方式取决于格式；有很多不同的 GIS 格式。GDAL 是一个优秀的免费图书馆，可以阅读（几乎）所有这些。
通常，道路将作为“线层”存储在文件中，即一组带有附加元数据的折线。因此，每条道路都会有一系列顶点，并且根据您的数据质量，它有望获得诸如它们是否是单向的、速度估计和某种连接 ID 等信息。
是的，它们通常被转换为有向图来求解。边权重可以是距离，或者更有用的是，通过该边所花费的时间。
快速求解是预计算和存储空间之间的权衡（嵌入式设备可能需要与 PC 不同的选择）。有一些非常有趣的算法可以做到这一点。
Mohammed：好的，我没有详细说明，因为最初的问题在这方面看起来很舒服。如果您不熟悉图论，那么现在阅读一下它可能是个好主意 -维基百科很适合作为介绍。
通常发生的情况是，在 GIS 数据中，道路被存储为带有附加元数据的折线。这对于在屏幕上显示它们等很好，但是为了能够导航它们，您需要知道哪些是相互连接的。因此，在元数据中，道路的每一端通常都有一个节点 ID，因此您可以说“这是路段 457，它从节点 332 到节点 667”。因此，当您读取 GIS 数据时，您会将其构建为一组由弧线连接的节点（即图形）。
如果该元数据不可用，您可以从中推断出哪些道路具有相同的开始/结束坐标（这是一些不太好的 GIS 数据的情况）。“有向”位仅表示道路有方向-其中一些可以沿任一方向行驶，而另一些只能单向行驶。
通过有向图寻找路径的典型算法是 Dijkstra 算法；在实践中使用了各种衍生物。基本上这涉及沿着图形的弧从一个节点移动到另一个节点，因此您需要适当的数据结构来支持它。
希望有帮助...
如果您想查看一些代码以了解路由应用程序的工作原理，请尝试查看从openstreetmap.org wiki链接的一些路由应用程序。Navit 和 Gosmore 都是开源的，尤其是相当容易设置。
Gosmore 应用程序的开发人员 Nic Roets 写了一篇有趣的文章，介绍了他对表示您可能感兴趣的道路矢量数据的选择。
如果你想看看 Gosmore 的实际应用，它是 yournavigation.org 基于 openstreetmap 数据的路由网站的后端。
为了以更多存储和有限分辨率为代价提高绘图速度，许多应用程序将使用地理参考光栅格式，例如GeoTiff。
鉴于 Zich 在下面的相当坚持的评论
“所有导航系统中的数据都以矢量形式存在，无一例外！”
我想我会在上面添加一点。首先，我将导航系统定义为一个系统，它可以根据您当前的位置帮助您如何到达您想去的地方，通常是通过计算一些可能的替代路线并推荐成本最低的路线。可能的路线可能由交通方式决定，例如汽车留在道路上，而登山者则不会。路线的成本计算也可能因运输方式以及用户要求而异。汽车可能希望根据道路速度采取最快的路线，卡车可能想要最省油的路线，爬山者可能想要最安全的直达路线，船只或飞机可能想要一条避开危险天气系统的路线，同时尽量减少燃料成本和花费的时间.
在最简单的层面上，地图和指南针是一个导航系统。将地图替换为小屏幕、可扩展的栅格地图和 GPS，您仍然拥有导航系统。大多数中低端海上导航系统仍然以这种方式工作，图表代表海岸线和海床，GPS 为您提供位置，回声探测深度。
在更先进的一端，自主机器人导航系统（如火星漫游者导航系统）动态生成 DTM 模型作为短程导航的基础，而卫星收集的 DEM 则用于远程导航。
建议所有导航系统都像消费者 Garmin 或 Tom Tom 设备一样工作是一个相当幼稚的假设。FWIW，许多现代 Garmin 设备还包括基于光栅的 DEM 数据，其中低成本 GPS 高度可能非常不准确。