[GRASS-dev] Re: r.walk, r.cost & r.drain patches posted

GRASS GRASS developer
,
1

On Dec 22, 2008, at 2:33 PM, Colin Nielsen wrote:

I have fixed that and other errors reported by Dylan. New patches are
available on ticket #399.

Thanks.
-Colin

On Sat, Dec 20, 2008 at 11:47 AM, Michael Barton <michael.barton@asu.edu> wrote:

Colin,

I applied your patches. Those for r.cost and r.walk went OK. The one for
r.drain did not compile. Here is the error:

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 'drain_cost':
main.c:697: error: 'dir_name' 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.i386-apple-darwin9.6.0/main.o] Error 1

Michael
____________________
C. Michael Barton, Professor of Anthropology
Director of Graduate Studies
School of Human Evolution & Social Change
Center for Social Dynamics & Complexity
Arizona State University

Phone: 480-965-6262
Fax: 480-965-7671
www: <www.public.asu.edu/~cmbarton>

On Dec 15, 2008, at 1:20 PM, Colin Nielsen wrote:

As the two people who have expressed the most interest in these
modules, I thought I would let you know that I have opened a ticket
and attached patches with my code updates
(#399 (Added "backlink" functionality to r.walk, r.cost & r.drain) – GRASS GIS). When either of you has the
chance, I'm looking forward to hearing about your tests of them.
Thanks.

-Colin

Colin,

I tested your new patches to r.cost, r.walk, and r.drain using elevation.dem from Spearfish and some of the archsites as starting points. In spite of the patch errors, all ran fine.

It seemed like all ran faster, but maybe that was my imagination. The backlinked and non-backlinked paths made on a cost surface from running r.cost on a slope map are very similar to each other.

The backlinked and non-backlinked paths made on a cost surface using r.walk are very different from each other, though the non-backlinked path on an r.walk surface was very similar to the backlinked and non-backlinked paths on an r.cost surface. The backlinked path looked a little odd, transecting rugged terrain in almost a straight line. In fact the backlinked paths from r.walk are nearly straight lines. Is this a reasonable result?

One fairly serious problem is that the backlinked paths are discontinuous, with lots of gaps; the non-backlinked paths are continuous without gaps.

I've posted screenshots of the tests at: http://www.public.asu.edu/~cmbarton/files/grass_cost/

Thanks for working on these modules.

Michael

2

Hello again,
Thanks for testing the modules. Apparently, the errors are only
related to the date stamp at the bottom of the manual pages and
therefore aren't affecting the functioning of the module.

It seemed like all ran faster, but maybe that was my imagination. The
backlinked and non-backlinked paths made on a cost surface from running
r.cost on a slope map are very similar to each other.

I'm surprised it ran faster, since it is actually doing more in the
new versions. However, to a certain extent the speed depends on the
paths that it finds so I think a straighter path would be calculated
faster than one with lots of curves.

The backlinked and non-backlinked paths made on a cost surface using r.walk
are very different from each other, though the non-backlinked path on an
r.walk surface was very similar to the backlinked and non-backlinked paths
on an r.cost surface. The backlinked path looked a little odd, transecting
rugged terrain in almost a straight line. In fact the backlinked paths from
r.walk are nearly straight lines. Is this a reasonable result?

The path in the middle of your r.walk backlink map seems to cross
rugged terrain but the ones in the the NW and SE corners seems to be
traversing slopes quite well. I should emphasize that the added
functionality does not alter the way the cost algorithm calculates
paths, rather it only makes sure that the path is accurately recorded.

One fairly serious problem is that the backlinked paths are discontinuous,
with lots of gaps; the non-backlinked paths are continuous without gaps.

I assume you used the "knight's move" option? I agree the
discontinuous paths may cause some problems, especially when trying to
vectorize the paths. However, the gaps are legitimate in the sense
that they were created by the knight's move which makes small jumps
for the sake of more accurate directionality (you can see this if you
look closely at drain_backlinkvsnobacklink.png). Unlike the old
r.drain function, the updated r.drain only draws the cells actually
used in the cost algorithm.

I'm not sure how we can overcome the vectorization problem though,
especially since you need vectorization to determine the overall
distance traveled.

I've posted screenshots of the tests at:
http://www.public.asu.edu/~cmbarton/files/grass_cost/

Thanks for the tests and the screenshots.

-Colin

3

On Jan 6, 2009, at 4:03 PM, Colin Nielsen wrote:

One fairly serious problem is that the backlinked paths are discontinuous,
with lots of gaps; the non-backlinked paths are continuous without gaps.

I assume you used the "knight's move" option? I agree the
discontinuous paths may cause some problems, especially when trying to
vectorize the paths. However, the gaps are legitimate in the sense
that they were created by the knight's move which makes small jumps
for the sake of more accurate directionality (you can see this if you
look closely at drain_backlinkvsnobacklink.png). Unlike the old
r.drain function, the updated r.drain only draws the cells actually
used in the cost algorithm.

I'm not sure how we can overcome the vectorization problem though,
especially since you need vectorization to determine the overall
distance traveled.

I've posted screenshots of the tests at:
http://www.public.asu.edu/~cmbarton/files/grass_cost/

Thanks for the tests and the screenshots.

-Colin

Hi Colin,

Thanks for the updates. I'll give them a try. While I understand the reason for the gaps in the paths now, I think that it is important to find some way to get rid of them. That is, there needs to be some algorithm that will 'connect the dots' of knights move jumps. These are supposed to be paths traversing a landscape. Even without vectorizing, the cell accumulation values will be inaccurate if cells are skipped in a path from point A to point B.

Michael

4

Thanks for the updates. I'll give them a try. While I understand the reason
for the gaps in the paths now, I think that it is important to find some way
to get rid of them. That is, there needs to be some algorithm that will
'connect the dots' of knights move jumps.

I certainly agree but it should be done without adding cells in
between. The knight's moves should be retained in the output. We need
some kind of vectorization algorithm which connects cell center to
cell center, or which joins all the little line segments that would be
produced by a discontinuous path.

Even without vectorizing, the cell accumulation
values will be inaccurate if cells are skipped in a path from point A to
point B.

The algorithm accounts for the accumulation value in these larger
jumps using pythagoras. Just as diagonals are multiplied by ~1.4,
knight's move jumps are multiplied by ~2.2 (but depending on the
resolution, etc.).

