[GRASS-dev] nasty bug in v.what.rast (CVS ~ 2 weeks ago)

[Dylan Beaudette]

On Thursday 15 November 2007, Glynn Clements wrote:
> Dylan Beaudette wrote:
> > Sorry for the spam, it looks like the bug is related to this:
> >
> > cvs diff  -r 1.26 -r 1.27 main.c
> > Index: main.c
> > ===================================================================
> > RCS file: /home/grass/grassrepository/grass6/vector/v.what.rast/main.c,v
> > retrieving revision 1.26
> > retrieving revision 1.27
> > diff -r1.26 -r1.27
> > 221,235c221,228
> > <     i = 1;
> > <     while ( i < point_cnt ) {
> > <         if ( cache[i].cat == cache[i-1].cat ) {
> > <           cache[i-1].count++;
> > <           for ( j = i; j < point_cnt - 1; j++ ) {
> > <               cache[j].row = cache[j+1].row;
> > <               cache[j].col = cache[j+1].col;
> > <               cache[j].cat = cache[j+1].cat;
> > <               cache[j].count = cache[j+1].count;
> > <           }
> > <           point_cnt--;
> > <           continue;
> > <       }
> > <         i++;
> > <     }
> > ---
> >
> > >     for (i = j = 0; j < point_cnt; j++)
> > >         if (cache[i].cat != cache[j].cat)
> > >           cache[++i] = cache[j];
> > >         else
> > >             cache[i].count++;
> > >     point_cnt = i + 1;
> >
> > reverting to this version fixed the problem for me. I am not sure how to
> > interpret what the changes implemented from 1.26 -> 1.27 are doing,
> > although it looks like some kind of optimization. Glynn? :)
>
> Yes, it's an optimisation (from O(n^2) to O(n)), but with an
> off-by-one error which effectively duplicates the first entry.
>
> Try this:
>
> --- vector/v.what.rast/main.c	22 Oct 2007 15:23:41 -0000	1.28
> +++ vector/v.what.rast/main.c	16 Nov 2007 00:31:01 -0000
> @@ -219,7 +219,7 @@
>
>      G_debug(1, "Points are sorted, starting duplicate removal loop");
>
> -    for (i = j = 0; j < point_cnt; j++)
> +    for (i = 0, j = 1; j < point_cnt; j++)
>          if (cache[i].cat != cache[j].cat)
>  	    cache[++i] = cache[j];
>          else
>
> Oddly enough, Markus actually tested this before it was committed, but
> only for timing, not results (see "v.what.rast speedup" thread from
> around Oct 22).

that did the trick. thanks.

That GRASS test suite is looking more and more important...

Dylan

-- 
Dylan Beaudette
Soil Resource Laboratory
http://casoilresource.lawr.ucdavis.edu/
University of California at Davis
530.754.7341