地图导航项目，一般如何存储/表示道路数据? [英] 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.

我在美国看到了此公开可用的地图数据，但我没有确定它的表示方式，以及是否足够详细，以使我能够从中构建有向图.

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.

这篇关于地图导航项目，一般如何存储/表示道路数据?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！