Re: filling area by color atack safety

On Sat, 30 Mar 2024 00:54:19 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

Michael S <already5chosen@yahoo.com> writes:
 
[...]
 

The most robust code that I found so far that performs well both
with small pictures and with large and huge, is a variation on the
same theme of explicit stack, may be, more properly called trace
back.  It operates on 2x2 squares instead of individual pixels.
>
The worst case auxiliary memory footprint of this variant is rather
big, up to picture_size/4 bytes.  The code is *not* simple, but
complexity appears to be necessary for robust performance with
various shapes and sizes.
>
[...] 

 
I took a cursory look just now, after reading your other later
posting.  I think I have a general sense, especially in conjunction
with the explanatory comments.
 
I'm still hoping to find a method that is both fast and has
good memory use, which is to say O(N) for an NxN pixel field.
 
Something that would help is to have a library of test cases,
by which I mean patterns to be colored, so that a set of
methods could be tried, and timed, over all the patterns in
the library.  Do you have something like that?  So far all
my testing has been ad hoc.
>

I am not 100% sure about the meaning of 'ad hoc', but I'd guess that
mine are ad hoc too. Below are shapes that I use apart from solid
rectangles. I run them at 5 sizes: 25x19, 200x200, 1280x720, 1920x1080,
3840x2160. That is certainly not enough for correction tests, but feel
that it is sufficient for speed tests.

static void make_standing_snake(
  unsigned char *image,
  int width, int height,
  unsigned char background_c,
  unsigned char pen_c)
{
  for (int y = 0; y < height; ++y) {
    unsigned char* p = &image[y*width];
    if (y % 2 == 0) {
      memset(p, pen_c, width);
    } else {
      memset(p, background_c, width);
      if (y % 4 == 1)
        p[width-1] = pen_c;
      else
        p[0] = pen_c;
    }
  }
}

static void make_prostrate_snake(
  unsigned char *image,
  int width, int height,
  unsigned char background_c,
  unsigned char pen_c)
{
  memset(image, background_c, sizeof(*image)*width*height);
  // vertical bars
  for (int y = 0; y < height; ++y)
    for (int x = 0; x < width; x += 2)
      image[y*width+x] = pen_c;

  // connect bars at top
  for (int x = 3; x < width; x += 4)
    image[x] = pen_c;

  // connect bars at bottom
  for (int x = 1; x < width; x += 4)
    image[(height-1)*width+x] = pen_c;
}


static void make_slalom(
  unsigned char *image,
  int width, int height,
  unsigned char background_c,
  unsigned char pen_c)
{
  const int n_col = width/3;
  const int n_row = (height-3)/4;

  // top row
  // P B B P P P
  for (int col = 0; col < n_col; ++col) {
    unsigned char c = (col & 1)==0 ? background_c : pen_c;
    image[col*3] = pen_c; image[col*3+1] = c; image[col*3+2] = c;
  }
  for (int x = n_col*3; x < width; ++x)
    image[x] = image[n_col*3-1];

  // main image: consists of 3x4 blocks filled by following pattern
  //  P B B
  //  P P B
  //  B P B
  //  P P B
  for (int row = 0; row < n_row; ++row) {
    for (int col = 0; col < n_col; ++col) {
      unsigned char* p = &image[(row*4+1)*width+col*3];
      p[0] = pen_c;        p[1] = background_c; p[2] = background_c; p
  += width; p[0] = pen_c;        p[1] = pen_c;        p[2] =
  background_c; p += width; p[0] = background_c; p[1] = pen_c;
  p[2] = background_c; p += width; p[0] = pen_c;        p[1] = pen_c;
       p[2] = background_c; p += width; }
  }

  // near-bottom rows
  // P B B
  for (int y = n_row*4+1; y < height-1; ++y) {
    for (int col = 0; col < n_col; ++col) {
      unsigned char* p = &image[y*width+col*3];
      p[0] = pen_c;        p[1] = background_c; p[2] = background_c;
    }
  }

  // bottom row - all P
  // P P P P B B
  unsigned char *b_row = &image[width*(height-1)];
  for (int col = 0; col < n_col; ++col) {
    unsigned char c = (col & 1)==1 ? background_c : pen_c;
    b_row[col*3+0] = pen_c;
    b_row[col*3+1] = c;
    b_row[col*3+2] = c;
  }
  for (int x = n_col*3; x < width; ++x)
    b_row[x] = b_row[n_col*3-1];

  // rightmost columns
  for (int x = n_col*3; x < width; ++x) {
    for (int y = 1; y < height-1; ++y)
      image[y*width+x] = background_c;
  }
}

