我已经实现了一个简单的 Dijkstra 算法,用于使用 Java 查找 .osm 地图上的最短路径。
从 .osm 文件创建的图形中的寻路效果非常好。但是,如果用户的当前位置和/或目的地不是该图的节点(只是原始坐标),我们如何将这些坐标“链接”到图以使寻路工作?
The simple straightforward solution "find the nearest to the current location node and draw a straight line" doesn't seem to be realistic. What if we have a situation like on the attached picture? (UPD)
这里的问题是,在我们开始任何“智能”寻路算法(如 Dijkstra 的)之前,我们将当前位置“链接”到图形,但这只是一个愚蠢的公式(毕达哥拉斯定理的斜边),用于根据以下方式查找最近的节点:地理坐标,这个公式不是“寻路”——它不能考虑障碍物和节点类型。
换句话来说,如果 B 是图中的节点,而 A 不是节点,我们如何找到 A 和 B 之间的最短路径?
您听说过这个问题的其他解决方案吗?
您描述的过程是“地图匹配 http://www.google.com/search?q=map%20matching,”并且它使用了空间索引 http://en.wikipedia.org/wiki/Spatial_index找到最近的节点。
一种常见的方法是构建一个quadtree http://en.wikipedia.org/wiki/Quadtree包含所有节点,然后识别包含您的点的四边形,然后计算从您的点到四边形中所有节点的距离(认识到经度比纬度短)。如果四边形中没有节点,那么您将逐步扩大搜索范围。四叉树有几个注意事项,但这至少应该让您开始。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)