地图路由,谷歌地图?

我一直对Map Routing很感兴趣,但是我从来没有发现任何好的介绍性(甚至是高级的)关于它的教程。有人有任何指针,提示等?

Update: I'm primarily looking for pointers as to how a map system is implemented (data structures, algorithms, etc).

0
额外 编辑
意见: 1

9 答案

查看开放式街道地图项目,了解如何在真正免费的软件中处理这类事情项目仅使用用户提供的和许可的数据,并有一个维基,其中包含您可能会感兴趣的内容

几年前,那些参加比赛的队员们都很轻松,并且回答了很多问题,所以我没有看到他们为什么仍然不是很好。

0
额外

Instead of learning APIs to each map service provider ( like Gmaps, Ymaps api) Its good to learn Mapstraction

“Mapstraction是一个为各种JavaScript映射API提供通用API的库”

我建议你去URL并学习一个通用的API。也有很多使用方法。

0
额外

谷歌地图路线寻找功能的工程师之一Barry Brumitt在这个话题上写了一篇关于这个话题的文章:

The road to better path-finding 11/06/2007 03:47:00 PM

0
额外

通过地图路由,你的意思是找到沿着街道网络的最短路径?

Dijkstra shortest-path algorithm is the best known. Wikipedia has not a bad intro: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

这里有一个Java applet,你可以在其中看到它: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html 和Google,您可以将您引导至任何语言的源代码。

任何生成驾驶路线的实际实现都将包含相当多的街道网络数据,这些数据描述与穿越链路和节点相关的成本?道路网络层次,平均速度,交叉口优先级,交通信号链接,禁止转弯等。

0
额外
地图通常太大而不允许使用标准的最短路径算法,因此您必须创建一些启发式来选择子图。此外,您可以使用完全不同的启发式方法(例如高速公路,..)来查找路线。
额外 作者 Don Johe,

我还没有找到一个关于路由的好教程,但有很多代码需要阅读:

有GPL路由应用程序使用Openstreetmap数据,例如 Gosmore ,适用于Windows(+ mobile)和Linux。有许多有趣的[应用程序使用相同的数据,但gosmore有一些很酷的用途例如与网站接口

路由的最大问题是数据不好,你永远不会获得足够好的数据。所以如果你想尝试一下,保持你的测试非常本地化,这样你就可以更好地控制数据。

0
额外

A *实际上更接近生产映射算法。与Dijikstra的原始算法相比,它需要少得多的探索。

0
额外
实际上,就我所知,修改的D *是通常使用的。
额外 作者 mmcdole,

从概念的角度来看,想象一下,把一块石头扔进池塘里,看着涟漪。路线代表池塘和石头的起始位置。

当然,当距离n增加时,算法将不得不搜索n ^ 2路径的一部分比例。你会带你开始的位置,并检查从这一点的所有可用路径。然后递归调用这些路径末尾的点等等。

您可以通过不在路径上重复支持来提高性能,通过不重新检查路由,如果路由已经被覆盖,并且放弃路径花费很长时间。

另一种方法是使用蚂蚁信息素方法,蚂蚁从起点随机爬行并留下一条香味,这样就形成了越过给定路径的蚂蚁。如果你从起点和终点发送(足够)蚂蚁,那么最终气味最强的路径将是最短的。这是因为考虑到蚂蚁以统一的速度步行,最短路径将在特定的时间段内访问更多次。

EDIT @ Spikie

作为如何实现池塘算法的进一步解释 - 需要强调的潜在数据结构:

您需要将地图存储为网络。这仅仅是它们之间的一组节点边缘。一组节点构成 route 。一个边连接两个节点(可能是同一个节点),并有一个相关的 cost ,例如 distancetime 来遍历边。边缘既可以是双向的,也可以是单向的。可能最简单的方法是只有单向节点,双节点之间的双向传输(即A到B的一个边和B到A的另一个边)。

举例来说,假设三个火车站以等边三角形向上指向。他们之间还有另外三个电台。边缘将所有相邻的站点连接在一起,最后的图表将在较大的三角形内部放置一个倒三角形。

标签节点从左下角开始,从左到右,从A,B,C,D,E,F(顶部的F)开始。

假定边缘可以在任一方向上移动。每条边都有1公里的费用。

好的,所以我们希望从左下角的路线A到最上面的路线F.有许多可能的路线,包括那些可以自己翻倍的路线,例如, ABCEBDEF。

我们有一个例程,称为 NextNode ,它接受 nodecost ,并为它可以前往的每个节点调用自身。

显然,如果我们让这个例程运行,它最终会发现所有的路由,包括可能无限长的路由(例如ABABABAB等)。我们通过检查 cost 来阻止这种情况的发生。每当我们访问一个以前没有访问过的节点时,我们就把这个节点的成本和节点都放在这个节点上。如果在检查现有成本之前已经访问了节点,并且如果我们更便宜,那么我们更新节点并继续(递归)。如果我们更昂贵,那么我们跳过节点。如果所有节点都被跳过,那么我们退出例程。

如果我们击中目标节点,那么我们也会退出例程。

通过这种方式检查所有可行的路线,但最重要的是只有那些成本最低的路线。到这个过程结束时,每个节点将获得到达该节点的最低成本,包括我们的目标节点。

为了获得路线,我们从目标节点向后工作。由于我们存储了来自节点的节点以及成本,所以我们只是向后跳跃建立路线。对于我们的例子,我们最终会得到如下结果:

Node A - (Total) Cost 0 - From Node None
Node B - Cost 1 - From Node A
Node C - Cost 2 - From Node B
Node D - Cost 1 - From Node A
Node E - Cost 2 - From Node D / Cost 2 - From Node B (this is an exception as there is equal cost)
Node F - Cost 2 - From Node D

所以最短的路线是ADF。

0
额外
@乔纳森请你能给我一些关于池塘算法中的石头的细节,以及我如何将它应用到map.let上,我说我在某一点上,并且我想在涟漪中搜索,然后再移动到下一个外部涟漪。和我知道的伙计和2年迟到的谈话
额外 作者 Spikie,

关于每次遍历的成本,我还会想到另一个想法,但会增加计算所需的时间和处理能力。

Example: There are 3 ways I can take (where I live) to go from point A to B, according to the GoogleMaps. Garmin units offer each of these 3 paths in the Quickest route calculation. After traversing each of these routes many times and averaging (obviously there will be errors depending on the time of day, amount of caffeine etc.), I feel the algorithms could take into account the number of bends in the road for high level of accuracy, e.g. straight road of 1 mile will be quicker than a 1 mile road with sharp bends in it. Not a practical suggestion but certainly one I use to improve the result set of my daily commute.

0
额外

从我在这个领域工作的经验来看,A *非常好。它(如上所述)比Dijkstra的算法更快,但对于一个普通的程序员来说,实现和理解起来仍然很简单。

建立路线网络是最困难的部分,但这可以分解为一系列简单的步骤:获取所有道路;按顺序对点进行排序;在不同的道路上将相同的点组成交点(节点);在节点连接的两个方向上添加弧线(或者仅对单向道路单向)添加弧线。

A *算法本身是在维基百科上有很好的文档。要优化的关键是从开放列表中选择最佳节点,为此您需要一个高性能优先级队列。如果您使用C ++,则可以使用STL priority_queue适配器。

定制该算法以在优选速度,距离或其他标准的网络的不同部分(例如,行人,汽车,公共交通工具等)上路由很容易。您可以通过编写过滤器来控制哪些路段可用,何时构建网络以及为每个路径分配哪个权重。

0
额外