r.drain: replace with new r.path, support multiple directions

[mmetz]

r.drain is a clone of r.fill.dir, with the added functionality to extract a path from a given start point to the nearest outlet, using internally calculated directions. Later on, the option to supply a direction map was added in order to support output from r.cost, r.walk, and r.watershed. This code duplication should be avoided. A new module r.path could be added that uses a direction map with optional surface map to trace paths. r.drain could then be converted to a script calling r.path. If no direction map is supplied, r.fill.dir can be used by r.drain to create a direction map.

r.fill.dir uses a bitmask to encode multiple directions from a single cell, as described by Jenson and Domingue (1988). These multiple directions are internally resolved to find the main (single) flow direction which is then recoded to a standard direction format using degrees. This bitmask to encode multiple directions from a single cell could be used and exposed by various other modules, i.e. r.cost, r.walk, r.watershed, to be used as input for r.path. As a result, the least costly path from a single start point to a single stop point can split and merge repeatedly (see attached multiple-directions-path.png).

[mlennert]

Replying to mmetz:

r.drain is a clone of r.fill.dir, with the added functionality to extract a path from a given start point to the nearest outlet, using internally calculated directions. Later on, the option to supply a direction map was added in order to support output from r.cost, r.walk, and r.watershed. This code duplication should be avoided. A new module r.path could be added that uses a direction map with optional surface map to trace paths. r.drain could then be converted to a script calling r.path. If no direction map is supplied, r.fill.dir can be used by r.drain to create a direction map.

+1

r.fill.dir uses a bitmask to encode multiple directions from a single cell, as described by Jenson and Domingue (1988). These multiple directions are internally resolved to find the main (single) flow direction which is then recoded to a standard direction format using degrees. This bitmask to encode multiple directions from a single cell could be used and exposed by various other modules, i.e. r.cost, r.walk, r.watershed, to be used as input for r.path. As a result, the least costly path from a single start point to a single stop point can split and merge repeatedly (see attached multiple-directions-path.png).

+1

;-)

[wenzeslaus]

Replying to mmetz:

A new module r.path could be added that uses a direction map with optional surface map to trace paths. r.drain could then be converted to a script calling r.path. If no direction map is supplied, r.fill.dir can be used by r.drain to create a direction map.

Sounds good. Similar to the case of r.grow and r.grow.distance (and replacing what is now r.grow.shrink in addons).

