[GIS] Shortest Path using interpolated OSM points

interpolationpgrouting

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.
enter image description here

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?

Best Answer

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.

Related Question