Re: filling area by color atack safety

On Tue, 19 Mar 2024 11:57:53 +0000
Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:

 
No. Mine takes horizontal scan lines and extends them, then places
the pixels above and below in a queue to be considered as seeds for
the next scan line. (It's not mine, but I don't know who invented it.
It wasn't me.)
 
Tim, now what does it do? Essentially it's the recursive fill
algorithm but with the data only on the stack instead of the call and
the data. And todo is actually a queue rather than a stack.
 
Now why would it be slower? Probaby because you usually only hit a
pixel three times with mine - once below, once above, and once for
the scan line itself, whilst you consider it 5 times for Tim's - once
for each neighbour and once for itself. Then horizontally adjacent
pixels are more likely to be in the same cache line than vertically
adjacent pixels, so processing images in scan lines tends to be a bit
faster.
 

Below is a variant of recursive algorithm that is approximately as
fast as your code (1.25x faster for filling solid rectangle, 1.43x
slower for filling snake shape).
The code is a bit long, but I hope that the logic is still obvious and
there is no need to prove correctness.
I have a micro-optimized variant of the same algorithm that is as fast
or faster than yours in all cases that I tested, but posting
micro-optimized code on c.l.c is a bad sportsmanship.
Recursion depth of this algorithm for typical solid shape is
O(max(width,height)), but for a worst case it still very bad, about N/4.
And since there are more local variable to preserve, the worst case
size of occupied stack is likely even bigger than in simple (but
non-naive) recursion. So, while fast, I wouldn't use this algorithm in
general-purpose library.
But it can serve as a reference point for implementation with explicit
stack.


struct recursive_context_t {
 unsigned char *grey;
 int width, height;
 unsigned char target, dest;
};

static void floodfill_r_core(const struct recursive_context_t* context,
int x, int y);

int floodfill_r(
  unsigned char *grey,
  int width, int height,
  int x, int y,
  unsigned char target, unsigned char dest)
{
  if (x < 0 || x >= width || y < 0 || y >= height)
    return 0;
  if (grey[y*width+x] != target)
    return 0;
  struct recursive_context_t context = {
    .grey = grey,
    .width = width,
    .height = height,
    .target = target,
    .dest = dest,
  };
  floodfill_r_core(&context, x, y);
  return 1;
}

static void floodfill_r_core(const struct recursive_context_t* context,
int x, int y) {
  // point (x,y) is in target rectangle and has target color. It's
guaranteed by caller

  // Find maximal cross (of Saint George's variety) with target color
  and center at (x,y) // go left
  int x0;
  for (x0 = x-1; x0 >= 0              &&
  context->grey[y*context->width+x0] == context->target; --x0); ++x0;
  // go right
  int x1;
  for (x1 = x+1; x1 < context->width  &&
  context->grey[y*context->width+x1] == context->target; ++x1); // go up
  int y0;
  for (y0 = y-1; y0 >= 0              &&
  context->grey[y0*context->width+x] == context->target; --y0); ++y0;
  // go down
  int y1;
  for (y1 = y+1; y1 < context->height &&
  context->grey[y1*context->width+x] == context->target; ++y1);

  // Fill cross with destination color
  for (int i = x0; i < x1; ++i)
    context->grey[y*context->width+i] = context->dest;
  for (int i = y0; i < y1; ++i)
    context->grey[i*context->width+x] = context->dest;

  if (y > 0) { // recursion into points above horizontal line
    unsigned char *row = &context->grey[(y-1)*context->width];
    for (int i = x0; i < x1; ++i)
      if (row[i] == context->target)
        floodfill_r_core(context, i, y-1);
  }
  if (y+1 < context->height) { // recursion into points below
  horizontal line unsigned char *row =
  &context->grey[(y+1)*context->width]; for (int i = x0; i < x1; ++i)
      if (row[i] == context->target)
        floodfill_r_core(context, i, y+1);
  }
  if (x > 0) { // recursion into points left of vertical line
    unsigned char *col = &context->grey[x-1];
    for (int i = y0; i < y1; ++i)
      if (col[i*context->width] == context->target)
        floodfill_r_core(context, x-1, i);
  }
  if (x+1 < context->width) { // recursion into points right of
  vertical line unsigned char *col = &context->grey[x+1];
    for (int i = y0; i < y1; ++i)
      if (col[i*context->width] == context->target)
        floodfill_r_core(context, x+1, i);
  }
}