[GRASS-dev] [GRASS GIS] #3468: r.drain: replace with new r.path, support multiple directions

GDAL · December 19, 2017, 10:02pm

#3468: r.drain: replace with new r.path, support multiple directions
-------------------------+---------------------------------
Reporter: mmetz | Owner: grass-dev@…
Type: enhancement | Status: new
Priority: normal | Milestone: 7.5.0
Component: Raster | Version: svn-releasebranch74
Keywords: r.drain | CPU: All
Platform: All |
-------------------------+---------------------------------
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).

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3468>
GRASS GIS <https://grass.osgeo.org>

GDAL · December 19, 2017, 10:03pm

#3468: r.drain: replace with new r.path, support multiple directions
--------------------------+---------------------------------
  Reporter: mmetz | Owner: grass-dev@…
      Type: enhancement | Status: new
  Priority: normal | Milestone: 7.5.0
Component: Raster | Version: svn-releasebranch74
Resolution: | Keywords: r.drain
       CPU: All | Platform: All
--------------------------+---------------------------------
Changes (by mmetz):

* Attachment "multiple-directions-path.png" added.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3468>
GRASS GIS <https://grass.osgeo.org>

GDAL · December 20, 2017, 10:07am

#3468: r.drain: replace with new r.path, support multiple directions
--------------------------+---------------------------------
  Reporter: mmetz | Owner: grass-dev@…
      Type: enhancement | Status: new
  Priority: normal | Milestone: 7.5.0
Component: Raster | Version: svn-releasebranch74
Resolution: | Keywords: r.drain
       CPU: All | Platform: All
--------------------------+---------------------------------

Comment (by mlennert):

Replying to [ticket:3468 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

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3468#comment:1>
GRASS GIS <https://grass.osgeo.org>

GDAL · December 20, 2017, 7:32pm

#3468: r.drain: replace with new r.path, support multiple directions
--------------------------+---------------------------------
  Reporter: mmetz | Owner: grass-dev@…
      Type: enhancement | Status: new
  Priority: normal | Milestone: 7.5.0
Component: Raster | Version: svn-releasebranch74
Resolution: | Keywords: r.drain
       CPU: All | Platform: All
--------------------------+---------------------------------

Comment (by wenzeslaus):

Replying to [ticket:3468 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!

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3468#comment:2>
GRASS GIS <https://grass.osgeo.org>

GDAL · December 20, 2017, 10:41pm

#3468: r.drain: replace with new r.path, support multiple directions
--------------------------+---------------------------------
  Reporter: mmetz | Owner: grass-dev@…
      Type: enhancement | Status: new
  Priority: normal | Milestone: 7.5.0
Component: Raster | Version: svn-releasebranch74
Resolution: | Keywords: r.drain
       CPU: All | Platform: All
--------------------------+---------------------------------

Comment (by mmetz):

Replying to [comment:2 wenzeslaus]:
> Replying to [ticket:3468 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).

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3468#comment:3>
GRASS GIS <https://grass.osgeo.org>

GDAL · December 21, 2017, 3:50am

#3468: r.drain: replace with new r.path, support multiple directions
--------------------------+---------------------------------
  Reporter: mmetz | Owner: grass-dev@…
      Type: enhancement | Status: new
  Priority: normal | Milestone: 7.5.0
Component: Raster | Version: svn-releasebranch74
Resolution: | Keywords: r.drain
       CPU: All | Platform: All
--------------------------+---------------------------------

Comment (by wenzeslaus):

Replying to [comment:3 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.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3468#comment:4>
GRASS GIS <https://grass.osgeo.org>

GDAL · December 21, 2017, 9:42am

#3468: r.drain: replace with new r.path, support multiple directions
--------------------------+---------------------------------
  Reporter: mmetz | Owner: grass-dev@…
      Type: enhancement | Status: new
  Priority: normal | Milestone: 7.5.0
Component: Raster | Version: svn-releasebranch74
Resolution: | Keywords: r.drain
       CPU: All | Platform: All
--------------------------+---------------------------------

Comment (by mmetz):

Replying to [comment:4 wenzeslaus]:
> Replying to [comment:3 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.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3468#comment:5>
GRASS GIS <https://grass.osgeo.org>

GDAL · December 22, 2017, 8:06pm

#3468: r.drain: replace with new r.path, support multiple directions
--------------------------+---------------------------------
  Reporter: mmetz | Owner: grass-dev@…
      Type: enhancement | Status: new
  Priority: normal | Milestone: 7.5.0
Component: Raster | Version: svn-releasebranch74
Resolution: | Keywords: r.drain
       CPU: All | Platform: All
--------------------------+---------------------------------

Comment (by mmetz):

Replying to [comment:5 mmetz]:
> Replying to [comment:4 wenzeslaus]:
> > Replying to [comment:3 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.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3468#comment:6>
GRASS GIS <https://grass.osgeo.org>

GDAL · December 23, 2017, 12:20pm

#3468: r.drain: replace with new r.path, support multiple directions
--------------------------+---------------------------------
  Reporter: mmetz | Owner: grass-dev@…
      Type: enhancement | Status: new
  Priority: normal | Milestone: 7.5.0
Component: Raster | Version: svn-releasebranch74
Resolution: | Keywords: r.drain
       CPU: All | Platform: All
--------------------------+---------------------------------

Comment (by hellik):

Replying to [comment:3 mmetz]:
>
> Implemented in r71962 (added r.path) and r71963 (updated r.cost/r.walk).

in the manual, see
[https://trac.osgeo.org/grass/browser/grass/trunk/raster/r.path/r.path.html#L73
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?

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3468#comment:7>
GRASS GIS <https://grass.osgeo.org>

GDAL · December 28, 2017, 9:37pm

#3468: r.drain: replace with new r.path, support multiple directions
--------------------------+---------------------------------
  Reporter: mmetz | Owner: grass-dev@…
      Type: enhancement | Status: new
  Priority: normal | Milestone: 7.5.0
Component: Raster | Version: svn-releasebranch74
Resolution: | Keywords: r.drain
       CPU: All | Platform: All
--------------------------+---------------------------------

Comment (by mmetz):

Replying to [comment:7 hellik]:
> Replying to [comment:3 mmetz]:
> >
> > Implemented in r71962 (added r.path) and r71963 (updated
r.cost/r.walk).
>
> in the manual, see
[https://trac.osgeo.org/grass/browser/grass/trunk/raster/r.path/r.path.html#L73
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.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3468#comment:8>
GRASS GIS <https://grass.osgeo.org>