I have a water-polygon grid shape file as shown (Each grid is 1latx1long):
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:
FeatureGraphGenerator
, assign some weight to the edges withEdgeWeighter
, and compute the shortest path withDijkstraShortestPathFinder
. 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):
EDIT: I have released a library/program implementing the approach mentioned above - Here it is: SeaRoute. Feel free to reuse/contribute !