原始地理坐标与图形节点之间的最短路径
我已经实现了一个简单的Dijkstra算法，用于在Java上查找.osm地图上的最短路径。
从.osm文件创建的图形中的路径查找效果非常好。 但是，如果用户的当前位置和/或目的地不是此图的节点（只是原始坐标），我们如何将这些坐标“链接”到图形以进行寻路工作？
简单直接的解决方案“找到最接近当前位置节点并绘制直线”似乎不太现实。 如果我们遇到附图所示的情况怎么办？ （UPD） 
这里的问题是，在我们开始任何“智能”寻路算法（如Dijkstra’s）之前，我们将当前位置与图形“链接”，但它只是根据毕达哥拉斯定理的一个愚蠢的公式（从斜方解释定义的斜边）找到最近的节点。地理坐标和这个公式不是“路径” – 它不能考虑障碍和节点类型。
换句话说 – 如果B是图中的节点，我们如何找到A和B之间的最短路径，而A不是节点？
你有没有听说过这个问题的其他解决方案？
您描述的过程是“ 地图匹配 ”，它使用空间索引来查找最近的节点。
一种常见的方法是构造包含所有节点的四叉树 ，然后识别包含点的四边形，然后计算从点到四边形中所有节点的距离（识别纵向度比纬度度更短）。 如果四元组中没有节点，则逐步扩展搜索范围。 有四个有四个树的警告，但这至少应该让你开始。
您可以将当前位置视为节点，并将该节点以直线连接到几个最近的节点。 GPS应用将这条直线视为“越野”，因此与节点之间的其他线路相比，该线路的成本非常高。
但是，我没有看到你的附图，所以不确定这是一个很好的解决方案。
实际上，我只是忽略了这个问题，并使用你建议的算法“直线到最近的节点”。 用户有责任尽可能接近可路由的实体。 如果你建议的第一个猜测是误导，用户可以相应地改变起始位置。
真正在无人区开始旅程的用户希望比你的算法更了解覆盖区域。 相信他。
顺便说一句，这是OpenRouteService和Google Maps正在使用的算法。
如果仍然不相信，我建议使用“不跨越障碍的最短直线”。 如果仍然不够，请定义一个5mx5m的虚拟网格及其对角线。 比跨越最短路径算法直到达到图顶点。
如果路径中存在约束，则应考虑使用具有相同最短路径问题的线性编程公式。
http://en.wikipedia.org/wiki/Shortest_path_problem
您的目标是最小化.osm文件中定义的起始和结束“节点”之间的每个“路径”的距离总和。 任何障碍都将被制定为限制因素。 要使用Java实现，请参阅下面的链接。
真好问题！
四叉树是一种解决方案，因为您还可以将线/边索引到其中，而不仅仅是节点。
但这种“天真”方法的问题在于这些解决方案是内存密集型的。 例如，如果你已经有一个非常大的图表用于最短路径计算，那么你需要相同或更多的内存用于四叉树（或者我做了一些非常愚蠢的事情）。
一种解决方案如下：
- 使用一个数组，它是使用区域上的网格。 我的意思是你可以将你的区域分成瓷砖，而每个瓷砖你有一个带有节点列表的数组条目。
- 因此，对于每个数组条目，您将拥有该磁贴中的节点列表。 对于边缘，您只需将两个节点添加到条目即可。 有边缘穿过瓷砖而在此瓷砖中没有节点时要小心。 BresenhamLine算法将在这里提供帮助。
- 查询：将输入ala（lat，lon）转换为tile数。 现在从数组条目中获取所有点。 使用欧几里得几何计算你的点A的节点和边缘的最近邻点 （只要它们不是太远就应该是最好的，这是最近邻居的情况）。
这个描述清楚了吗？
更新现在在graphhopper中实现 ！
要获得更高内存效率的解决方案，您必须简单地为一个条目（磁贴）排除相同的节点。
减少内存使用量的一个更复杂的技术：如果图形遍历尊重图块边界，您可以想象图形被分成几个子图形（即图形遍历不会到达其他子图形）图块内的图形）。 现在您不需要所有节点，只需要位于不同子图中的节点！ 这将减少内存使用量，但在查询时，您不仅需要进一步遍历一个边缘（就像当前的graphhopper实现一样）！ 因为您需要遍历整个图块 – 即只要不超过图块边界。