Added "backlink" functionality to r.walk, r.cost & r.drain

[cnielsen]

I have updated the r.walk, r.cost and r.drain modules to include "back-link raster" functionality. Currently the path created by r.drain does not necessarily take THE path through a cost surface, that the cost accumulation algorithm took to generate that cost surface. My updates add an "outdir" raster as an output from the r.drain and r.cost modules which creates a backlink raster, or a raster surface of the movements made to create the cost surface (recorded in degrees). I then modified r.drain to read this surface when it's given the "-d" flag.

I have tested it on my win32/vista build (mingw/msys), but not on linux or mac builds. Since this is my first patch, I have added extensive commenting which can probably be removed later.

[hamish]

Hi,

thanks for the patches,

some comments & cleanups:

• don't use C++ style //comments (see the SUBMITTING file)
• please run tools/grass_indent.sh on the code (see SUBMITTING...)
• comments like "//cn:added;" are redundant and should be removed. that info & source heritage is available through the SVN history, which can be annotated line by line in the viewVc web interface. a rule there is if it doesn't help explain the code, it is noise which helps clutter & obfuscate the code.
• the GRASS convention for angle is to use Cartesian theta, i.e. degrees are counted CCW from East, not compass-style CW from North. Convert with "90-angle".
• do not remove (valid) documentation from the help pages lightly, and certainly do not remove prior authors from the AUTHORS section of the help page! (I spotted Roger Miller was removed, maybe others) If you are unsure <!-- comment it out -->.

Hamish

[cnielsen]

Update: * C++ style comments removed * indent used (I think, I got a "sed: invalid option -- i" msg) * unnecessary comments removed * angles changed to CCW from East * The removal of Roger Miller was an accident caused by me overwriting r.drain's description.html with r.walk's. My apologies for not catching that before upload.

-Colin

ps. r.cost.2.patch is the same as r.cost.patch (not sure how to delete attachments)

[dylan]

r.cost.patch applies and compiles against GRASS64-SVN r34983

r.drain patch: error on applying to documentation, does not compile

(Stripping trailing CRs from patch.) patching file main.c (Stripping trailing CRs from patch.) patching file description.html Hunk #4 FAILED at 208. 1 out of 4 hunks FAILED -- saving rejects to file description.html.rej

main.c: In function â: main.c:697: error: â undeclared (first use in this function) main.c:697: error: (Each undeclared identifier is reported only once main.c:697: error: for each function it appears in.) make: *** [OBJ.i686-pc-linux-gnu/main.o] Error

r.walk.patch: applies with one error, and compiles

(Stripping trailing CRs from patch.) patching file main.c (Stripping trailing CRs from patch.) patching file description.html Hunk #4 FAILED at 149. 1 out of 4 hunks FAILED -- saving rejects to file description.html.rej (Stripping trailing CRs from patch.) patching file stash.h

[glynn]

Replying to dylan:

r.cost.patch applies and compiles against GRASS64-SVN r34983 r.drain patch: error on applying to documentation, does not compile

patching file description.html Hunk #4 FAILED at 208.

r.walk.patch: applies with one error, and compiles

patching file description.html Hunk #4 FAILED at 149.

Both of these are due to the expanded $Date$ at the bottom of the file.

main.c: In function â: main.c:697: error: â undeclared (first use in this function) main.c:697: error: (Each undeclared identifier is reported only once main.c:697: error: for each function it appears in.) make: *** [OBJ.i686-pc-linux-gnu/main.o] Error

I don't know what happened to your comment (cut/paste issue?), but this should read:

main.c: In function `drain_cost':
main.c:697: error: `dir_name' undeclared (first use in this function)

Indeed, dir_name is local to main(), so it isn't visible in drain_cost().

[dylan]

Replying to glynn:

Replying to dylan:

r.cost.patch applies and compiles against GRASS64-SVN r34983 r.drain patch: error on applying to documentation, does not compile

patching file description.html Hunk #4 FAILED at 208.

r.walk.patch: applies with one error, and compiles

patching file description.html Hunk #4 FAILED at 149.

Both of these are due to the expanded $Date$ at the bottom of the file.

main.c: In function â: main.c:697: error: â undeclared (first use in this function) main.c:697: error: (Each undeclared identifier is reported only once main.c:697: error: for each function it appears in.) make: *** [OBJ.i686-pc-linux-gnu/main.o] Error

