地图路线,谷歌地图?

Translate

我一直对Map Routing感兴趣,但是我从来没有找到关于它的任何入门级(甚至高级!)级教程。有人有任何指针,提示等吗?

更新:我主要是在寻找有关如何实现地图系统的指针(数据结构,算法等)。

This question and all comments follow the "Attribution Required."

所有的回答

Translate

看看开放式街道地图项目看看如何在仅使用用户提供和许可的数据的真正自由软件项目中解决此类问题,并拥有Wiki,其中包含您可能会发现有趣的内容.

几年前,这些家伙参与其中,他们很随和,回答了我很多问题,所以我看不出为什么他们仍然不是一个好人。

来源
Translate

Google地图路线查找功能的工程师之一巴里·布鲁米特(Barry Brumitt)就该主题撰写了一篇可能引起关注的帖子:

通往更好道路的道路2007/11/06下午03:47:00

来源
Translate

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

来源
Translate

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

Dijkstra最短路径算法是最著名的。维基百科的介绍很不错:http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

这里有一个Java小程序,您可以在其中查看它的运行情况:http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html而Google,则可以引导您使用几乎任何语言编写源代码。

生成行驶路线的任何实际实现都将在街道网络上包含大量数据,这些数据描述了与遍历链接和节点相关的成本-道路网络层次,平均速度,交叉路口优先级,交通信号灯链接,禁止转弯等。

来源
Translate

与其学习每个地图服务提供商的API(例如Gmaps,Ymaps api),不如学习它Mapstraction

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

我建议您转到URL并学习通用的API。也有大量的方法指南。

来源
Translate

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

有一些使用Openstreetmap数据的GPL路由应用程序,例如高斯莫尔适用于Windows(+移动版)和Linux。有很多有趣的[应用程序使用相同的数据,但是gosmore有一些很酷的用途例如与网站的界面.

路由的最大问题是坏数据,而您永远得不到足够的数据。因此,如果您想尝试将其保持在非常本地的测试中,则可以更好地控制数据。

来源
Translate

从概念的角度,想象一下将一块石头扔进池塘里,看着涟漪。路线将代表池塘,而石头则代表您的出发位置。

当然,随着距离n的增加,该算法将不得不搜索一定比例的n ^ 2路径。您将以起始位置为起点,并检查从该点开始的所有可用路径。然后递归地调用这些路径末端的点,依此类推。

您可以通过以下方式来提高性能:不对路径进行重复备份;不重新检查某个路径是否已被覆盖;以及放弃花费时间太长的路径。

另一种方法是使用蚂蚁信息素方法,在这种方法中,蚂蚁从起点随机爬行并留下气味,这会在给定路径上积聚更多的蚂蚁。如果您从起点和终点都发送(足够)的蚂蚁,那么最终气味最强的路径最终将是最短的。这是因为假设蚂蚁以统一的速度行走,那么在给定的时间段内,最短的路径将被多次访问。

编辑@ Spikie

为了进一步说明如何执行池塘算法-突出了所需的潜在数据结构:

您需要将地图存储为网络。这只是一组nodesedges它们之间。一套nodes构成一个route。一条边连接两个节点(可能是同一节点),并具有关联的costdistance要么time遍历边缘。边可以是双向的也可以是单向的。仅具有单向路径并在节点之间的双向旅行中加倍(即,一条边从A到B,另一条边从B到A)可能是最简单的。

举例来说,想象三个火车站以等边三角形的形式指向上方。它们之间的中途还有另外三个站。边将所有相邻测站连接在一起,最终图将在大三角形内包含一个倒三角形。

标记节点从左下开始,从左到右并向上,依次为A,B,C,D,E,F(顶部为F)。

假定可以沿任一方向遍历边缘。每个边缘的成本为1公里。

好的,所以我们希望从左下角A到顶部站点F。有许多可能的路线,包括那些自身折返的路线,例如ABCEBDEF。

我们有一个常规的说法,NextNode,即接受node和一个cost并针对其可以到达的每个节点进行调用。

显然,如果我们让此例程运行,它将最终发现所有路由,包括可能无限长的路由(例如ABABABAB等)。我们通过检查cost。每当我们访问以前从未访问过的节点时,我们会将成本和来自该节点的节点都放在该节点上。如果在访问节点之前检查了现有成本,并且如果我们更便宜,那么我们将更新该节点并继续(递归)。如果我们更昂贵,那么我们跳过该节点。如果所有节点都被跳过,则我们退出例程。

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

这样,可以检查所有可行的路线,但关键是仅检查成本最低的路线。到流程结束时,每个节点(包括我们的目标节点)将具有最低的成本到达该节点。

为了获得路线,我们从目标节点向后进行工作。由于我们存储了来自节点以及成本,因此我们仅向后跳即可构建路线。对于我们的示例,我们最终将得到以下结果:

节点A-(总计)成本0-从节点无
节点B-费用1-从节点A
节点C-费用2-从节点B
节点D-费用1-从节点A
节点E-成本2-从节点D /成本2-从节点B(这是例外,因为成本相等)
节点F-费用2-从节点D

因此,最短的路线是ADF。

来源
Translate

根据我在该领域的工作经验,A *做得很好。 (如上所述)它比Dijkstra的算法快,但是对于普通的有能力的程序员来说,实现和理解仍然足够简单。

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

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

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

来源
Translate

关于每个遍历的代价,我想到了另一个想法,但是会增加计算所需的时间和处理能力。

例:根据GoogleMaps,我可以通过3种方式(居住的地方)从A点到达B点。 Garmin装置可在Quickest路线计算。在遍历这些路线中的每条路线并进行平均后(显然会有误差,具体取决于一天中的时间,咖啡因的量等),我觉得算法可以考虑到道路弯道的数量,从而获得较高的准确性,例如 1英里的直路比弯弯的1英里路要快。这不是实际的建议,但我肯定会使用它来改善日常通勤的结果。

来源