Allow routing from arbitrary start and end coordinates

[karussell]

At the moment the routing start and end point can be only on a node. We need to extend the algorithm and the querying to allow arbitrary GPS coordinates on an edge (the road) too.

• depends on GPS Lookup #17
• extend the algorithm to allow two multiple start nodes (start(node), end(someCondition) and default is end(PointCondition(endNode))?)
• calculate the shortest path from the GPS coordinate to one of the start nodes
• do the same for the end point

[ocampana]

Can you please explain this? I mean, following the example code in mi app I call

calcPath (fromLatitude, fromLongitude, toLatitude, toLongitude, mapName);

where {from,to}{Latitude,Longitude} are double variables, whose values are not bound to anything. Why does it work?

[karussell]

Not sure if I understand you ... there is a search functionality going on in Location2IDIndex which returns a node id from a point (lat,lon). But the node id could be relative far away from the original requested point. As we only need crossroads for routing, all other information of the actual path (e.g. for displaying) is stored in wayGeometry.

In this ticket we'll have to extend the current algorithm interface to make it possible somehow to return the full path from start to end (both some valid positions on a road or path) not only from cross-road to cross-road.

We could try to somehow introduce a virtual node to the graph. To make that thread safe we would need to separate node access from the Graph interface, e.g. instead of graph.getLatitude(int index) we would need something like new NodeAccess(graph).getLatitude(int index) and then return custom latitude values for our virtual node....hmmh. This change will trigger changes in RoutingAlgorithm and Path.

[karussell]

BTW: this limitation will result in wrong routes if one starts or ends on one-way roads. See http://lists.openstreetmap.org/pipermail/graphhopper/2013-May/000136.html?

[ngmip]

I have developed a improvement for this.
Feel free to check my fork https://github.com/ngmip/graphhopper
I did two things :

• First : decorate the LocationIdResult with the closest edge informations so that I have start and end edges (works only with Location2NodesNTree index).
  This allow me to take edge direction into account when electing the start/end node to respect one way.
  Note that tough it improves the current algorithm it not 100% optimal for bidirectional edges as the bes starting node is not alway the closest node to the GPS location. (see the DummyNodeResolver class)
• Second, compare the resulting path with the edges and adapt geometry, time and distance.
  This is done through my PathFinisher class. It computes a "cut point" being the location where the GPS point is projected on the edge and then add or remove the necessary points of the path to make neat endings.

I think I documented my code quite well and it has been synced with the master branch last Friday.

Suggestion for a perfect optimal solution :
A better way to do this would be to add 2 nodes and 4 edges in the graph at the "cut points" but this involves multi-thread issues as is. A good option would be to create a "virtual graph" ; a kind of wrapper around the actual graph and implementing the Graph interface. This wrapper would mirror method call to the underling actual graph. You could create one virtual graph for each request and add it the virtual node and edges. Those would be in the virtual graph (thread safe) but not in the actual graph. Then in the mirrored methods you could check if it involves virtual nodes/edges and adapt the method behavior to either return virtual objects or call the base graph's method.
I made an attempt to implement this solution but without success, that's the VirtualNodeVelvelGraph class in my repository.

[karussell]

Thanks! I'll have a look into it this week!

[ngmip]

Just a shared thought :

As said before, start/end node are more or less arbitrary chosen.
When the edge can be matched it's still difficult to chose which tower node to use. (unless the edge is one way)
The best tower node would be the node for the shortest/fastest path.

Instead of computing the 4 possible path (or event partly computing them) and take the best I wonder if that would not be possible to "simply" initializes the 4 edges' nodes weight with a weight computed from the GPS point.

Let's take an example for the "from" node:
An edge AB with the P point on it (P being the projection of start GPS coordinate).

A --------------- P --- B

The index returns us the B node as the closest node and routing algorithm will use that node as start giving B the weight 0.
While computing route, the A node will soon have the 'BA' weight as best min weight.
If instead we define the B weight = PB (PB > 0) and the A weight = PA (PA < BA) then the routing algorithm should pass through A point in case it's actually shorter that passing through B.

That should give the best path, what do you think ?

[karussell]

Exactly. One 'just' needs to put the first two nodes (with the correct weights) in the queue. But additionally one needs to check for two nodes as finish condition instead of only one.

But for that one needs to add a method calcPath to all algorithms that take two EdgeIterator parameters instead of two nodes (+ adjust the finish method for all algorithms). Also we need a bunch of unit tests for this as this is even more complex when pillar nodes (wayGeometry) comes into the game :)

Last but not least one needs the post processing you already have implemented.

[swoker]

I'm hope this is the correct issue, but I'll +1 it
For this path I would expect totally different routes than the ones shown ...
Example: From Ackerstraße 157 Berlin - To Bergstraße 79 Berlin
The green path is my expectation...

by foot

by car

Unfortunately, this issue is keeping me from using Graphhopper in my application.

[karussell]

Closing in favor of #115