I don't know what happened to your comment (cut/paste issue?), but this should read: {{{ main.c: In function `drain_cost': main.c:697: error: `dir_name' undeclared (first use in this function) }}} Indeed, dir_name is local to main(), so it isn't visible in drain_cost().

Right. Forgot about the verbatim formatting... I have attached a new patch against r34985 that compiles cleanly.

[dylan]

single line modification to colin's patch

[dylan]

OK Some real comments.

I have noticed that the patch r.cost gives a segmentation fault if the outdir raster is not specified. The cost surface is identical between r.cost in SVN and the patched version. The output from the patched r.drain (without the new backlink functionality) is identical to the SVN version of r.drain.

Attempting to use the outdir/indir options on r.cost/r.drain does not seem to work. I get:

 r.drain -d input=cost_new output=cost.drain_new vector_points=end indir=cost_dir --o
Directional drain selected... checking for direction raster
Direction raster found <cost_dir>
Dev note: Adapted sites library used for vector points. (module should be
updated to GRASS 6 vector library)
ERROR: Raster map (·¿Óõ·>^[[?1;2c not a direction map

Probably related to my crappy hack job getting the patched r.drain to compile.

Another thing. Patched r.cost and r.drain do not seem to be using the standard GRASS command line parser, as partial arguments such as 'in' (input) are not accepted as legal arguments.

[dylan]

One more set of comments:

1. The patched r.walk appears to have the same problem as patched r.cost-- Seg fault if the outdir option is not specified.

2. Output direction from patched r.walk is not accepted by patched 'r.drain -d'.

I have been using data on this page ( http://casoilresource.lawr.ucdavis.edu/drupal/node/544) as my test cases. The elevation surface and start/stop points are included at the bottom of the linked page.

Cheers,

Dylan

[glynn]

Replying to dylan:

Another thing. Patched r.cost and r.drain do not seem to be using the standard GRASS command line parser, as partial arguments such as 'in' (input) are not accepted as legal arguments.

The patches add options indir= and outdir=. With those options, in= and out= are no longer unique prefixes; you would need to use at least inp= and outp= to disambiguate.

[cnielsen]

Further fixes

[cnielsen]

Thanks for all the comments. I believe I have fixed all the errors mentioned above (except the description.html $date thing, I'm not sure how to fix that one).

I removed the problem in r.drain that dylan mentioned... Something is still needed there but I couldn't find a working solution. I wanted an error to come up if the user put in an invalid direction raster, but the NULL cell value was coming up as a false positive... If someone has an idea let me know.

-Colin

[cnielsen]

I have now implemented vectorization in r.drain to solve the knight's move errors discussed before. I have also adapted the patches to three different source code branches to bring my work up to date. 630rc6* = grass-6.3.0RC6 64rel* = releasebranch_6_4 6dev* = develbranch_6 Once I can get grass7 (trunk) to compile on my mingw/msys, I'll create patches for that version as well.

As far as I can tell everything works at this point, please test and let me know if there are any problems. If there are no problems, I would appreciate it if the patches could be committed. Thanks.

-Colin

[cmbarton]

Colin,

One thing I just saw in downloading these patches is that they have Windows line feeds. These need to be unix.

[cmbarton]

The r.drain patch doesn't compile. Error below

Michael

=======================

cmb-MBP-2:r.drain cmbarton$ patch -p0 < 6devdrain.patchpatching file main.c patching file description.html cmb-MBP-2:r.drain cmbarton$ make gcc -I/Users/cmbarton/grass_dev/grass6_src/dist.i386-apple-darwin9.6.0/include -arch i386 -Os -I/Library/Frameworks/GDAL.framework/Versions/1.6/Headers -DPACKAGE=\""grassmods"\" -I/Users/cmbarton/grass_dev/grass6_src/dist.i386-apple-darwin9.6.0/include -o OBJ.i386-apple-darwin9.6.0/main.o -c main.c main.c: In function ‘main’: main.c:608: error: too many arguments to function ‘Vect_build’ make: *** [OBJ.i386-apple-darwin9.6.0/main.o] Error 1 cmb-MBP-2:r.drain cmbarton$

[cmbarton]

The r.cost and r.walk patches compile fine, but I can't test until r.drain is fixed.

Michael

[neteler]

Replying to cmbarton:

The r.drain patch doesn't compile. Error below Michael ======================= cmb-MBP-2:r.drain cmbarton$ patch -p0 < 6devdrain.patchpatching file main.c patching file description.html cmb-MBP-2:r.drain cmbarton$ make gcc -I/Users/cmbarton/grass_dev/grass6_src/dist.i386-apple-darwin9.6.0/include -arch i386 -Os -I/Library/Frameworks/GDAL.framework/Versions/1.6/Headers -DPACKAGE=\""grassmods"\" -I/Users/cmbarton/grass_dev/grass6_src/dist.i386-apple-darwin9.6.0/include -o OBJ.i386-apple-darwin9.6.0/main.o -c main.c main.c: In function ‘main’: main.c:608: error: too many arguments to function ‘Vect_build’ make: *** [OBJ.i386-apple-darwin9.6.0/main.o] Error 1 cmb-MBP-2:r.drain cmbarton$

The newer prototype is (only one argument, delete the second):

int Vect_build(struct Map_info *Map)

This indicates that the patch was prepared with an older GRASS version.

Markus

[cnielsen]

Vect_build error now fixed, and all patches converted to unix line feeds.

[cnielsen]

r.cost for grass-6.3.0RC6

[cnielsen]

r.drain for grass-6.3.0RC6

[cnielsen]

r.cost for releasebranch_6_4

[cnielsen]

r.drain for releasebranch_6_4

[cnielsen]

r.walk for grass-6.3.0RC6

[cnielsen]

r.walk for releasebranch_6_4

[cnielsen]

New patches for r.walk posted which fix a bug where r.walk would crash if outdir wasn't specified. Thanks to Michael for the bug testing.

-Colin

[cmbarton]

This works very nicely in tests on Mac OSX Intel, develbranch_6.

It produces more accurate least cost paths (r.drain apparently is incorrect in some cases). It would be nice to get this into all branches ASAP to avoid errors with r.drain.

Michael

[cnielsen]

r.cost for develbranch_6

[cnielsen]

r.walk for develbranch_6

[cnielsen]

r.drain for develbranch_6

[cnielsen]

Fixed some spacing issues, patches now only contain "hunks" of genuine changes and not extra spaces.

[dylan]

Just re-compiled GRASS with Colin's recent patches to r.cost, r.drain, and r.walk. Compiles fine against develbranch_6 on linux, with visibly different results. Using the output direction update to r.cost/r.drain does not appear to differ much from the original implementation. The results from r.walk/r.drain using the output direction patch results in considerably differences-- that appear to be non-optimal in this terrain. Code and resulting output posted here:

 http://casoilresource.lawr.ucdavis.edu/drupal/node/544#comment-948

Thanks for the work on these modules. I wonder if using more than the cardinal directions would result in a more realistic "direction map".

[dylan]

Actually, after looking at the new output from r.walk/r.drain, the linearity of the shortest cost path made me think that the path was somehow non-optimal. It is actually much shorter (by 1.2km), and probably not impossible in this terrain.

[cnielsen]

Thanks for the testing and the how-to Dylan. I should emphasize that the changes I made only record the directions taken by the original cost accumulation algorithm. These means that I have not (well only a slight change to fix a mathematical error) changed how r.cost or r.walk calculates paths, only how those same paths are recorded and then turned into paths using r.drain.

The clearest way I can put it is to think of the knight's move. With the old modules, r.drain had no way to tell if the cost surface was created with or without knight's move. Instead it just followed a water drop "drain" through the map only looking at 8 neighbours. Now it uses the direction surface to remember what the cost accumulation algorithm did and recreates that path.

Therefore the cardinal directions are necessary (and precisely sufficient) since they record either eight directions, or for knight's move sixteen directions, based on the original moves... does that make sense?

Also patches for grass_trunk aka grass70 are ready for testing (they work for me).

-Colin

[cnielsen]

r.cost for grass_trunk

[cnielsen]

r.walk for grass_trunk

[cnielsen]

r.drain for grass_trunk

[cmbarton]

I've just committed the stash.h file.

Michael

[neteler]

Added to GRASS 7: r36614, r36615, r36616.

If ok, please close the ticket.

[cnielsen]

Seems ok to me.