Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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

enter image description here

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?

share|improve this question
    
Why would you have a lot of point? You compute the route between two points. If the user drag the polyline, it will happen on the client side, so it is not routing-dependant. When the user click on the polyline move it, and then stop moving the mouse, the route is recomputed between three points instead of two. So instead of having 1 route, I suspect what you should do is compute two different routes, and then merge the results. So for each route, you will only split edge between two points. Isn't it the flow you would want to use? –  Fabien Ancelin Oct 25 '11 at 16:55
    
Temporary nodes appears to be the only way to achieve a solution with the current state of pgRouting. Did you use a built in function to insert nodes (vertexes) into the graph, or hand roll something? –  Steve Horn Jan 5 '12 at 14:43
    
I add the temporary nodes into the sql query that does the shortest path with a join. –  mrg Jan 6 '12 at 13:50

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
Would you mind sharing the query? I'm sure it would be very helpful for others. Thank you! –  underdark Jan 21 '12 at 11:38
1  
I added the query i used for my OSM case (table generated by osm2pgrouting). It might look a bit complex but if you need to dig into this material for your own case it will become clear and else you can always contact me here for further explanation. –  mrg Jan 21 '12 at 12:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.