原始地理坐标和图形节点之间的最短路径

Question

我用Java实现了一个简单的Dijkstra算法，用于在.osm地图上寻找最短路径。从.osm文件创建的图中的路径查找效果很好。但是，如果用户的当前位置和/或目标不是该图的节点（只是原始坐标），那么我们如何将这些坐标“连接”到图形中以使路径查找工作？简单直接的解决方案“找到最接近当前位置的节点并画一条直线”似乎不太现实。如果我们有像附图这样的情况呢？问题在于，在我们开始任何“聪明”的路径查找算法（如Dijkstra）之前，我们要将当前位置与图形链接起来，但这只是一种愚蠢的公式（勾股定理的斜边），用于找到地理坐标方面最近的节点，而这个公式并不是“路径查找”，它不能考虑障碍物和节点类型。换句话说，如果B是图中的节点，而A不是节点，我们如何找到A和B之间的最短路径？你听说过其他解决这个问题的方法吗？

- Kirill

Answer 1

你描述的过程是 "地图匹配(map matching)", 它使用 空间索引(spatial index) 来找到最近的节点。

常见方法之一是构建一个包含所有节点的 四叉树(quadtree)，然后确定包含你点的四叉树，接着计算从你的点到该四叉树内所有节点的距离(需要注意的是经度比纬度短)。如果四叉树中没有节点，则逐步扩大搜索范围。四叉树有几个注意事项，但这至少可以让你开始了。

- Anon

---

抱歉回复晚了，但我不得不阅读你提供的所有链接。问题是：这个“四叉树方法”与普通的“在一定半径内查找最近节点”的方法有何不同？据我所知，如果我们在四叉树中找不到任何节点，我们应该尝试下一个四叉树（顺便问一下，我们如何从其他三个四叉树中选择？标准是什么？）。但这与在一定半径内搜索最近节点并增加半径直到找到最近节点非常相似。 - Kirill

@Kirill - 你如何“查找最近的节点”？除非你打算遍历所有节点，否则你需要一些方法来组织它们。四叉树是一种组织彼此相近的节点的方式。 - Anon

找到最近节点：我们可以设置一个最小的期望“边界框”，并创建一个包含所有位于该框内的节点列表（即它们的坐标在某个“边界框”内）。然后我们遍历该列表，并计算我们当前位置与所取节点之间的距离（勾股定理）。然后我们选择距离最小的节点。问题在于，我们可以将“边界框”扩大，直到它捕捉到图片中“最接近当前位置的节点”，但不是“围栏”节点。我认为四叉树存在相同的问题。 - Kirill

@Kirill - 我会再问一遍：你如何“创建一个包含此框中所有节点的列表”？要么你迭代所有节点来做到这一点，要么你找到一种索引节点的方法。如果你只有几十个或几千个节点，那么迭代可能还好。在现实世界中，你有数百万个节点，这不是一个合适的解决方案。 - Anon

Answer 2

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

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

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

如果仍然不确定，我建议使用“最短的直线，不穿过障碍物”。如果这还不够，定义一个5mx5m及其对角线的虚拟网格。然后延伸最短路径算法，直到达到图形顶点。

- EPSG31468

---

“那不是问题，我非常确定谷歌/ORS不会使用这种简单的算法！想象一下你在街上，但这条街的起始节点很远，而另一条街的起始节点却靠近你的位置。这经常发生在高速公路穿过较小的街道时。然后你的路由算法将使用错误的起始位置。” - Karussell

对的，Google 不会捕捉街道的第一个/最后一个顶点，而是会捕捉最接近街道的点。但它仍然只是抓住“在道路网络上”的最近点。试一下：即使是汽车导航，它甚至可以穿过像铁路轨道这样的障碍物：https://maps.google.com/maps?saddr=42.761634,-89.244869&daddr=42.741024,-89.188914&hl=en&sll=42.755269,-89.232459&sspn=0.024421,0.038581&geocode=FaJ9jAIdOzuu-g%3BFSAtjAIdzhWv-g&dirflg=w&mra=ls&t=m&z=14 - EPSG31468

但这正是问题所在：如何获取最接近的点，即使它在道路上。 - Karussell

我认为Kirill主要关心避障问题。 - EPSG31468

Answer 3

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

但是，我没有看到你附加的图片，所以不确定这是否对你有帮助。

- Fortega

---

问题是找到最近的节点 - Anon

Answer 4

如果您的路径受到限制，您应该考虑使用同样的最短路径问题的线性规划公式。

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

你的目标是最小化在你的.osm文件中定义的起始和结束“节点”之间采取的每个“路径”的距离总和。任何障碍都将被制定为限制条件。要使用Java实现，请参见下面的链接。

http://javailp.sourceforge.net/

- dpott197

Answer 5

非常好的问题！

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

但是，这种“天真”的方法的问题在于这些解决方案会占用大量内存。例如，如果您已经有一个非常大的图形用于最短路径计算，则需要相同或更多的内存用于四叉树（或者我做了一些非常愚蠢的事情）。

一种解决方案如下：

• 使用一个数组，它是所使用区域上的网格。我的意思是，您可以将您的区域分成瓦片，并且每个瓦片都有一个带有节点列表的数组条目。
• 因此，对于每个数组条目，您将拥有该瓦片中节点的列表。对于边缘，您只需将两个节点添加到该条目中。当存在没有其节点的瓷砖穿过该瓷砖时，请注意BresenhamLine算法。
• 查询：将输入ala（lat，lon）转换为瓦片编号。现在从数组条目获取所有点。使用欧几里得几何计算节点和边缘到您的点A的最近邻居（只要它们不太远，这是最近邻居的情况）。

这个描述清楚吗？

更新 这已经在graphhopper中实现了！

为了获得更高效的内存解决方案，您只需排除一个条目（瓷砖）中的相同节点。

减少内存使用的一种更复杂的技术：如果图形遍历尊重瓷砖边界，则可以想象该图形被分成几个子图形以适应该瓷砖（即，图形遍历不会到达瓷砖边界之外的其他子图形）。现在，您不需要所有节点，而只需要位于不同子图形中的节点！这将减少内存使用，但在查询时，您需要遍历不止一个边缘（就像当前的graphhopper实现一样）！因为您需要遍历整个瓷砖-即使瓷砖边界没有超出。

- Karussell