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

[Glynn Clements]

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).

-- 
Glynn Clements <glynn at gclements.plus.com>