-Colin

5

Maybe what is needed is a built in vectorization algorithm that will transform the paths to vectors is a flag is set.

Michael
____________________
C. Michael Barton, Professor of Anthropology
Director of Graduate Studies
School of Human Evolution & Social Change
Center for Social Dynamics & Complexity
Arizona State University

Phone: 480-965-6262
Fax: 480-965-7671
www: <www.public.asu.edu/~cmbarton>

On Jan 7, 2009, at 9:32 AM, Colin Nielsen wrote:

Thanks for the updates. I'll give them a try. While I understand the reason
for the gaps in the paths now, I think that it is important to find some way
to get rid of them. That is, there needs to be some algorithm that will
'connect the dots' of knights move jumps.

I certainly agree but it should be done without adding cells in
between. The knight's moves should be retained in the output. We need
some kind of vectorization algorithm which connects cell center to
cell center, or which joins all the little line segments that would be
produced by a discontinuous path.

Even without vectorizing, the cell accumulation
values will be inaccurate if cells are skipped in a path from point A to
point B.

The algorithm accounts for the accumulation value in these larger
jumps using pythagoras. Just as diagonals are multiplied by ~1.4,
knight's move jumps are multiplied by ~2.2 (but depending on the
resolution, etc.).

-Colin

6

I agree that since vectorization is needed, something built-in is
required. I think it would require one of the following:

a) borrow sections of code from r.to.vect to add a new section to
r.drain (not optimal since it's duplicating code)

b) alter r.to.vect to include a "-k knight's move input" flag and
ability to read a this type of path (with converging or nearly
parallel paths I can see the errors already)... on second though
having r.to.vect read the direction raster would be less error prone
than reading the path since by definition the paths are already
connected. But this isn't optimal either since it's adding very
specific functionality to a module meant for generic functionality.

c) have r.drain generate an ascii file to be read back in by
v.in.ascii which could be called by r.drain itself (probably the
easiest solution, but not particularly eloquent).

Other ideas? Suggestions?

