# Creating optimised path between nodes avoiding polygons entities using QGIS

I have a point shapefile representing seaports. I have the linear cost of shipping for every seaport pairing (specific shipping cost to go from one point to another point). I want to find a way of creating shipping routes (lines) between all nodes.

Then I will be able to give, for every line, a specific linear cost (\$/km), so I can calculate, if I want to go from seaport A to Seaport Z, which path is cost optimised through pgRouting.

On top of that, as a constraint, I want the shipping to avoid land (I have a shapefile of land polygons). That's the real difficulty, because that's way more difficult than a "shortest path" method and I can't figure out any method to deal with this difficulty as a novice.

Here is a...unique(??) way of doing it. I managed to create routes using QGIS 2.14 with GRASS and rasters. I got the idea from here. To summarize we will rasterize the land and sea, run a proximity algorithim, invert the output, run a cost, and drain algorithm in GRASS and finally polygonize the routes to polylines.

1) Rasterize your land and sea. First ensure your land is a single multi-polygon (Vector > Geometry Tools > Singleparts to Multipart). If you don't have a sea polygon, create one, and add rings around any islands. Merge your land and sea layers together (Vector > Data Management Tools > Merge Shapefiles to One). In the attribute table of the new merged layer you should now have two features (one land, one sea). Add a new column for a value and have land = 0, sea = 1. Rasterize (Raster > Conversion > Rasterize):

``````Input File = land/sea layer
Attribute Field = value
Raster Resolution = Don't use anything too fine as it will really increase
computing time. Alternatively too course will degrade
accuracy
``````

This will create a two tone raster where all land is 0 and sea is 1 This is some example data I created to test to problem with (Black = land, white = sea)

2) Calculate distance from land. Using your new raster (referred to as 'Area raster') run the proximity algorithm (Raster > Analysis > Proximity (Raster Distance)). This is the QGIS version of a Euclidean Distance analysis where each cell is given an increasing value the further away it is from a target cell.

``````Input file = Area Raster
Output file = Proximity Raster
Dist units = PIXEL
``````

Now comes the really horrible part. I haven't found a good way of inverting the values in the proximity raster so I:

a. Polygonized the layer (Raster > Conversion > Polygonize)

b. Used singleparts to multipart to collate all values into their unique values. Luckily this puts the values in ascending order.

c. Create new column (inv_val) in attribute table

d. Hand type into the new column each value in descending order. My example had 364 unique values so it didn't take too long but your using real world data so it could be much larger. This is where choosing the right resolution really helps.

NOTE: IF ANYONE KNOWS A BETTER WAY OF DOING THIS BIT THEN IT'LL SPEED EVERYTHING UP.

e. Rasterize this layer using "inv_val" column for raster values.

You should now have a new raster with inverted value to your proximity raster.

Proximty raster using test data

Inverted Proximity raster using test data

The inversion has to happen so we can use the GRASS tools. r.drain works by finding the cheapest route across a raster. Had we just used the Proximity raster, r.drain would stick on or close to land (which I understand is bad for boats). Inverting proximity will make r.drain stick to the water furthest from land.

The reason we inverted proximity was to create a cost raster. Proximity showed us that each pixel is a distance (in pixels) from the originating point (this being the land polygon boundary). Inverting those distance values now shows that its a greater distance from the furthest sea pixel. In cost terms it is more expensive the closer you are to land, and cheaper to be in open water.

3) Calculate route. This is where GRASS comes in. You could use the standalone version but I find GRASS in QGIS pretty easy and a lot more user friendly (The instructions follow GRASS IN QGIS). Make sure you've got GRASS setup properly for this. (download the GRASS plugin for QGIS).

Open your GRASS mapset and open the GRASS tools if it doesn't automatically open. Run "r.gdal.in.qgis" to load your inverted proximity raster into GRASS. Click "View Output" and the new GRASS layer will be added into QGIS In the "Region" tab at the top of the GRASS Tools window, click "Select the extent by dragging on canvas" and draw a a rectangle around the GRASS raster. This limits the GRASS calculation area.

Now run "r.cost.coord". Select your GRASS proximity raster as input. Use seaport A as starting coordinates and (under advanced options) use seaport B as the end coordinates (to calculate the AB route). You can also check "Knights Move" which is slower but more accurate.

As explained earlier the inverse proximity is a cost raster. "r.cost.coord" calculates the accumulated cost from point A to Point B. You shouldn't use "r.cost.vect" as it takes all your points as a single starting location, so the most expensive point would be the furthest distance away from all seaport points.

Now run "r.drain"

``````Input = r.cost.coord output
output = AB_Route
Starting coordinates  = seaport B
``````

You have to use the end coordinates you used in r.cost as r.drain is a regressive tool, identifying flow from the top (most expensive) to the bottom (least expensive, source).

Now just convert the drain raster to polygon ("r.to.vect.line") and export it out of GRASS. You mentioned you wanted to use pgRouting so it could be your best bet to use "v.out.ogr.pg" which will export straight to PostGIS/PostgreSQL.

CAVEAT: Not only is the raster inversion convoluted, but you would have to repeat "r.cost.coord" for every possible route between seaports, then run r.drain on each of those. I do have a sneaky suspicion that this could be dramatically shortened using python to loop through everything but that outside of my scope. The r.drain tool follows the cheapest route home, so it's not really designed for shortest path which is why it takes some funny routes through open water. It does give land the widest possible berth, which must be good for boats, but it is by no means the most efficient route.

Even if this doesn't answer your question fully, I hope it's given you some good ideas on how to achieve this.

• I got an answer for inverting the raster which seemed to work for me. gis.stackexchange.com/questions/262629/…. This is an awesome tool, I'm using it to trace shopping mall routes. Theoretically you could put all these algorithms into the qgis modeler and run them fairly quickly with out all the outputs. I haven't tried yet since I'm still testing it to get a better result. Nov 22, 2017 at 17:54