[GRASS-dev] [GRASS GIS] #2368: Python version of r.grow does not support shrinking

GRASS GIS GRASS GIS developer
1

#2368: Python version of r.grow does not support shrinking
----------------------------------------------------------------+-----------
Reporter: wenzeslaus | Owner: grass-dev@…
     Type: enhancement | Status: new
Priority: normal | Milestone: 7.1.0
Component: Raster | Version: svn-trunk
Keywords: r.grow, r.grow.distance, r.buffer, r.buffer.lowmem | Platform: Unspecified
      Cpu: Unspecified |
----------------------------------------------------------------+-----------
While C version of `r.grow` supports shrinking (negative distance/radius)
since r59735, the Python version of `r.grow` based on C module
`r.grow.distance` and `r.mapcalc` expression supports only growing
(positive distance/radius). Shrinking (negative buffer) is a useful
feature, so I think we should add it.

I'm not sure if negative distances can be added to `r.grow.distance`.

If not, I would say that we need to use C implementation of `r.grow`
(which might be even faster then the Python script version which calls
several modules and creates temporary maps).

If duplication of code would be an issue in case of C `r.grow` and
`r.grow.distance`, we may consider adding some functions to the library if
they are useful for more modules.

`r.buffer` and `r.buffer.lowmem` does not seem to support it neither, as
far as I know.

`v.buffer` supports negative distances ("inward buffer" / "negative
buffer").

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/2368&gt;
GRASS GIS <http://grass.osgeo.org>

2

#2368: Python version of r.grow does not support shrinking
----------------------------------------------------------------+-----------
Reporter: wenzeslaus | Owner: grass-dev@…
     Type: enhancement | Status: new
Priority: normal | Milestone: 7.1.0
Component: Raster | Version: svn-trunk
Keywords: r.grow, r.grow.distance, r.buffer, r.buffer.lowmem | Platform: Unspecified
      Cpu: Unspecified |
----------------------------------------------------------------+-----------

Comment(by glynn):

Replying to [ticket:2368 wenzeslaus]:

> While C version of `r.grow` supports shrinking (negative
distance/radius) since r59735, the Python version of `r.grow` based on C
module `r.grow.distance` and `r.mapcalc` expression supports only growing
(positive distance/radius). Shrinking (negative buffer) is a useful
feature, so I think we should add it.

For me, the question isn't whether it's useful, but whether it belongs in
r.grow, as opposed to a separate r.shrink module. The two operations are
quite different (growing has to determine the correct value for "new"
cells, shrinking only discards data).

> I'm not sure if negative distances can be added to `r.grow.distance`.

Shrinking can be implemented using r.grow.distance by first generating an
"inverted" map (null if the input is non-null, non-null if the input is
null), growing the inverted map, inverting the result, then using it as a
mask.

Whether this will be faster than the C version depends upon the size of
the buffer and the proportion of non-null cells. The worst-case time for
r.grow.distance is proportional to the size of the input, whereas the
worst-case time for the C version of r.grow is also proportional to the
size of the buffer (specifically, to its area, i.e. the square of its
radius).

For a sufficiently large buffer, r.grow.distance will be faster. Unless
the cross-over point is unreasonably large, it may be worth implementing
an r.grow.distance-based version even if the C version of r.grow is
provided.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/2368#comment:1&gt;
GRASS GIS <http://grass.osgeo.org>

3

#2368: Python version of r.grow does not support shrinking
----------------------------------------------------------------+-----------
Reporter: wenzeslaus | Owner: grass-dev@…
     Type: enhancement | Status: new
Priority: normal | Milestone: 7.1.0
Component: Raster | Version: svn-trunk
Keywords: r.grow, r.grow.distance, r.buffer, r.buffer.lowmem | Platform: Unspecified
      Cpu: Unspecified |
----------------------------------------------------------------+-----------

Comment(by wenzeslaus):

Replying to [comment:1 glynn]:
> Replying to [ticket:2368 wenzeslaus]:
>
> > While C version of `r.grow` supports shrinking (negative
distance/radius) since r59735, the Python version of `r.grow` based on C
module `r.grow.distance` and `r.mapcalc` expression supports only growing
(positive distance/radius). Shrinking (negative buffer) is a useful
feature, so I think we should add it.
>
> For me, the question isn't whether it's useful, but whether it belongs
in r.grow, as opposed to a separate r.shrink module. The two operations
are quite different (growing has to determine the correct value for "new"
cells, shrinking only discards data).
>
`r.shrink`, this makes sense. But maybe the difference is not so big. What
about shrinking the original values but putting there some new ones.

> > I'm not sure if negative distances can be added to `r.grow.distance`.
>
> Shrinking can be implemented using r.grow.distance by first generating
an "inverted" map (null if the input is non-null, non-null if the input is
null), growing the inverted map, inverting the result, then using it as a
mask.

Creating yet another intermediate map, this is what I'm afraid of, this is
always slow.
>
> Whether this will be faster than the C version depends upon the size of
the buffer and the proportion of non-null cells. The worst-case time for
r.grow.distance is proportional to the size of the input, whereas the
worst-case time for the C version of r.grow is also proportional to the
size of the buffer (specifically, to its area, i.e. the square of its
radius).
>
> For a sufficiently large buffer, r.grow.distance will be faster. Unless
the cross-over point is unreasonably large, it may be worth implementing
an r.grow.distance-based version even if the C version of r.grow is
provided.

Having two versions of the same module is inconvenient. What about moving
C version of `r.grow` to addons under a different name. I don't have any
suggestion right now but perhaps somebody else has.

--
Ticket URL: <http://trac.osgeo.org/grass/ticket/2368#comment:2&gt;
GRASS GIS <http://grass.osgeo.org>

4

#2368: Python version of r.grow does not support shrinking
----------------------------------------------------------------+-----------
Reporter: wenzeslaus | Owner: grass-dev@…
     Type: enhancement | Status: new
Priority: normal | Milestone: 7.1.0
Component: Raster | Version: svn-trunk
Keywords: r.grow, r.grow.distance, r.buffer, r.buffer.lowmem | Platform: Unspecified
      Cpu: Unspecified |
----------------------------------------------------------------+-----------

Comment(by glynn):

Replying to [comment:2 wenzeslaus]:

> > > I'm not sure if negative distances can be added to
`r.grow.distance`.

Having thought about this some more ...

In the case where you're interested in the distance= map (rather than the
value= map), distance inside is just as meaningful as distance outside.

