Shortest Path using interpolated OSM points

Question

I have a set of GPS points which I have snapped to the OSM network. In the below screenshot GPS points are red, snapped points are green.

I want to calculate the shortest path that includes all of these green way points. My solution is to calculate the shortest path between each pair of points and finally concatenate the results.

My problem is that dijkstra_sp will not accept arbitrary points on the OSM network. My snapped points are not necessarily in the ways table because they were calculated using the following logic.

1) Find the closest way to a given GPS point. 2) Using interpolation, find the closest point on this way to the GPS point.

The snapped points are not in the ways table because they were derived by interpolation.

So my question is: How do I calculate the shortest path between two points on the OSM network that are not necessarily in the ways table?

Kind regards, Cathal

Answer 1

I finally figured out how to do this. I've written a blog post about it here http://cathalsgeo.blogspot.com/2011/04/pgrouting-shortest-path-b.html.

Maybe this will help someone else who is stuck with the same problem.

Answer 2

We solved the same problem with temporary edges and vertices. We snapped our GPS coords to an edge e from v1 to v2 and got an offset between 0 and 1:

segOffset := line_locate_point(geom(e), Point(coords);

With this we created a new Point() and out of this a new vertex v_tmp:

line_interpolate_point(geom(e), segOffset);

We than split our edge e1 into two new edges e_tmp1 from v1 to v_tmp and e_tmp2 from v_tmp to v2. (You could need to split it in into 4 temp endges...)

With our target we did the same. Than we started pgrouting with our new vertices v_tmp_source, v_tmp_dest and thats it.

Answer 3

I matched to the closest nodes, used pgrouting to find the route between these nodes. I was after the total distance, so I then added the two point-node distances.

I had an upper limit on how close a node had to be, to be acceptable.

The math would be more complicated/slower, but you could do the same for edges if you were using a pgrouting algorithm that worked in terms of edges rather than nodes.

Answer 4

(Sorry, somehow I can't comment to "winwaed", so I have to do it with another answer)

The math would be more complicated/slower, but you could do the same for edges if you were using a pgrouting algorithm that worked in terms of edges rather than nodes.

Shooting Star algorithm takes edges instead of nodes.

Answer 5

your problem remembers me to some similar case, that we had to solve some years ago: someone is drawing a path (linestring) on top of a raster map and we had to match this path with the underlaying road network.

This seems to be similar to your red GPS points. And same as you we assumed that we can look for the shortest path between these points.

Because this is so long time ago, I don't remember details anymore. But we published the function(s) in "matching.sql", which is part of pgRouting already. There is no documentation though. Sorry for that. But maybe reading the SQL source gives you some idea how it works: https://github.com/pgRouting/pgrouting/blob/master/core/sql/matching.sql

Answer 6

Sounds to me you are trying to solve the Traveling Salesman Problem. In that case, the most efficient way to go would be using a TSP algorithm...