How to route over (partial) edges in pgrouting?

Question

I have made a route planning system (based on shortest path using A*) like the Google directions service using pgrouting and google maps. It includes clicking on the map to generate waypoints, dragging of waypoints or polylines to change your desired route. It also shows a directions panel with instructions how to get from A to B.

However in the reverse geocoding i use to find out where the user clicks on the map i return the closest node in the topology. This all works pretty well except for some real world cases where a direct route from A to B is longer than an indirect route through D

The blue A,D,B are the nodes and the red C-A, C-B are my mouse clicks that corresponded to those nodes. The red C-C is the place on the edge where i want my route to visit.

If a user wants to go from A to B through the long direct edge it isn't possible atm because it isn't the fastest route.

I am looking for a way to route over edges or partial edges. One can imagine that a user doesn't want to start in a node but somewhere halfway on an edge (this is another use case but i feel it will be solved as well with the answer i seek).

The cleanest way i can come up with is generating temporary nodes on an edge when a user clicks there (see click C-C on the image) by effectively splitting up an edge into 2 edges and placing a new (temporary) node on the split point. This way pgrouting can route over this new node and thus force the route to follow the edges surrounding that new node.

However, this will generate a lot of temporary nodes when dragging a polyline across the map. All those during_drag_generated nodes have to be removed except the one created at drag_end as that one becomes part of the final route.

So i am wondering are there easier ways to solve this?

Answer 1

I solved this problem by indeed adding a temporary node on the clicked edge and adding 2 temporary edges to this temporary node. By manually joining these temporary node and edges before calling shortest_path_astar they are being used for calculating the correct path but they dont clutter your database with extra records that are only interesting for 1 particular user (at 1 particular moment in time).

Here the SQL query i used (in Python):

"SELECT 
    row_number() over (range unbounded preceding) as rownumber, 
    astar.vertex_id, 
    astar.edge_id,
    astar.cost
FROM 
    shortest_path_astar('SELECT 
                            gid as id, 
                            source::integer as source, 
                            target::integer as target,
                            length::double precision as cost, 
                            ST_X(ST_Startpoint(the_geom)) as x1, 
                            ST_Y(ST_Startpoint(the_geom)) as y1, 
                            ST_X(ST_Endpoint(the_geom)) as x2, 
                            ST_Y(ST_Endpoint(the_geom)) as y2 
                        FROM ways 
                        %s', 
                        %s, 
                        %s, 
                        false, 
                        false) astar" % (extra_edges, route_origin, route_destination)

where route_origin or route_destination can be the new temporary (negative) id of the virtual node and extra_edges looks like:

" UNION SELECT %d, %s, %d, ww.length * %f, ST_X(ST_Startpoint(ww.the_geom)), ST_Y(ST_Startpoint(ww.the_geom)), ST_X(ST_Line_Interpolate_Point(ww.the_geom, %f)), ST_Y(ST_Line_Interpolate_Point(ww.the_geom, %f)) FROM ways ww WHERE ww.source = %s AND ww.target = %s" % (edgeid, edge_fromnode, nodeid, perc, perc, perc, edge_fromnode, edge_tonode)
+ " UNION SELECT %d, %d, %s, ww.length * (1-%f), ST_X(ST_Line_Interpolate_Point(ww.the_geom, %f)), ST_Y(ST_Line_Interpolate_Point(ww.the_geom, %f)), ST_X(ST_Endpoint(ww.the_geom)), ST_Y(ST_Endpoint(ww.the_geom)) FROM ways ww WHERE ww.source = %s AND ww.target = %s" % (edgeid-1, nodeid, edge_tonode, perc, perc, perc, edge_fromnode, edge_tonode);

Where edgeid is a unique (negative) id for this temp edge, nodeid a unique (negative) id for this virtual node, edge_fromnode the from node of the original edge, edge_tonode the to node of the original edge, perc is the percentage on the original edge (edge_fromnode, edge_tonode) of the new virtual node.

A week ago (9-1-2012) the pgrouting newsletter also touched this subject. See: Pgrouting-users Digest, Vol 40, Issue 2 -> http://lists.osgeo.org/pipermail/pgrouting-users/2012-January/000927.html