I have a water-polygon grid shape file as shown (Each grid is 1latx1long): Water polygon grid shape file in QGIS

I have created this in QGIS and files (coastal lines and land polygons) selected from http://openstreetmapdata.com/data Now if I have given a source grid and a destination grid, I have to come up with different routing ways (shortest path, dijkstra or at-least one of them). pgrouting is the way to go, if I am interested in all the different algorithms. These are my questions: 1. Is there any other simpler way than pgrouting 2. How can I create the road topology for this grid structure.

  • 4
    Normally routing over polygons would be done as a least cost path analysis in Raster not vector based network routing. Commented Aug 25, 2013 at 18:51
  • I am not interested in raster based one. I have created another shape file with the centroids of the above water-polygon grids. So it's a shape file with multiple points. I am looking for ways to route from one to another location. Any suggestions?
    – kaja
    Commented Aug 26, 2013 at 15:20
  • So you want to create create a line network of all points to all other points? GRASS v.net stuff comes to mind for creating the topology which can then be exported to other network analysis tools (though many of them have special formats) Commented Sep 10, 2013 at 21:29
  • Yeah I don't see polygons being the best way to do this. Raster is likely the best way forward. There is a good guide using Grass, which might point you in the correct direction: gracilis.carleton.ca/CUOSGwiki/index.php/… Commented Jan 23, 2015 at 13:40

1 Answer 1


If your objective is to develop a routing program over the sea returning various maritime routes from (origin,destination) pairs, you should rather rely on a linear mesh covering the seas, instead of polygons. I had exactly the same goal and I did something using:

  • The shipping lane dataset "Oak Ridge National Labs CTA Transportation Network Group, Global Shipping Lane Network, World, 2000" available on geocommon. I did not find any more detailled dataset despite this question...
  • The Dijskra shortest path finder in geotools. If you know a bit of Java, it is rather easy to use. You have to load the maritime lines from the SHP file, transform it into a graph using the FeatureGraphGenerator, assign some weight to the edges with EdgeWeighter, and compute the shortest path with DijkstraShortestPathFinder. Tada! I find PGrouting a bit to big for just computing shortest paths.

It is possible to densify the input dataset to get more detailled routes, but then execution time should increase.

Here is an example of output (the red line):

enter image description here

EDIT: I have released a library/program implementing the approach mentioned above - Here it is: SeaRoute. Feel free to reuse/contribute !

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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