3

I have one shapefile which consists of all the streets in the study area, and another shapefile which has points representing origins and destinations.

Is it possible to find shortest path between all origins and destinations, using the links in the link shapefile?

I primarily use Python, Networkx and QGIS for my work, so it would be great to use these tools for this task.

enter image description here

Improve this question
  • 1
    Is the network topology ready or do you need to still prepare it? – underdark♦ Jun 6 '14 at 11:34
  • @underdark network is ready. – Alex Jun 6 '14 at 15:51
  • Have you tried anitagraser.com/2013/10/19/… – underdark♦ Jun 6 '14 at 17:18
  • @underdark I've worked with that library before. It does allow to attach nodes to graph, but it doesn't contain as many functions as networkx has, and pre/post processing steps make it usually considerably slower, when you consider the whole program. I would like to stick to networkx if possible. – Alex Jun 6 '14 at 22:16
  • 2
    OK, understood. First you'll need to co-register your points to your network. I think the approach I outlined here should work: gis.stackexchange.com/questions/396/… – scw Jun 10 '14 at 21:37
6
+50

The harder initial problem to solve is co-registering your point data with your network. These data may have come from different sources, and so some positional error is to be expected. In the absence of more complex rules governing how points should be located in the network, you can use the closest point on the network to each origin/destination as shown in this existing answer. The challenge here is finding the nearest location along the line, not just the closest vertex:

nearest-point-on-line-ex

Once you've done that step, you should have your original network, and the newly co-registered points. From there, you can use the nx_shp function of NetworkX to import the shapefile into a graph model.

And though it isn't documented, if you peek at the source, you'll see that if you create a shapefile with two layers, one of points and one of lines, it will use your points as the nodes, and the lines as the edges, which can be useful.

Improve this answer
  • Great! The problem is that this intersection node is somewhere in between 2 ends of an existing edge (unless it's itself endpoint). So the best thing would be to break the edge somehow at that point, so that it becomes "attached" to the graph, and hence routable. – Alex Jun 14 '14 at 1:04
  • 1
    @Pep: right, you have a couple of options. If you're looking to build a permanent data structure, you could edit the line segment and insert that point, by adding two new segments when you find the closest one. If you just wanted to do it one-off, then compute the linear distance to each closest vertex, then do the cost path to those two locations and see which one is shorter with cost + dist_to_vertex. – scw Jun 14 '14 at 2:29
3

QGIS 1.8 has a built-in class called qgis.networkanalysis, it has functions to tie points to lines and calculate shortest path.

Improve this answer
  • But it does it implicitly, and it does not calculate the length of this connection link, which can be pretty critical in many cases. – Alex Jun 13 '14 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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