原始地理坐标与图形节点之间的最短路径 [英] Shortest path between raw geo coordinates and a node of a graph
问题描述
我已经实现了一个简单的Dijkstra算法，用于在Java上查找.osm地图上的最短路径。
从.osm文件创建的图中的路径查找效果非常好。但是，如果用户的当前位置和/或目的地不是该图的节点（只是原始坐标），我们如何将这些坐标链接到图形以进行寻路工作？
简单直接的解决方案找到最接近当前位置节点并绘制直线似乎不太现实。如果我们遇到附图所示的情况怎么办？ （UPD）
<这里的问题是，在我们开始任何智能寻路算法（如Dijkstra's）之前，我们将当前位置与图形链接，但它只是在寻找最近节点时的愚蠢公式（来自毕达哥拉斯定理的斜边）。地理坐标和这个公式的术语不是'追踪' - 它不能考虑障碍和节点类型。
用它来解释一下 - 如果B是图中的节点而A是不是节点，我们如何找到A和B之间的最短路径？
您是否听说过此问题的其他解决方案？
过程你我正在描述的是地图匹配，并使用空间索引以查找最近的节点。
一个常见的方法是构建包含所有节点的四叉树，然后识别包含您的点的四边形，然后计算从你的点到四边形中所有节点的距离（识别纵向度比纬度度短）。如果四元组中没有节点，则逐步扩展搜索范围。有四个有四个树的警告，但这至少应该让你开始。
I have implemented a simple Dijkstra's algorithm for finding the shortest path on an .osm map with Java.
The pathfinding in a graph which is created from an .osm file works pretty well. But in case the user's current location and/or destination is not a node of this graph (just raw coordinates) how do we 'link' those coordinates to the graph to make pathfinding work?
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)
The problem here is that before we start any 'smart' pathfinding algorithms (like Dijkstra's) we 'link' the current position to the graph, but it is just dumb formula (a hypotenuse from Pythagorean theorem) of finding the nearest node in terms of geographical coordinates and this formula is not 'pathinding' - it can not take obstacles and types of nodes into account.
To paraphrase it - how do we find the shortest path between A and B if B is a node in a graph, and A is not a node?
Have you heard of any other solutions to this problem?
The process you're describing is "map matching," and it uses a spatial index to find the nearest node.
One common approach is to construct a quadtree that contains all your nodes, then identify the quad that contains your point, then calculate the distance from your point to all nodes in the quad (recognizing that longitudinal degrees are shorter than latitudinal degrees). If there are no nodes in the quad then you progressively expand your search. There are several caveats with quadtrees, but this should at least get you started.
这篇关于原始地理坐标与图形节点之间的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