static void make_slalom90(
  unsigned char *image,
  int width, int height,
  unsigned char background_c,
  unsigned char pen_c)
{
  const int n_col = (width-3)/4;
  const int n_row = height/3;

  // leftmost column
  // P
  // B
  // B
  // P
  // P
  // P
  for (int row = 0; row < n_row; ++row) {
    unsigned char c = (row & 1)==0 ? background_c : pen_c;
    image[(row*3+0)*width] = pen_c;
    image[(row*3+1)*width] = c;
    image[(row*3+2)*width] = c;
  }
  for (int y = n_row*3; y < height; ++y)
    image[y*width] = image[(n_row*3-1)*width];

  // main image: consists of 4x3 blocks filled by following pattern
  //  P P B P
  //  B P P P
  //  B B B B
  for (int row = 0; row < n_row; ++row) {
    for (int col = 0; col < n_col; ++col) {
      unsigned char* p = &image[(row*3*width)+(col*4+1)];
      p[0] = pen_c;        p[1] = pen_c;        p[2] = background_c;
  p[3] = pen_c; p += width; p[0] = background_c; p[1] = pen_c;
  p[2] = pen_c;        p[3] = pen_c; p += width; p[0] = background_c;
  p[1] = background_c; p[2] = background_c; p[3] = background_c; }
  }

  // near-rightmost column
  // P
  // B
  // B
  for (int row = 0; row < n_row; ++row) {
    for (int x = n_col*4+1; x < width-1; ++x) {
      unsigned char* p = &image[row*width*3+x];
      p[0*width] = pen_c;
      p[1*width] = background_c;
      p[2*width] = background_c;
    }
  }

  // rightmost column
  // P
  // P
  // P
  // P
  // B
  // B
  unsigned char *r_col = &image[width-1];
  for (int row = 0; row < n_row; ++row) {
    unsigned char c = (row & 1)==1 ? background_c : pen_c;
    r_col[(row*3+0)*width] = pen_c;
    r_col[(row*3+1)*width] = c;
    r_col[(row*3+2)*width] = c;
  }
  for (int y = n_row*3; y < height; ++y)
    r_col[y*width] = r_col[(n_row*3-1)*width];

  // bottom rows
  for (int y = n_row*3; y < height; ++y) {
    for (int x = 1; x < width-1; ++x)
      image[y*width+x] = background_c;
  }
}

static void make_crosss_in_cross(
  unsigned char* image,
  int            width,
  int            height,
  int            xc,
  int            yc,
  unsigned char  background_c,
  unsigned char  pen_c)
{
  memset(image, pen_c, width*height);

  if (xc > 1 && xc+1 < width-1 && yc > 1 && yc+1 < height-1) {
    memset(&image[(yc-1)*width+1], background_c, xc-1);
    memset(&image[(yc+1)*width+1], background_c, xc-1);
    memset(&image[(yc-1)*width+xc+1], background_c, width-xc-2);
    memset(&image[(yc+1)*width+xc+1], background_c, width-xc-2);
    for (int y = 1; y < yc; ++y) {
      image[y*width+xc-1] = background_c;
      image[y*width+xc+1] = background_c;
    }
    for (int y = yc+1; y < height-1; ++y) {
      image[y*width+xc-1] = background_c;
      image[y*width+xc+1] = background_c;
    }
  }
}

Incidentally, it looks like your code assumes X varies more rapidly
than Y, so a "by row" order, whereas my code assumes Y varies more
rapidly than X, a "by column" order.

It is not so much about what I assume as about what is cheaper for
CPU hardware.

The difference doesn't matter
as long as the pixel field is square and the test cases either are
symmetric about the X == Y axis or duplicate a non-symmetric pattern
about the X == Y axis.  I would like to be able to run comparisons
between different methods and get usable results without having
to jump around because of different orientations.  I'm not sure
how to accommodate that.