地图导航项目，道路数据通常如何存储/表示？
Garmin 和 TomTom 等导航系统一直让我着迷。 我想实现小型地图/导航应用程序来尝试各种路径算法并扩展我对它们的了解。
这是一个由两部分组成的问题：
1.) 地图数据如何存储？ - 当您拥有道路网络时，该数据通常如何存储？ 保留哪些数据部分以便稍后重现地图？ 每条道路是否存储为一系列改变方向的点？ 这些数据以什么类型的文件格式存储？ 是否有公开可用的库可以轻松解析这些文件？ 有谁知道如何存储/表示地图/道路数据的具体信息，这将非常有帮助。
2.) 导航/寻路 - 当在此地图数据（Garmin）上进行基本寻路时，我的假设是否正确，即它被转换为有向图？ 每个道路交叉口都是一个顶点，其边权重是顶点之间的距离吗？ 这就是我正在考虑做的事情，这样我就可以尝试一些基本的众所周知的路径算法，看看我会得到什么。
我看过此美国公开地图数据，但我不确定它是如何实现的是表示的，并且它是否足够详细，让我能够从中构建我的有向图。
如果有人有任何信息，我将不胜感激。 您掌握的知识越详细越好。
Navigation systems like the Garmin and TomTom have always fascinated me. I've wanted to implement small map/navigation applications to try out various pathing algorithms and expand on my knowledge of them.
This is a two part question:
1.) How is Map data stored? - When you have a network of roads, how is this data generally stored? What parts of the data are retained inorder to reproduce a map later? Is each road stored as a series of points where it changes direction? What kind of file formats is this data stored in? Are there publically available libraries for easily parsing these files? Does anyone have specifics on how map/road data is stored/represented it would be very helpful.
2.) Navigation/Pathing - When doing basic pathing on this map data (a la Garmin) is my assumption correct that it is converted to a directed graph? Is each road intersection a vertex with the edge weights the distance between vertexes? This is what I was thinking about doing so I could try some basic well known pathing algorithms and see what I get.
I've seen this publically available map data on the US but I'm not sure how it is represented and if it is detailed enough for me to be able to build my directed graph out of it.
If anyone has any information I would appreciate it. The more detailed knowledge you have the better.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
我不知道导航系统单元的具体情况，但在标准 GIS 世界中，地图数据基本上存储为多边形、线和点的集合，每个数据都由其坐标（以及所使用的投影和一些其他参数）进行描述。 例如，此处描述了最常见的格式之一 shapefile， 基于数据库的格式标准位于此处。
我已成功使用此存储模型进行道路显示和路线计算，使用 PostgreSQL、PostGIS 和 PGRouting。 计算是使用常用的图形算法完成的，并且以通用格式存储的数据也存储为图形以允许其应用。 我无法将这种体验推断到嵌入式设备，因为考虑到其有限的计算能力，它们的做法可能会非常不同。 他们很可能预先计算了很多东西。
对于稍微不同的存储方法，请查看 OpenStreetMap
I don't know specifics about navigation system units, but in the standard GIS world, map data is stored basically as a collection of polygons, lines and points, each described by its coordinates (and the projection used and some other parameters). For instance, one of the most common formats, shapefiles, is described here, and the database based format standard is here.
I've successfully used this storage model for roads display and route calculation, using PostgreSQL, PostGIS and PGRouting. Calculations are done using the usual graph algorithms and the data stored in the common format is stored also as a graph to allow for their application. I can't extrapolate that experience to an embedded device as they likely do it very differently given their limited computing capacity. They very probably precalculate lots of stuff.
For a somewhat different approach to storage, check OpenStreetMap
前面的回答都是指GIS系统。 这不是 PND（便携式导航设备）的工作原理。 它们太简单，无法运行桌面/工作站级 GIS 软件。
相反，PND 存储的信息与 Simucal 推测的差不多。 道路被分成几段。 这使得模型变得更加简单。 在一段内，最大速度等属性不会改变。
出于规划目的，路段充当图表中的边。 对于每个节点，传入和传出节点都被存储。 然后使用修改后的 A* 算法完成规划。 边权重通常不是距离，而是估计的行程时间（或者在 TomTom 的情况下，实际的行程时间，测量时间）。
不过，道路网络通常是分层的，普通 A* 启动缓慢。 从一个城镇前往另一个城镇时，A* 会花费大量时间爬行穿过起始城镇。 然而，我们人类知道长途旅行时最好使用高速公路。 这就是它们的目的。 PND 同样更喜欢高速公路。 由于高速公路越来越少，这可以节省大量内存。
另一个优化是向前和向后搜索； 你从双方计划走向某个中间点。 这样做的一大好处是，如果走错了路，还可以从新的起点重新搜索。 由于您的目的地没有移动，因此向后搜索树不会改变。
The previous responses all refer to GIS sytems. This is not how PNDs (Portable Navigation Devices) work. They're far too simple to run desktop/workstattion level GIS software.
Instead, PNDs store information pretty much as Simucal presumed. Roads are broken down into segments. This keeps the model a lot simpler. Within a segment, attributes like maximum speed don't change.
For planning purposes, road segments act as the edges in a graph. For each nodes, incoming and outgoing nodes are both stored. Planning is then done using a modified A* algorithm. Edge weights are typically not distances, but estimated travel time (or in TomToms case, actual, measured time).
Road networks are typically hiearchical, though, and normal A* is a slow starter. When travelling from one town to another, A* will spend excessive amounts of time crawling through the start town. However, we humans know it's best to use highways when travelling longer distances. That's what they're built for. PNDs likewise prefer highways. And as highways are a lot rarer, this saves a lot of memory.
Another optimization is forward and backward search; you plan from both sides towards some middle point. The big advantage of this is that if you take a wrong turn, you can search again from a new start point. The backwards search tree is unchanged as your destination didn't move.
它的确切存储方式取决于格式； 有大量不同的 GIS 格式。 GDAL 是一个优秀的免费图书馆，可以阅读（几乎）所有这些内容。
通常，道路将作为“线图层”存储在文件中，即一组带有附加元数据的折线。 因此，每条道路都会有一系列顶点，并且根据数据的质量，它有望获得诸如是否单向、速度估计和某种连接 ID 之类的信息。
是的，它们通常会转换为有向图来求解。 边权重可以是距离，或者更有用的是，移动该边所花费的时间。
快速求解是预计算和存储空间之间的权衡（嵌入式设备可能需要与 PC 不同的选择）。 有一些非常有趣的算法可以做到这一点。
The exact way it's stored depends on the format; there are heaps of different GIS formats. GDAL is an excellent free library for reading (almost) all of them.
Typically roads will be stored in the file as a "lines layer", that is a set of polylines with attached metadata. So each road will have a series of vertices, and depending on the quality of your data it will hopefully have information such as whether they're one-way or not, speed estimates and some sort of connection id.
Yes, they're normally converted to a directed graph for solving. Edge weights may be distance or, more usefully, the time taken to travel that edge.
Solving quickly is a tradeoff between precomputation and storage space (an embedded device may necessitate a different choice here to a PC). There are some very interesting algorithms out there for doing that.
为了以更多存储空间和有限分辨率为代价提高绘图速度，许多应用程序将使用地理参考栅格格式，例如 GeoTiff。
鉴于下面 Zich 相当坚持的评论
我想我应该在上面添加一些内容。 首先，我将导航系统定义为一种系统，它可以根据您当前的位置帮助您到达您想去的地方，通常通过计算许多可能的替代路线的成本并推荐成本最低的路线。 可能的路线可能由交通方式决定，例如，汽车留在道路上，而山地步行者则不然。 路线成本也可能因运输方式和用户要求而异。 汽车可能希望根据道路速度采取最快的路线，卡车可能希望最省油的路线，爬山者可能希望最安全的直接路线，船只或飞机可能希望避开危险的天气系统，同时最大限度地减少燃料成本和时间花费的路线。
在最简单的层面上，地图和指南针是一个导航系统。 用小屏幕、可缩放光栅地图和 GPS 替换地图，您仍然拥有导航系统。 大多数中低端海上导航系统仍然以这种方式工作，图表代表海岸线和海底，GPS 为您提供位置，回声探测深度。
在更先进的领域，自主机器人导航系统，例如火星漫游者导航系统动态生成 DTM 模型作为短程导航的基础，卫星收集 DEM 进行长程导航。
认为所有导航系统都像消费者 Garmin 或 Tom Tom 设备一样工作是一个相当天真的假设。 FWIW，许多现代 Garmin 设备还包含基于栅格的 DEM 数据，其中低成本 GPS 高度可以非常不准确。
For improved drawing speed at the cost of more storage and limited resolution, many applications will use a georeferenced raster format such as GeoTiff.
Given the rather insistent comment by Zich below that
I thought I'd add a bit to the above. Firstly, I'd define a navigation system as a system that assists you how you get to where you want to go based on your current location, typically by costing a number of possible alternative routes and recommending the lowest cost one. Possible routes may be dictated by mode of transport, cars stay on roads for example whereas hill walkers don't. Costing of routes may vary by mode of transport too as well as user requirements. Cars might want to take quickest route based on road speed, trucks might want most fuel efficient route, hill walkers might want the safest direct route, boats or aeroplanes might want a route that avoids dangerous weather systems, while also minimising fuel cost and time spent.
At the most simple level a map and compass is a navigation system. Replace the map with a small screen, a scalable raster map and a GPS and you still have a navigation system. Most low to medium end maritime navigation systems still work this way, with charts representing the coastline and seabed and GPS to give you location, and echo sounding for depth.
At the more advanced end of the spectrum, autonomous robotic navigation systems such as the Mars Rover navigation system generate DTM models on the fly as a basis for short range navigation, and satellite gathered DEMs for longer range navigation.
To suggest that all navigation systems work like consumer Garmin or Tom Tom devices is a rather naive presumption. FWIW, many modern Garmin devices also include raster based DEM data where low cost GPS heighting can be wildly inaccurate.
如果您想要查看一些代码以了解路由应用程序的工作原理，请尝试查看从 openstreetmap.org 维基。 Navit 和 Gosmore 都是开源的，而且设置起来相当容易。
Gosmore 应用程序的开发人员 Nic Roets 撰写了一篇有趣的帖子 关于他对表示道路矢量数据的选择，您可能也会感兴趣。
如果您想查看运行中的 Gosmore，它是 yournavigation.org 路由网站的后端基于openstreetmap数据。
If you want some code to look at to get some idea about how routing applications work, try having a look at some of the routing applications linked from the openstreetmap.org wiki. Navit and Gosmore are both open source and fairly easy to set up in particular.
Nic Roets, the developer of the Gosmore application wrote an interesting post about his choices for representing the road-vector data that may be of interest to you as well.
If you want to have a look at Gosmore in action, it is the backend of the yournavigation.org routing website based on openstreetmap data.
穆罕默德：好的，我没有详细讨论，因为最初的问题在这方面似乎很舒服。 如果您不熟悉图论，现在阅读一下可能是个好主意 - 维基百科 非常适合介绍。
通常发生的情况是，在 GIS 数据中，道路存储为带有附加元数据的折线。 这对于在屏幕等上显示它们来说很好，但是为了能够导航它们，您需要知道哪些是相互连接的。 因此，在元数据中，道路的每一端通常都有一个节点 ID，因此您可以说“这是路段 457，它从节点 332 到节点 667”。 因此，当您读取 GIS 数据时，您会将其表示为一组由弧连接的节点（即图形）。
如果该元数据不可用，您可以根据哪些道路具有相同的起点/终点坐标来推断（某些不太好的 GIS 数据就是这种情况）。 “定向”位仅意味着道路有方向 - 其中一些道路可以沿任一方向行驶，但其他道路只能单向行驶。
通过有向图寻找路径的典型算法是 Dijkstra 算法； 实践中使用了各种衍生物。 基本上，这涉及沿着图的弧线从一个节点移动到另一个节点，因此您需要适当的数据结构来支持这一点。
希望有帮助...
Mohammed: Okay, I didn't go into much detail there because the original question seemed pretty comfortable on that aspect. If you aren't familiar with graph theory, it's probably a good idea to do a bit of reading on it now - Wikipedia is fine for an introduction.
What typically happens is that in the GIS data the roads are stored as polylines with attached metadata. That's fine for displaying them onscreen etc, but to be able to navigate them you need to know which ones are connected to one another. So in the metadata there's normally a node id for each end of the road, so you can say "this is road segment 457, it goes from node 332 to node 667". So when you read in the GIS data you build up a representation of it as a set of nodes connected by arcs (ie. a graph).
If that metadata's not available you could infer it from which roads have the same start/end coordinates (this is the case with some not-so-wonderful GIS data). The "directed" bit just means that roads have direction - some of them can be travelled along in either direction, but others are only one-way.
The typical algorithm for finding a path through a digraph is Dijkstra's algorithm; various derivatives are used in practice. Basically that involves moving from node to node along the arcs of the graph, so you need the appropriate data structures to support that.
Hope that helps...