Map-Navigation Project，道路数据通常如何存储/表示? [英] Map-Navigation Project, How is road data generally stored/represented?

问题描述

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

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.) 地图数据如何存储? - 当您拥有道路网络时，这些数据通常如何存储?保留哪些部分数据以便以后重现地图?每条道路是否存储为一系列改变方向的点?这些数据以何种文件格式存储?是否有公开可用的库来轻松解析这些文件?有没有人详细说明地图/道路数据是如何存储/表示的，这将非常有帮助.

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.) 导航/路径 - 在此地图数据(la Garmin)上执行基本路径时，我的假设是否正确，即它被转换为有向图?每个道路交叉点是否是一个顶点，边缘加权顶点之间的距离?这就是我正在考虑做的事情，因此我可以尝试一些众所周知的基本路径算法，看看我得到了什么.

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.

我在美国看到过 this 公开可用的地图数据，但我没有确定它是如何表示的，以及它是否足够详细，让我能够从中构建我的有向图.

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.

推荐答案

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

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.

相反，PND 存储信息的方式与 Simucal 推测的差不多.道路被分成几段.这使模型更加简单.在一个段内，诸如最大速度之类的属性不会改变.

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.

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

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).

不过，道路网络通常是分层的，而普通的 A* 起步较慢.当从一个城镇到另一个城镇时，A* 将花费过多的时间在起始城镇爬行.然而，我们人类知道在长途旅行时最好使用高速公路.这就是他们的目的.PND同样更喜欢高速公路.而且由于高速公路很少见，因此可以节省大量内存.

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.

这篇关于Map-Navigation Project，道路数据通常如何存储/表示?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！