Shortest path between raw geo coordinates and a node of a graph

Question

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?

Answer 1

Practically speaking, I would just ignore the problem and use your suggested algorithm "straight line to nearest node". It is the user's responsibility to be as close as possible to a routable entity. If the first guess you suggested was missleading, user can change the starting position accordingly.

The user who really starts his journey in no man's land hopefully knows the covered area much more than your algorithm. Trust him.

BTW, this is the algorithm that OpenRouteService and Google Maps are using.

If still not convinced, I suggest to use the "shortest straight line that does not cross an obstacle". If this is still not enough, define a virtual grid of say 5mx5m and its diagonals. Than span a shortest path algorithm until you reach a graph-vertex.

Answer 2

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.