Shortest path between raw geo coordinates and a no

问题:

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?

回答1:

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.

回答2:

You could treat the current location as a node, and connect that node to a few of the nearest nodes in a straight line. GPS applications would consider this straight line as being 'off road', so the cost of this line is very big compared to the other lines between nodes.

However, I didn't see your attached picture, so not sure this is a good solution for you.

回答3:

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.

回答4:

If you have constraints in your path, you should consider using a linear programming formulation of the same shortest path problem.

http://en.wikipedia.org/wiki/Shortest_path_problem

Your objective would be to minimize the sum of the distance of each "way" taken between the starting and ending "nodes" defined in your .osm file. Any obstacles would be formulated as constraints. To implement with Java, see the link below.

http://javailp.sourceforge.net/

回答5:

Really nice question!

Quad tree is a solution, as you can also index lines/edges into it, not only nodes.

But the problems with this 'naive' approach is that these solutions are memory intensive. E.g. if you already have a very big graph for shortest path calculation then you need the same or more memory for the quad tree (or I was doing something very stupid).

One solution is as follows:

• use an array which is a grid over the used area. I mean you can devide your area into tiles, and per tile you have an array entry with the list of nodes.
• so per array entry you'll have a list of nodes in that tile. For an edge you can just add both nodes to the entry. Take care when there are edges crossing a tile without having its node in this tile. The BresenhamLine algorithm will help here.
• querying: converte the input ala (lat,lon) into a tile number. now get all points from the array entry. Calculate the nearest neighbor of the nodes AND edges to your point A using euclidean geometry (which should be fine as long as they are not too far away which is the case for nearest neighbor).

Is this description clear?

Update This is now implemented in graphhopper!

To get a more memory efficient solution you have to simply exclude identical nodes for one entry (tile).

A bit more complicated technic to reduce mem-usage: if a graph traversal respects the tile bounds you can imagine that the graph is then devided into several sub-graphs for that tile (ie. a graph traversal wouldn't reach the other sub-graph within the tile-bounds). Now you don't need all nodes but only the nodes which lay in a different sub-graph! This will reduce the memory usage, but while querying you need to traverse not only one edge further (like in the current graphhopper implementation)! Because you need to traverse the full tile - i.e. as so long as the tile bounds are not exceeded.