[GIS] Route through water polygons

algorithmpgroutingroutingvector-grid

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.

Best Answer

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 !

Related Question