7

我已经实现了一个简单的 Dijkstra 算法，用于使用 Java 在 .osm 地图上查找最短路径。

从 .osm 文件创建的图中的路径查找工作得很好。但是如果用户的当前位置和/或目的地不是该图的节点（只是原始坐标），我们如何将这些坐标“链接”到图以进行寻路工作？

简单直接的解决方案“找到离当前位置节点最近的并画一条直线”似乎并不现实。如果我们遇到附图中的情况怎么办？(UPD) 在此处输入图像描述

这里的问题是，在我们开始任何“智能”寻路算法（如 Dijkstra 的）之前，我们将当前位置“链接”到图形，但这只是根据以下公式找到最近节点的愚蠢公式（勾股定理的斜边）地理坐标，这个公式不是“寻路”——它不能考虑障碍物和节点类型。

套用它 - 如果 B 是图中的节点，而 A 不是节点，我们如何找到 A 和 B 之间的最短路径？

你听说过这个问题的任何其他解决方案吗？

4

5 回答 5

3

您描述的过程是“地图匹配”，它使用空间索引来查找最近的节点。

一种常见的方法是构建一个包含所有节点的四叉树，然后识别包含您的点的四边形，然后计算从您的点到四边形中所有节点的距离（认识到纵向度数小于纬度度数）。如果四边形中没有节点，那么您将逐步扩大搜索范围。四叉树有几个注意事项，但这至少可以帮助您入门。

于 2011-04-12T12:08:40.950 回答
1

实际上，我会忽略这个问题并使用您建议的算法“直线到最近的节点”。尽可能接近可路由实体是用户的责任。如果您建议的第一个猜测具有误导性，用户可以相应地更改起始位置。

真正在无人区开始旅程的用户希望比您的算法更了解覆盖区域。相信他。

顺便说一句，这是OpenRouteService和Google Maps正在使用的算法。

如果还是不服气，我建议使用“不越障的最短直线”。如果这还不够，请定义一个 5mx5m 的虚拟网格及其对角线。比跨越最短路径算法直到到达图顶点。

于 2012-08-09T12:01:36.040 回答
0

真是个好问题！

四叉树是一种解决方案，因为您还可以将线/边索引到其中，而不仅仅是节点。

但是这种“幼稚”方法的问题在于这些解决方案是内存密集型的。例如，如果您已经有一个非常大的最短路径计算图，那么您需要为四叉树提供相同或更多的内存（或者我正在做一些非常愚蠢的事情）。

一种解决方案如下：

  • 使用一个数组，它是已使用区域上的网格。我的意思是您可以将您的区域划分为图块，并且每个图块都有一个包含节点列表的数组条目。
  • 因此，对于每个数组条目，您将在该图块中拥有一个节点列表。对于边缘，您只需将两个节点都添加到条目中。当有边缘穿过瓦片而其节点不在此瓦片中时要小心。BresenhamLine 算法将在这里提供帮助。
  • 查询：将输入 ala (lat,lon) 转换为瓦片编号。现在从数组条目中获取所有点。使用欧几里德几何计算节点和边的最近邻居到您的点 A（只要它们不是太远就可以了，这是最近邻居的情况）。

这个描述清楚吗？

更新 现在在graphhopper中实现了！

要获得内存效率更高的解决方案，您必须简单地排除一个条目（图块）的相同节点。

减少内存使用的更复杂的技术：如果图遍历尊重图块边界，您可以想象该图随后被划分为该图块的多个子图（即图遍历不会到达另一个子图）平铺边界内的图形）。现在您不需要所有节点，而只需要位于不同子图中的节点！这将减少内存使用量，但是在查询时，您不仅需要进一步遍历一条边（就像在当前的 graphhopper 实现中一样）！因为您需要遍历整个图块 - 即只要不超过图块边界。

于 2012-08-09T10:52:47.477 回答
0

如果您的路径有约束，您应该考虑使用相同最短路径问题的线性规划公式。

http://en.wikipedia.org/wiki/Shortest_path_problem

您的目标是最小化 .osm 文件中定义的开始和结束“节点”之间的每个“方式”的距离总和。任何障碍都将被表述为约束。要使用 Java 实现，请参阅下面的链接。

http://javailp.sourceforge.net/

于 2012-09-15T11:21:24.920 回答
0

您可以将当前位置视为一个节点，并将该节点连接到直线上的几个最近的节点。GPS 应用程序会将这条直线视为“越野”，因此与节点之间的其他线路相比，这条线路的成本非常高。

但是，我没有看到您所附的图片，所以不确定这是否适合您。

于 2011-04-12T10:09:41.247 回答