-Colin

On Mon, Jan 12, 2009 at 4:49 PM, Michael Barton <michael.barton@asu.edu> wrote:

Maybe what is needed is a built in vectorization algorithm that will
transform the paths to vectors is a flag is set.

Michael
____________________
C. Michael Barton, Professor of Anthropology
Director of Graduate Studies
School of Human Evolution & Social Change
Center for Social Dynamics & Complexity
Arizona State University

Phone: 480-965-6262
Fax: 480-965-7671
www: <www.public.asu.edu/~cmbarton>

On Jan 7, 2009, at 9:32 AM, Colin Nielsen wrote:

Thanks for the updates. I'll give them a try. While I understand the
reason
for the gaps in the paths now, I think that it is important to find some
way
to get rid of them. That is, there needs to be some algorithm that will
'connect the dots' of knights move jumps.

I certainly agree but it should be done without adding cells in
between. The knight's moves should be retained in the output. We need
some kind of vectorization algorithm which connects cell center to
cell center, or which joins all the little line segments that would be
produced by a discontinuous path.

Even without vectorizing, the cell accumulation
values will be inaccurate if cells are skipped in a path from point A to
point B.

The algorithm accounts for the accumulation value in these larger
jumps using pythagoras. Just as diagonals are multiplied by ~1.4,
knight's move jumps are multiplied by ~2.2 (but depending on the
resolution, etc.).

-Colin

7

I'd first say that probably a) or c) is the best. But b) is intriguing, however. Thinking about it, it's not all that specific. It currently handles several different kinds of rasters, blocks of cells, scattered individual cells, and linear arrays of cells. This woulc simply be adding another kind of raster configuration to read from.

Michael
______________________________
C. Michael Barton, Professor of Anthropology
Director of Graduate Studies
School of Human Evolution & Social Change
Center for Social Dynamics & Complexity
Arizona State University
Tempe, AZ 85287-2402
USA

voice: 480-965-6262; fax: 480-965-7671
www: http://www.public.asu.edu/~cmbarton

On Jan 14, 2009, at 10:36 AM, Colin Nielsen wrote:

I agree that since vectorization is needed, something built-in is
required. I think it would require one of the following:

a) borrow sections of code from r.to.vect to add a new section to
r.drain (not optimal since it's duplicating code)

b) alter r.to.vect to include a "-k knight's move input" flag and
ability to read a this type of path (with converging or nearly
parallel paths I can see the errors already)... on second though
having r.to.vect read the direction raster would be less error prone
than reading the path since by definition the paths are already
connected. But this isn't optimal either since it's adding very
specific functionality to a module meant for generic functionality.

c) have r.drain generate an ascii file to be read back in by
v.in.ascii which could be called by r.drain itself (probably the
easiest solution, but not particularly eloquent).

Other ideas? Suggestions?

-Colin

On Mon, Jan 12, 2009 at 4:49 PM, Michael Barton <michael.barton@asu.edu> wrote:

Maybe what is needed is a built in vectorization algorithm that will
transform the paths to vectors is a flag is set.

Michael
____________________
C. Michael Barton, Professor of Anthropology
Director of Graduate Studies
School of Human Evolution & Social Change
Center for Social Dynamics & Complexity
Arizona State University

Phone: 480-965-6262
Fax: 480-965-7671
www: <www.public.asu.edu/~cmbarton>

On Jan 7, 2009, at 9:32 AM, Colin Nielsen wrote:

Thanks for the updates. I'll give them a try. While I understand the
reason
for the gaps in the paths now, I think that it is important to find some
way
to get rid of them. That is, there needs to be some algorithm that will
'connect the dots' of knights move jumps.

I certainly agree but it should be done without adding cells in
between. The knight's moves should be retained in the output. We need
some kind of vectorization algorithm which connects cell center to
cell center, or which joins all the little line segments that would be
produced by a discontinuous path.

Even without vectorizing, the cell accumulation
values will be inaccurate if cells are skipped in a path from point A to
point B.

The algorithm accounts for the accumulation value in these larger
jumps using pythagoras. Just as diagonals are multiplied by ~1.4,
knight's move jumps are multiplied by ~2.2 (but depending on the
resolution, etc.).

-Colin