[GRASS-dev] Re: [bug #3112] r.watershed hangs

[Hamish]

Charles Ehlschlaeger wrote:
> Thanks for posting the patch of r.watershed. That snippet of code
> ensures that colors allocated to watersheds are as different as
> possible. Back in the early '90s, we were so worried about RAM use
> that we wrote convoluted code that prevented making new arrays
> whenever possible.

IMO this is why GRASS has (in general) scaled so well for today's
massive datasets. Raster overheads are very low.


> The simpliest fix would be to insert a conditional after
> G_make_random_colors(&colors, 1, max) as shown in the patch below (two
> lines added).

thanks, applied to the 6.2 & 6.3(HEAD) branches.

Also took the opportunity to slop on lots of metadata in the output
maps (6.3cvs only).


> From a visualization perspective, 1000 basins are too
> many basins to matter anyway, so 1000 might be good. If you look at
> the experiment you performed, you can see 10000 basins took 3 minutes
> to run.

I went with 10000.


> The best fix would be to write an algorithm that chooses category
> color based on adjacent cell values. Here is a psuedo code solution:
>
> random_colors( Raster map, Color[] colors) {
>     long adjacentColors[][] = new long[ colors.length][];
>     for( int r = 0; r < map.rows(); r++) {
>        for( int c = 0; c < map.cols(); c++) {
>           long cellValue = map.getValue( r, c);
>           if( c < map.cols() - 1) {
>              if( map.getValue( r, c + 1) < cellValue) {
>                 // add map.getValue( r, c + 1) to adjacentColors[
> cellValue][] if not already in array
>              }
>           }
>           if( r < map.rows() - 1) {
>              if( map.getValue( r + 1, c ) < cellValue) {
>                 // add map.getValue( r + 1, c) to adjacentColors[
> cellValue][] if not already in array
>              }
>           }
>           if( (r < map.rows() - 1) && c < map.cols() - 1) {
>              if( map.getValue( r + 1, c + 1 ) < cellValue) {
>                 // add map.getValue( r + 1, c + 1) to adjacentColors[
> cellValue][] if not already in array
>              }
>           }
>        }
>     }
>     for( int i = 0; i < colors.length; i++) {
>        // if no adjacentColors[i] == null, give any random color
>        // otherwise randomly create 100 colors
>        // choose color furthest from colors of adjacentColors[i] array
>        
>     }
> }


The random case doesn't do too poorly. (256^3 color possibilities vs.
the four-color theorem)

> // choose color furthest from colors of adjacentColors[i] array

color distance in 3D RGB space isn't something I understand how to do
well. (I've wondered for a while how to find the "opposite" RGB color:
think of it as a vector ray from the origin inside a 3D sphere?)

Anyway, I'll have to leave the "better way" for someone who understands
color-space a bit better than I do.


thanks,
Hamish