[GRASS-dev] nasty bug in v.what.rast (CVS ~ 2 weeks ago)
Glynn Clements
glynn at gclements.plus.com
Thu Nov 15 19:36:28 EST 2007
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>
More information about the grass-dev
mailing list