[GRASS-dev] New module: r.grow.distance

GRASS GRASS developer
1

I have added a new module, r.grow.distance, which generates a map
where the value of each cell is the distance to the nearest non-null
cell in the input map (similar to r.cost with a constant cost, except
that you get real circles rather than approximations).

Suggestions for a better name are welcome; r.distance was already
taken.

Unlike r.buffer, it doesn't require loading the entire map into
memory, so (in conjuction with r.recode) it may also be useful as an
alternative to r.buffer for large maps.

--
Glynn Clements <glynn@gclements.plus.com>

2

Glynn:

I have added a new module, r.grow.distance, which generates a map
where the value of each cell is the distance to the nearest non-null
cell in the input map (similar to r.cost with a constant cost, except
that you get real circles rather than approximations).

ie better than r.cost's knight's move / octagon. (?)

Suggestions for a better name are welcome; r.distance was
already taken.

Unlike r.buffer, it doesn't require loading the entire
map into memory, so (in conjuction with r.recode) it may also be
useful as an alternative to r.buffer for large maps.

When I get back (in a couple of weeks) I'll give it a try to see how it does with my v.surf.icw script (IDW interp but with distance term as (AFAIU) r.grow.distance does it)

http://trac.osgeo.org/grass/browser/grass-addons/vector/v.surf.icw

thanks, it look interesting.

Hamish

3

Hamish wrote:

> I have added a new module, r.grow.distance, which generates a map
> where the value of each cell is the distance to the nearest non-null
> cell in the input map (similar to r.cost with a constant cost, except
> that you get real circles rather than approximations).

ie better than r.cost's knight's move / octagon. (?)

AFAICT, r.cost gives octagons without -k and hexadecagons (16 sides)
with -k.

Even if that's an adequate approximation, r.grow.distance is
noticeably faster, especially if the map won't fit into memory.

In the process of quantifying that, I found a bug in the way that
r.cost computes the number of segments:

    if (maxmem > 0)
  segments_in_memory =
      2 + maxmem * (nrows / SEGCOLSIZE) * (ncols / SEGCOLSIZE) / 100;
    else
  segments_in_memory = 4 * (nrows / SEGCOLSIZE + ncols / SEGCOLSIZE + 2);

Because integer division rounds down, if the map is
one-point-something segments in each direction, it allocates 2+1*1 = 3
segments for a map which really needs 4.

[With "spearfish".]

$ g.region res=45
$ time r.cost -k --o start_rast=test input=one output=test.grow
318 rows, 423 cols
real 1m18.267s
user 0m2.876s
sys 1m15.358s

78 seconds, of which 75 is spent in the kernel (i.e. swapping segments
to file). At res=30 (spearfish's default), I Ctrl-C'd it after a
couple of minutes.

OTOH, with percent_memory=0 (4*(1+1+2) = 16 segments):

$ g.region res=45
$ time r.cost -k --o start_rast=test input=one output=test.grow percent_memory=0
318 rows, 423 cols
real 0m1.518s
user 0m1.477s
sys 0m0.040s

1.5 seconds. A significant improvement over 78 seconds.

Fixed in SVN trunk (r32239).

--
Glynn Clements <glynn@gclements.plus.com>

4

On Wednesday 23 July 2008, Glynn Clements wrote:

Hamish wrote:
> > I have added a new module, r.grow.distance, which generates a map
> > where the value of each cell is the distance to the nearest non-null
> > cell in the input map (similar to r.cost with a constant cost, except
> > that you get real circles rather than approximations).
>
> ie better than r.cost's knight's move / octagon. (?)

AFAICT, r.cost gives octagons without -k and hexadecagons (16 sides)
with -k.

Even if that's an adequate approximation, r.grow.distance is
noticeably faster, especially if the map won't fit into memory.

In the process of quantifying that, I found a bug in the way that
r.cost computes the number of segments:

    if (maxmem > 0)
  segments_in_memory =
      2 + maxmem * (nrows / SEGCOLSIZE) * (ncols / SEGCOLSIZE) / 100;
    else
  segments_in_memory = 4 * (nrows / SEGCOLSIZE + ncols / SEGCOLSIZE + 2);

Because integer division rounds down, if the map is
one-point-something segments in each direction, it allocates 2+1*1 = 3
segments for a map which really needs 4.

[With "spearfish".]

$ g.region res=45
$ time r.cost -k --o start_rast=test input=one output=test.grow
318 rows, 423 cols
real 1m18.267s
user 0m2.876s
sys 1m15.358s

78 seconds, of which 75 is spent in the kernel (i.e. swapping segments
to file). At res=30 (spearfish's default), I Ctrl-C'd it after a
couple of minutes.

OTOH, with percent_memory=0 (4*(1+1+2) = 16 segments):

$ g.region res=45
$ time r.cost -k --o start_rast=test input=one output=test.grow
percent_memory=0 318 rows, 423 cols
real 0m1.518s
user 0m1.477s
sys 0m0.040s

1.5 seconds. A significant improvement over 78 seconds.

Fixed in SVN trunk (r32239).

Nice work. Is there any schedule for fixes like these to make it back to 6.4?

Thanks,

Dylan

--
Dylan Beaudette
Soil Resource Laboratory
http://casoilresource.lawr.ucdavis.edu/
University of California at Davis
530.754.7341