An r.shrink.distance module would be structurally similar (i.e. a near
clone), so it makes sense to try to keep them in the same module.

The easiest change would be to have an "invert" flag which caused the
distance= map to contain the distance from the nearest null cell
(currently, it's the distance from the nearest non-null cell, so the non-
null cells themselves have a distance of 0).

The value= map (which normally contains the value of the nearest non-null
cell) would be meaningless in this case; the value of the nearest null
cell is always null.

Alternatively, it could calculate both positive and negative distances
simultaneously, and could probably even use the same arrays for both
calculations.

(Would we need to add a flag to enable negative distances? It's an
incompatible change, but the module is new in 7.0. Are the 7.0 betas
something with we now need to retain compatibility?).

For non-null cells, the {old,new}_{x,y}_row and dist_row arrays always
contain zero (i.e. the x and y offsets and the distance to the nearest
non-null cell are always zero), and the {old,new}_val_row arrays (the
value of the nearest non-null cell) always contain the current cell's
value. This is all information which can be deduced directly from the
current input row.

It's only for null cells where the arrays contain accumulated results.

The only drawback is that lookups would be complicated slightly, but the
performance impact should be trivial.

--
Ticket URL: <http://trac.osgeo.org/grass/ticket/2368#comment:3&gt;
GRASS GIS <http://grass.osgeo.org>

5

#2368: Python version of r.grow does not support shrinking
----------------------------------------------------------------+-----------
Reporter: wenzeslaus | Owner: grass-dev@…
     Type: enhancement | Status: new
Priority: normal | Milestone: 7.1.0
Component: Raster | Version: svn-trunk
Keywords: r.grow, r.grow.distance, r.buffer, r.buffer.lowmem | Platform: Unspecified
      Cpu: Unspecified |
----------------------------------------------------------------+-----------

Comment(by wenzeslaus):

As a quick solution to enable functionality of C version of `r.grow` I
would suggest to move it to addons under a different name (`r.grow.c`,
`r.grow2`, `r.grow.negative`, `r.grow.inside`, `r.grow.shrink`?). This
will provide convenient access to this functionality before what
[comment:3 glynn] is suggesting gets implemented.

--
Ticket URL: <http://trac.osgeo.org/grass/ticket/2368#comment:4&gt;
GRASS GIS <http://grass.osgeo.org>

6

#2368: Python version of r.grow does not support shrinking
----------------------------------------------------------------+-----------
Reporter: wenzeslaus | Owner: grass-dev@…
     Type: enhancement | Status: new
Priority: minor | Milestone: 7.1.0
Component: Raster | Version: svn-trunk
Keywords: r.grow, r.grow.distance, r.buffer, r.buffer.lowmem | Platform: Unspecified
      Cpu: Unspecified |
----------------------------------------------------------------+-----------
Changes (by wenzeslaus):

  * priority: normal => minor

Comment:

C version of `r.grow` moved to addons as `r.grow.shrink` in r62819, so the
shrinking functionality is available for all without compiling.

However, I would like to see this ticket resolved by adding the
functionality as suggested earlier.

--
Ticket URL: <http://trac.osgeo.org/grass/ticket/2368#comment:5&gt;
GRASS GIS <http://grass.osgeo.org>

7

#2368: Python version of r.grow does not support shrinking
----------------------------------------------------------------+-----------
Reporter: wenzeslaus | Owner: grass-dev@…
     Type: enhancement | Status: new
Priority: minor | Milestone: 7.1.0
Component: Raster | Version: svn-trunk
Keywords: r.grow, r.grow.distance, r.buffer, r.buffer.lowmem | Platform: Unspecified
      Cpu: Unspecified |
----------------------------------------------------------------+-----------

Comment(by mmetz):

Replying to [comment:3 glynn]:
> Replying to [comment:2 wenzeslaus]:
>
> > > > I'm not sure if negative distances can be added to
`r.grow.distance`.
>
> Having thought about this some more ...
>
> In the case where you're interested in the distance= map (rather than
the value= map), distance inside is just as meaningful as distance
outside.
>
> An r.shrink.distance module would be structurally similar (i.e. a near
clone), so it makes sense to try to keep them in the same module.
>
> The easiest change would be to have an "invert" flag which caused the
distance= map to contain the distance from the nearest null cell
(currently, it's the distance from the nearest non-null cell, so the non-
null cells themselves have a distance of 0).

Attached is a minimally invasive patch to add a new flag to
r.grow.distance, calculating the distance to the nearest null cell.

--
Ticket URL: <http://trac.osgeo.org/grass/ticket/2368#comment:6&gt;
GRASS GIS <http://grass.osgeo.org>