[rt #103786] prevent fills crossing 4-connected boundaries

fixed an off-by-one error inherited from the original pseudo-code

diff --git a/draw.c b/draw.c
index 9103c78ef8dfc2a31a9be32e976cb907231108d2..e66af53123393445e24c62771f46ff13a44891b3 100644 (file)
--- a/draw.c
+++ b/draw.c
@@ -1760,10 +1760,36 @@ i_rspan(i_img *im, i_img_dim seedx, i_img_dim seedy, i_color const *val, ff_cmpf
   return seedx;
 }
 
+#ifdef DEBUG_FLOOD_FILL
+
+#define ST_PUSH_NOTE(left, right, dadl, dadr, y, dir) \
+  fprintf(stderr, "push(left %" i_DF ", right %" i_DF ", dadleft %" i_DF  ", dadright %" i_DF ", y %" i_DF ", dir %d, line %d)\n", \
+         i_DFc(left), i_DFc(right), i_DFc(dadl), i_DFc(dadr), i_DFc(y), (dir), __LINE__)
+
+#define ST_POP_NOTE(left, right, dadl, dadr, y, dir) \
+  fprintf(stderr, "popped(left %" i_DF ", right %" i_DF ", dadleft %" i_DF  ", dadright %" i_DF ", y %" i_DF ", dir %d, line %d)\n", \
+         i_DFc(left), i_DFc(right), i_DFc(dadl), i_DFc(dadr), i_DFc(y), (dir), __LINE__)
+
+#define ST_STACK_NOTE(dadl, dadr, left, right, y, dir)                 \
+  fprintf(stderr, "stack(left %" i_DF ", right %" i_DF ", dadleft %" i_DF  ", dadright %" i_DF ", y %" i_DF ", dir %d, line %d)\n", \
+         i_DFc(left), i_DFc(right), i_DFc(dadl), i_DFc(dadr), i_DFc(y), (dir), __LINE__)
+
+#else
+
+#define ST_PUSH_NOTE(left, right, dadl, dadr, y, dir)
+
+#define ST_POP_NOTE(left, right, dadl, dadr, y, dir)
+
+#define ST_STACK_NOTE(dadl, dadr, left, right, y, dir)
+
+#endif
+
+
 /* Macro to create a link and push on to the list */
 
 #define ST_PUSH(left,right,dadl,dadr,y,dir) do {                 \
   struct stack_element *s = crdata(left,right,dadl,dadr,y,dir);  \
+  ST_PUSH_NOTE(left, right, dadl, dadr, y, dir);                \
   llist_push(st,&s);                                             \
 } while (0)
 
@@ -1779,24 +1805,28 @@ i_rspan(i_img *im, i_img_dim seedx, i_img_dim seedy, i_color const *val, ff_cmpf
   dadRx     = s->dadRx;       \
   y         = s->myY;         \
   direction = s->myDirection; \
+  ST_POP_NOTE(lx, rx, dadLx, dadRx, y, direction);     \
   myfree(s);                  \
 } while (0)
 
 #define ST_STACK(dir,dadLx,dadRx,lx,rx,y) do {                    \
   i_img_dim pushrx = rx+1;                                              \
   i_img_dim pushlx = lx-1;                                              \
+  ST_STACK_NOTE(lx, rx, dadLx, dadRx, y, dir);          \
   ST_PUSH(lx,rx,pushlx,pushrx,y+dir,dir);                         \
   if (rx > dadRx)                                                 \
     ST_PUSH(dadRx+1,rx,pushlx,pushrx,y-dir,-dir);                 \
-  if (lx < dadLx) ST_PUSH(lx,dadLx-1,pushlx,pushrx,y-dir,-dir);   \
+  if (lx < dadLx)                                              \
+    ST_PUSH(lx,dadLx-1,pushlx,pushrx,y-dir,-dir);   \
 } while (0)
 
 #define SET(x,y) btm_set(btm,x,y)
 
 /* INSIDE returns true if pixel is correct color and we haven't set it before. */
-#define INSIDE(x,y, seed) ((!btm_test(btm,x,y) && ( i_gpix(im,x,y,&cval),cmpfunc(seed,&cval,channels)  ) ))
-
-
+#define INSIDE(x,y, seed) \
+  (assert((x) >= 0 && (x) < (im)->xsize && (y) >= 0 && (y) < (im)->ysize), \
+   (!btm_test(btm,x,y) && \
+     ( i_gpix(im,x,y,&cval),cmpfunc(seed,&cval,channels)  ) ))
 
 /* The function that does all the real work */
 
@@ -1817,7 +1847,7 @@ i_flood_fill_low(i_img *im,i_img_dim seedx,i_img_dim seedy,
 
   int channels;
   i_img_dim xsize,ysize;
-  i_color cval;
+  i_color cval; /* used by the INSIDE() macro */
 
   channels = im->channels;
   xsize    = im->xsize;
@@ -1862,6 +1892,8 @@ i_flood_fill_low(i_img *im,i_img_dim seedx,i_img_dim seedy,
        SET(lx,y);
        lx--;
       }
+      /* lx should point at the left-most INSIDE() pixel */
+      ++lx;
     }
 
     if (bxmin > lx) bxmin = lx;

diff --git a/t/250-draw/020-flood.t b/t/250-draw/020-flood.t
index 767cbab85bb075e65214d478c5cd39144c859ee3..fce20191b6d600eeaeb97dde20f4e31bed330716 100644 (file)
--- a/t/250-draw/020-flood.t
+++ b/t/250-draw/020-flood.t
@@ -1,6 +1,6 @@
 #!perl -w
 use strict;
-use Test::More tests => 15;
+use Test::More tests => 17;
 use Imager;
 use Imager::Test qw(is_image);
 
@@ -52,6 +52,19 @@ SKIP:
   is_image($im, $cmp, "check the result");
 }
 
+{
+  # 103786 - when filling up would cross a 4-connected border to the left
+  # incorrectly
+  my $im = Imager->new(xsize => 20, ysize => 20);
+  $im->box(filled => 1, box => [ 0, 10, 9, 19 ], color => "FFFFFF");
+  $im->box(filled => 1, box => [ 10, 0, 19, 9 ], color => "FFFFFF");
+  my $cmp = $im->copy;
+  $cmp->box(filled => 1, box => [ 10, 10, 19, 19 ], color => "0000FF");
+  ok($im->flood_fill(x => 19, y => 19, color => "0000FF"),
+     "flood_fill() to big checks");
+  is_image($im, $cmp, "check result correct");
+}
+
 unless ($ENV{IMAGER_KEEP_FILES}) {
   unlink "testout/t22fill1.ppm";
   unlink "testout/t22fill2.ppm";