Once r.drain is a script, it would be great if we can manage to also remove the need for providing a "dummy" cost map. See r.mapcalc "const1 = 1" in a r.drain example I created recently (please, correct me if I'm wrong):

https://grass.osgeo.org/grass74/manuals/r.drain.html#path-following-directions

r.fill.dir uses a bitmask to encode multiple directions from a single cell, as described by Jenson and Domingue (1988). These multiple directions are internally resolved to find the main (single) flow direction which is then recoded to a standard direction format using degrees. This bitmask to encode multiple directions from a single cell could be used and exposed by various other modules,

This makes sense to me also in light of what I have recently dealt with in r71809 (null values if conversion fails). We are potentially throwing out information and this was partially related to the fact that until recently it was hiding some potential problems in r.fill.dir (the problems are still there, just not as hidden as before).

Jenson and Domingue (1988) is a format described in a paper and it makes sense adding it. Any ideas for a name? The current ones (in r.fill.dir) are not really descriptive (agnps, answers, grass).

i.e. r.cost, r.walk, r.watershed, to be used as input for r.path.

One common format for all modules would be great. It is strange when user needs to recompute the angles like in my r.drain example from above (again, correct me if I'm wrong):

https://grass.osgeo.org/grass74/manuals/r.drain.html#path-following-directions

the least costly path from a single start point to a single stop point can split and merge repeatedly (see attached multiple-directions-path.png).

Looks great!

[mmetz]

Replying to wenzeslaus:

Replying to mmetz:

[...]

Once r.drain is a script, it would be great if we can manage to also remove the need for providing a "dummy" cost map. See r.mapcalc "const1 = 1" in a r.drain example I created recently (please, correct me if I'm wrong):

https://grass.osgeo.org/grass74/manuals/r.drain.html#path-following-directions

Yes, a dummy cost map should not be needed. Either an elevation map or a direction map is needed. If a direction map is not provided, an elevation map will be needed to create a direction map with r.fill.dir.

Jenson and Domingue (1988) is a format described in a paper and it makes sense adding it. Any ideas for a name? The current ones (in r.fill.dir) are not really descriptive (agnps, answers, grass).

I suggest bitmask as a new name. This name is also not really descriptive and should be explained in the manual of r.fill.dir. BTW, the manual of r.fill.dir provides clear explanations of agnps, answers, grass.

i.e. r.cost, r.walk, r.watershed, to be used as input for r.path.

One common format for all modules would be great.

Two common formats: 1. degrees CCW from East, 2. bitmask for multiple directions as described by Jenson and Domingue (1988)

It is strange when user needs to recompute the angles like in my r.drain example from above (again, correct me if I'm wrong):

https://grass.osgeo.org/grass74/manuals/r.drain.html#path-following-directions

That would be a substantial change because other modules (all r.stream.*) depend on the direction output of r.watershed.

the least costly path from a single start point to a single stop point can split and merge repeatedly (see attached multiple-directions-path.png).

Looks great!

Implemented in r71962 (added r.path) and r71963 (updated r.cost/r.walk).

[wenzeslaus]

Replying to mmetz:

That would be a substantial change because other modules (all r.stream.*) depend on the direction output of r.watershed.

Then I guess we have 3 standards and all make sense. Should all the modules have flags, or perhaps an option as r.fill.dir, to set the desired direction encoding/format?

Implemented in r71962 (added r.path) and r71963 (updated r.cost/r.walk).

Thank you.

With the naming, I hit an issues with r.path versus r.patch, but I don't see any better alternatives. As for the functionality, r.spreadpath now comes to my mind, but I don't know right now the relation of backlinks there and direction from neighbor and to neighbor.

In r71964 I added an image and extended the example, anybody please review.

[mmetz]

Replying to wenzeslaus:

Replying to mmetz:

That would be a substantial change because other modules (all r.stream.*) depend on the direction output of r.watershed.

Then I guess we have 3 standards and all make sense. Should all the modules have flags, or perhaps an option as r.fill.dir, to set the desired direction encoding/format?

Right now, I have introduced a new -b flag, but that only makes sense if there are 2 possible formats. For more different formats, an option as r.fill.dir would make sense.

Instead of changing lots of existing modules, r.path could be enhanced to support more different direction formats, e.g. r.watershed's directions.

With the naming, I hit an issues with r.path versus r.patch, but I don't see any better alternatives. As for the functionality, r.spreadpath now comes to my mind, but I don't know right now the relation of backlinks there and direction from neighbor and to neighbor.

If r.spread would produce standard directions instead of x_output, y_output with backlink coordinates, r.spreadpath would no longer be needed and r.path can be used instead.

In r71964 I added an image and extended the example, anybody please review.

Thanks.

[mmetz]

Replying to mmetz:

Replying to wenzeslaus:

Replying to mmetz:

That would be a substantial change because other modules (all r.stream.*) depend on the direction output of r.watershed.

Then I guess we have 3 standards and all make sense. Should all the modules have flags, or perhaps an option as r.fill.dir, to set the desired direction encoding/format?

Right now, I have introduced a new -b flag, but that only makes sense if there are 2 possible formats. For more different formats, an option as r.fill.dir would make sense.

I have removed the -b flag and added an option to define the format of the input direction map in r71967.

Instead of changing lots of existing modules, r.path could be enhanced to support more different direction formats, e.g. r.watershed's directions.

Supported formats are r.watershed's directions, degrees CCW from east and bitmask encoded directions. By default, r.path tries to automatically detect the format of the input direction map.

[hellik]

Replying to mmetz:

Implemented in r71962 (added r.path) and r71963 (updated r.cost/r.walk).

in the manual, see ​manual source L73

i.e. a cell with the value 135 means the next cell is to the North-West, 
and a cell with the value 157.5 means that the next cell is to the 
West-North-West-

maybe some missing part of the sentence?

[mmetz]

Replying to hellik:

Replying to mmetz:

Implemented in r71962 (added r.path) and r71963 (updated r.cost/r.walk).

in the manual, see ​manual source L73

i.e. a cell with the value 135 means the next cell is to the North-West, 
and a cell with the value 157.5 means that the next cell is to the 
West-North-West-

maybe some missing part of the sentence?

No, it should be West-North-West. Fixed in trunk r71991.

[martinl]

Milestone renamed

[martinl]

Ticket retargeted after milestone closed

[martinl]

Ticket retargeted after milestone closed