我想知道Google地图用哪种算法计算两点之间的方向？Google是否曾经提到过它？顺便说一下：我正在询问Google用于查找两点之间最短路线的算法。
谷歌地图使用哪种算法来计算两点之间的方向？
9
- IT-Fan
2
5以下是需要翻译的内容：https://dev59.com/gHRC5IYBdhLWcg3wCMnX有哪些算法可以计算出地图上从点A到点B的方向？ - Sherif elKhatib
https://dev59.com/xVkS5IYBdhLWcg3w8ai-#39256428 - Alex Filatov
6个回答
18
据我所知，谷歌从未公开表示其在P2P查询中使用哪种算法。虽然目前文献中关于查询时间的最新技术是由Abraham等人提出的Hub标签算法http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20。最近，微软技术报告中发表了一篇详细而优秀的领域调查http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf。
简而言之...
Hub标签算法为静态道路网络提供了最快的查询速度，但需要大量内存运行（18 GiB）。
过渡节点路由略慢，但只需要约2 GiB的内存，并具有更快的预处理时间。
收缩分层提供了快速预处理时间、低空间要求（0.4 GiB）和快速查询时间之间的良好平衡。
没有一种算法完全占优势...
这个由Peter Sanders主讲的Google技术讲座可能会引起您的兴趣。https://www.youtube.com/watch?v=-0ErpE8tQbw
还有这个由安德鲁·戈德伯格发表的演讲
https://www.youtube.com/watch?v=WPrkc78XLhw
可以从KIT的Peter Sanders研究小组网站上获取收缩分层的开源实现。http://algo2.iti.kit.edu/english/routeplanning.php
- Barnaby Hussey-Yeo
3
如果你指的是谷歌地图方向API和两点之间的最短路径，那么它是一个图论问题，可以使用Dijkstra算法解决。这是一个带有回溯的DFS。
- Micromega
3
1你好，这真的是 Google 地图正在使用的算法吗？Google 是否在任何文章中提到过这个算法？ - IT-Fan
简短的回答是肯定的。也许这是A+寻路算法。但是回溯意味着尝试所有解决方案，直到找到最佳解决方案或者解决方案不符合要求（即比当前最短解决方案更长）。 - Micromega
以下是来自谷歌员工的帖子链接：https://dev59.com/gHRC5IYBdhLWcg3wCMnX - Micromega
1
像这样的疑问，您应该始终检查Android源代码。
private static void computeDistanceAndBearing(double lat1, double lon1,
double lat2, double lon2, float[] results) {
int MAXITERS = 20;
// Convert lat/long to radians
lat1 *= Math.PI / 180.0;
lat2 *= Math.PI / 180.0;
lon1 *= Math.PI / 180.0;
lon2 *= Math.PI / 180.0;
double a = 6378137.0; // WGS84 major axis
double b = 6356752.3142; // WGS84 semi-major axis
double f = (a - b) / a;
double aSqMinusBSqOverBSq = (a * a - b * b) / (b * b);
double L = lon2 - lon1;
double A = 0.0;
double U1 = Math.atan((1.0 - f) * Math.tan(lat1));
double U2 = Math.atan((1.0 - f) * Math.tan(lat2));
double cosU1 = Math.cos(U1);
double cosU2 = Math.cos(U2);
double sinU1 = Math.sin(U1);
double sinU2 = Math.sin(U2);
double cosU1cosU2 = cosU1 * cosU2;
double sinU1sinU2 = sinU1 * sinU2;
double sigma = 0.0;
double deltaSigma = 0.0;
double cosSqAlpha = 0.0;
double cos2SM = 0.0;
double cosSigma = 0.0;
double sinSigma = 0.0;
double cosLambda = 0.0;
double sinLambda = 0.0;
double lambda = L; // initial guess
for (int iter = 0; iter < MAXITERS; iter++) {
double lambdaOrig = lambda;
cosLambda = Math.cos(lambda);
sinLambda = Math.sin(lambda);
double t1 = cosU2 * sinLambda;
double t2 = cosU1 * sinU2 - sinU1 * cosU2 * cosLambda;
double sinSqSigma = t1 * t1 + t2 * t2; // (14)
sinSigma = Math.sqrt(sinSqSigma);
cosSigma = sinU1sinU2 + cosU1cosU2 * cosLambda; // (15)
sigma = Math.atan2(sinSigma, cosSigma); // (16)
double sinAlpha = (sinSigma == 0) ? 0.0 :
cosU1cosU2 * sinLambda / sinSigma; // (17)
cosSqAlpha = 1.0 - sinAlpha * sinAlpha;
cos2SM = (cosSqAlpha == 0) ? 0.0 :
cosSigma - 2.0 * sinU1sinU2 / cosSqAlpha; // (18)
double uSquared = cosSqAlpha * aSqMinusBSqOverBSq; // defn
A = 1 + (uSquared / 16384.0) * // (3)
(4096.0 + uSquared *
(-768 + uSquared * (320.0 - 175.0 * uSquared)));
double B = (uSquared / 1024.0) * // (4)
(256.0 + uSquared *
(-128.0 + uSquared * (74.0 - 47.0 * uSquared)));
double C = (f / 16.0) *
cosSqAlpha *
(4.0 + f * (4.0 - 3.0 * cosSqAlpha)); // (10)
double cos2SMSq = cos2SM * cos2SM;
deltaSigma = B * sinSigma * // (6)
(cos2SM + (B / 4.0) *
(cosSigma * (-1.0 + 2.0 * cos2SMSq) -
(B / 6.0) * cos2SM *
(-3.0 + 4.0 * sinSigma * sinSigma) *
(-3.0 + 4.0 * cos2SMSq)));
lambda = L +
(1.0 - C) * f * sinAlpha *
(sigma + C * sinSigma *
(cos2SM + C * cosSigma *
(-1.0 + 2.0 * cos2SM * cos2SM))); // (11)
double delta = (lambda - lambdaOrig) / lambda;
if (Math.abs(delta) < 1.0e-12) {
break;
}
}
float distance = (float) (b * A * (sigma - deltaSigma));
results[0] = distance;
if (results.length > 1) {
float initialBearing = (float) Math.atan2(cosU2 * sinLambda,
cosU1 * sinU2 - sinU1 * cosU2 * cosLambda);
initialBearing *= 180.0 / Math.PI;
results[1] = initialBearing;
if (results.length > 2) {
float finalBearing = (float) Math.atan2(cosU1 * sinLambda,
-sinU1 * cosU2 + cosU1 * sinU2 * cosLambda);
finalBearing *= 180.0 / Math.PI;
results[2] = finalBearing;
}
}
}
- Reno
1
1嗨，谢谢，但似乎不是我要问的。 我正在询问Google用来查找两个点之间最短路线的算法。 - IT-Fan
1
谷歌地图使用Dijkstra最短路径算法。它计算元素或所谓节点对之间的连接。节点之间的连接称为边缘。每个边缘都有一个权重。边缘的权重可以表示距离、时间或任何模拟它连接的节点对之间的“连接”的内容。这些权重对于Dijkstra算法至关重要。通过这种方式，您可以找到节点之间的最短路径。特别是，您可以从一个节点（称为“源节点”）找到到所有其他节点的最短路径，从而生成一棵最短路径树。
- Boris
2
你有引用谷歌使用Dijkstra算法的来源吗？根据最受赞同的答案，似乎谷歌并没有公开说明他们用于点对点计算的算法，但那是6年前的事了。 - Hoppeduppeanut
我在网上冲浪时发现了这些信息，主要是在 Quora 上。没有任何来源是 Google 官方网站。正如之前提到的那样，Google 从未公开确认它确实是 Dijkstra 算法。 - Boris
1
谷歌地图使用了一些非常复杂的算法。它可能是任何启发式算法，比如A*算法；但肯定不是Dijkstra算法。我的发现：
1] 很多时候它显示的是交通较少的路线，这会随时间而变化，但是Dijkstra算法在所有情况下都只会给出一条路径。
2] 我和我的朋友们去参观某个地方，我们同时开始使用谷歌地图。如果谷歌地图提供的是最优最短路径，那么我们的地图必须提供相同的路径；但事实并非如此。这意味着他们没有使用任何确切的算法。
Udacity数据结构和算法纳米学位声称谷歌正在使用类似于A*算法的算法，但需要引用。你也可以访问quora discussion。
1] 很多时候它显示的是交通较少的路线，这会随时间而变化，但是Dijkstra算法在所有情况下都只会给出一条路径。
2] 我和我的朋友们去参观某个地方，我们同时开始使用谷歌地图。如果谷歌地图提供的是最优最短路径，那么我们的地图必须提供相同的路径；但事实并非如此。这意味着他们没有使用任何确切的算法。
Udacity数据结构和算法纳米学位声称谷歌正在使用类似于A*算法的算法，但需要引用。你也可以访问quora discussion。
- Aaditya Bhardwaj
0
谷歌地图 API 中的几何库提供了算法，你可以在源代码中找到它。
我不确定谷歌地图是否使用相同的算法。
这个算法很简单：
function toRadians(deg){
return deg * (Math.PI / 180);
}
function getDistance(from, to) {
var c = toRadians(from.lat()),
d = toRadians(to.lat());
return 2 * Math.asin(Math.sqrt(Math.pow(Math.sin((c - d) / 2), 2) + Math.cos(c) * Math.cos(d) * Math.pow(Math.sin((toRadians(from.lng()) - toRadians(to.lng())) / 2), 2))) * 6378137;
}
这两行代码将会得到相同的结果:
console.log(google.maps.geometry.spherical.computeDistanceBetween(new google.maps.LatLng(39.915, 116.404), new google.maps.LatLng(38.8871, 113.3113)));
console.log(getDistance(new google.maps.LatLng(39.915, 116.404), new google.maps.LatLng(38.8871, 113.3113)));
- jz1108
1
嗨，谢谢，但似乎不是我要问的。我正在询问谷歌用来找到两点之间最短路线的算法。 - IT-Fan
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接