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

[Dylan Beaudette]

On Wednesday 25 October 2006 22:59, Hamish wrote:
> 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
>

I don't have anything constructive to add to this thread other than - This 
small transaction between various parties, referencing events from the 90's, 
dealing with current bugs, the speed in which a fix was suggested and the 
speed in which it was committed to CVS astounds me! 

This would be a great bit of text to bring up in a presentation on GRASS and 
the FOSS concept of software development.

Great job everyone!

Dylan

-- 
Dylan Beaudette
Soils and Biogeochemistry Graduate Group
University of California at Davis
530.754.7341