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

您正在描述的过程是“地图匹配”，它使用空间索引来找到最近的节点。 一种常见的方法是构造一个包含所有节点的四叉树，然后标识包含您的点的四叉树，然后计算从您的点到该四边形中所有节点的距离（确认纵向度比纬度度短）。如果四边形中没有节点，那么您将逐步扩展搜索范围。有一些关于四叉树的警告，但这至少应该让您入门。     

您可以将当前位置视为一个节点，然后将该节点沿直线连接到一些最近的节点。 GPS应用程序会将这条直线视为“越野”，因此与节点之间的其他线路相比，这条直线的成本非常高。 但是，我没有看到您附带的图片，因此不确定这对您来说是一个好的解决方案。     

实际上，我将忽略该问题，而使用建议的算法“到最近节点的直线”。用户有责任尽可能靠近可路由的实体。如果您建议的第一个猜测有误导性，则用户可以相应地更改开始位置。 真正在无人区中开始旅程的用户希望比您的算法更了解覆盖区域。相信他。 顺便说一句，这是OpenRouteService和Google Maps使用的算法。 如果仍然不能说服，我建议使用“不越过障碍的最短直线”。如果还不够，请定义一个虚拟网格，例如5mx5m及其对角线。比跨过最短路径算法，直到达到图顶点。     

如果路径上有约束，则应考虑使用相同最短路径问题的线性编程公式。 http://en.wikipedia.org/wiki/Shortest_path_problem 您的目标是最小化.osm文件中定义的开始和结束“节点”之间的每个“方向”的距离之和。任何障碍都将被表述为约束。要使用Java实施，请参见下面的链接。 http://javailp.sourceforge.net/     

真是个好问题！ 四叉树是一种解决方案，因为您还可以将线/边索引到其中，而不仅仅是节点。 但是，这种“幼稚”方法的问题在于这些解决方案需要占用大量内存。例如。如果您已经有一个很大的图形用于最短路径计算，那么您需要为四叉树使用相同或更多的内存（或者我做的非常愚蠢的操作）。 一种解决方案如下： 使用数组，该数组是使用区域上方的网格。我的意思是您可以将区域划分为图块，每个图块都有一个包含节点列表的数组条目。 因此，对于每个数组条目，您将在该图块中有一个节点列表。对于边缘，您可以将两个节点都添加到条目中。当有边缘穿过瓷砖时，请注意不要将其节点放在此瓷砖中。 BresenhamLine算法将在此提供帮助。 查询：将输入的ala（纬度，经度）转换为图块编号。现在从数组条目中获取所有点。使用欧几里得几何来计算节点和边缘到点A的最近邻居（只要它们之间的距离不算太远（最近邻居就是这种情况），就可以了）。 这个描述清楚吗？ 更新资料 现在已在graphhopper中实现了！ 为了获得一种内存效率更高的解决方案，您必须简单地为一个条目（平铺）排除相同的节点。 减少内存使用的技术更为复杂：如果图遍历遵守图块边界，您可以想象该图然后被划分为该图块的几个子图（即，图遍历不会到达另一个子图） -图在图块范围内）。现在，您不需要所有节点，只需要位于不同子图中的节点即可！这将减少内存使用量，但是在查询时，您不仅需要遍历一个边（就像在当前的graphhopper实现中一样）！因为您需要遍历整个图块-也就是说，只要不超出图块范围即可。