Opened 11 years ago

Closed 11 years ago

#399 closed enhancement (fixed)

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

Reported by: cnielsen Owned by: grass-dev@…
Priority: major Milestone: 6.4.0
Component: Raster Version: unspecified
Keywords: Cc: michael.barton@…
CPU: All Platform: All

Description

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.

Attachments (20)

r.walk.patch (18.8 KB) - added by cnielsen 11 years ago.
r.cost.2.patch (16.9 KB) - added by cnielsen 11 years ago.
r.cost.patch (16.9 KB) - added by cnielsen 11 years ago.
r.drain.patch (12.4 KB) - added by cnielsen 11 years ago.
r.drain.patch_2 (9.5 KB) - added by dylan 11 years ago.
single line modification to colin's patch
r.costv2.patch (19.4 KB) - added by cnielsen 11 years ago.
Further fixes
r.walkv2.patch (21.5 KB) - added by cnielsen 11 years ago.
r.drainv2.patch (13.2 KB) - added by cnielsen 11 years ago.
630rc6.cost.patch (40.1 KB) - added by cnielsen 11 years ago.
r.cost for grass-6.3.0RC6
630rc6drain.patch (19.0 KB) - added by cnielsen 11 years ago.
r.drain for grass-6.3.0RC6
64relcost.patch (17.2 KB) - added by cnielsen 11 years ago.
r.cost for releasebranch_6_4
64reldrain.patch (14.3 KB) - added by cnielsen 11 years ago.
r.drain for releasebranch_6_4
630rc6walk.patch (37.9 KB) - added by cnielsen 11 years ago.
r.walk for grass-6.3.0RC6
64relwalk.patch (19.8 KB) - added by cnielsen 11 years ago.
r.walk for releasebranch_6_4
6devcost.patch (17.4 KB) - added by cnielsen 11 years ago.
r.cost for develbranch_6
6devwalk.patch (18.6 KB) - added by cnielsen 11 years ago.
r.walk for develbranch_6
6devdrain.patch (14.3 KB) - added by cnielsen 11 years ago.
r.drain for develbranch_6
7cost.patch (16.9 KB) - added by cnielsen 11 years ago.
r.cost for grass_trunk
7walk.patch (18.2 KB) - added by cnielsen 11 years ago.
r.walk for grass_trunk
7drain.patch (13.7 KB) - added by cnielsen 11 years ago.
r.drain for grass_trunk

Download all attachments as: .zip

Change History (44)

comment:1 Changed 11 years ago by hamish

Type: defectenhancement

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

comment:2 Changed 11 years ago by 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)

Changed 11 years ago by cnielsen

Attachment: r.walk.patch added

Changed 11 years ago by cnielsen

Attachment: r.cost.2.patch added

Changed 11 years ago by cnielsen

Attachment: r.cost.patch added

Changed 11 years ago by cnielsen

Attachment: r.drain.patch added

comment:3 Changed 11 years ago by 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

comment:4 in reply to:  3 ; Changed 11 years ago by 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().

comment:5 in reply to:  4 Changed 11 years ago by 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.

Changed 11 years ago by dylan

Attachment: r.drain.patch_2 added

single line modification to colin's patch

comment:6 Changed 11 years ago by 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.

comment:7 Changed 11 years ago by 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.
  1. 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

comment:8 in reply to:  6 Changed 11 years ago by 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.

Changed 11 years ago by cnielsen

Attachment: r.costv2.patch added

Further fixes

Changed 11 years ago by cnielsen

Attachment: r.walkv2.patch added

Changed 11 years ago by cnielsen

Attachment: r.drainv2.patch added

comment:9 Changed 11 years ago by 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

comment:10 Changed 11 years ago by cnielsen

Cc: michael.barton@… added

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

comment:11 Changed 11 years ago by cmbarton

Colin,

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

comment:12 Changed 11 years ago by 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$

comment:13 Changed 11 years ago by cmbarton

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

Michael

comment:14 in reply to:  12 Changed 11 years ago by 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

comment:15 Changed 11 years ago by cnielsen

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

Changed 11 years ago by cnielsen

Attachment: 630rc6.cost.patch added

r.cost for grass-6.3.0RC6

Changed 11 years ago by cnielsen

Attachment: 630rc6drain.patch added

r.drain for grass-6.3.0RC6

Changed 11 years ago by cnielsen

Attachment: 64relcost.patch added

r.cost for releasebranch_6_4

Changed 11 years ago by cnielsen

Attachment: 64reldrain.patch added

r.drain for releasebranch_6_4

Changed 11 years ago by cnielsen

Attachment: 630rc6walk.patch added

r.walk for grass-6.3.0RC6

Changed 11 years ago by cnielsen

Attachment: 64relwalk.patch added

r.walk for releasebranch_6_4

comment:16 Changed 11 years ago by 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

comment:17 Changed 11 years ago by 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

Changed 11 years ago by cnielsen

Attachment: 6devcost.patch added

r.cost for develbranch_6

Changed 11 years ago by cnielsen

Attachment: 6devwalk.patch added

r.walk for develbranch_6

Changed 11 years ago by cnielsen

Attachment: 6devdrain.patch added

r.drain for develbranch_6

comment:18 Changed 11 years ago by cnielsen

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

comment:19 Changed 11 years ago by 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".

comment:20 Changed 11 years ago by 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.

comment:21 Changed 11 years ago by 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

Changed 11 years ago by cnielsen

Attachment: 7cost.patch added

r.cost for grass_trunk

Changed 11 years ago by cnielsen

Attachment: 7walk.patch added

r.walk for grass_trunk

Changed 11 years ago by cnielsen

Attachment: 7drain.patch added

r.drain for grass_trunk

comment:22 Changed 11 years ago by cmbarton

I've just committed the stash.h file.

Michael

comment:23 Changed 11 years ago by neteler

Added to GRASS 7: r36614, r36615, r36616.

If ok, please close the ticket.

comment:24 Changed 11 years ago by cnielsen

Resolution: fixed
Status: newclosed

Seems ok to me.

Note: See TracTickets for help on using tickets.