# Shortest Path using interpolated OSM points

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

-

## 6 Answers

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.

-
Neither closest node nor edge based procedures are going to work, see the below example. dl.dropbox.com/u/11502389/Screenshot2.png The blue lines are the ways that the each green dots are on. – user2249 Mar 9 '11 at 15:14

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

-
Using closest nodes doesn't work, consider the below example. – user2249 Mar 9 '11 at 14:42
This matching function I mention does a combination of matching to nodes and road segments. It depends how close your GPS point is to a node. If you are very close to a crossing, your GPS point might be closer to an edge, that it actually shouldn't be assigned to. – dkastl Mar 11 '11 at 3:29

(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.

-

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.

-
that's great! I'm curious about the code, if you're happy to share, as I'm trying to learn how to use pgrouting. – djq Apr 13 '11 at 14:46
Very nice, but i don't get why the calculated point is never perpendicular on the closest edge. I know postgis has a method for getting the closest point on a line (i think it is st_line_locate_point). Are you using that? Is your solution available for public use? – mrg Aug 26 '11 at 15:39

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.

-

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...

-