Re: filling area by color atack safety

On Fri, 22 Mar 2024 17:55:26 +0300
Michael S <already5chosen@yahoo.com> wrote:

On Fri, 22 Mar 2024 13:04:39 +1100
Peter 'Shaggy' Haywood <phaywood@alphalink.com.au> wrote:
 

 
  To use this, simply call floodfill() passing the coordinates of
the starting point for the fill (y and x) and the fill colour
(new_clr).

 
It looks like anisotropic variant of my St. George Cross algorithm.
Or like recursive variant of Malcolm's algorithm.
Being anisotropic, it has higher amount of glass jaws. In particular,
it would be very slow for not uncommon 'jail window' patterns.
* *** *** *** ***
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
*** *** *** *** *
 
Also, implementation is still recursive and the worst-case recursion
depth is still O(N), where N is total number of recolored pixels, so
unlike many other solutions presented here, you didn't solve fir's
original problem.
And in presented form it's not thread-safe. Which is not a problem for
fir, but nonn-desirable for the rest of us.
 
Conclusion: sorry, you aren't going to get a cookie for your effort.
 

So, what is my own practical answer?
Assuming that speed is not a top priority and that simplicity
is pretty high on priority scale and that it should work with big
images and default stack size under Windows, I will go with following
not particularly fast and not particularly slow algorithm that I call
"deferred stack". That is, it's  mostly explicit stack, but (explicit)
recursion is deferred until all four neighbors of current pixel saved
on todo stack.
"Not particularly slow" means that I did see cases where some other
algorithms is 2 times faster, but had never seen 3x difference.
In case x and y are known to fit in uint16_t, UI type could be redefined
accordingly. It will make execution faster, but not by much.

#include <stdlib.h>
#include <stddef.h>
#include <string.h>

typedef unsigned char Color;
typedef int           UI;

int floodfill_r(
  Color *image,
  int width,
  int height,
  int x0,
  int y0,
  Color old,
  Color new)
{
  if (width < 0 || height < 0)
    return 0;
   
  if (x0 < 0 || x0 >= width || y0 < 0 || y0 >= height)
    return 0;

  size_t x = x0;
  size_t y = y0;
  if (image[y*width+x] != old)
    return 0;

  const ptrdiff_t INITIAL_TODO_SIZE = 128;
  struct Point { UI x, y; } ;
  struct Point *todo =  malloc(INITIAL_TODO_SIZE * sizeof *todo );
  if (!todo)
    return -1;
  struct Point* todo_end = &todo[INITIAL_TODO_SIZE];

  todo[0].x = x; todo[0].y = y;
  struct Point* sp = &todo[1];
  do {
    x = sp[-1].x; y = sp[-1].y;
    --sp;
    if (image[y*width+x] == old) {
      image[y*width+x] = new;
      if (x > 0 && image[y*width+x-1] == old) {
        sp->x = x - 1; sp->y = y;     ++sp;
      }
      if (y > 0 && image[y*width+x-width] == old) {
        sp->x = x;     sp->y = y - 1; ++sp;
      }
      if (x+1 < width && image[y*width+x+1] == old) {
        sp->x = x + 1; sp->y = y;     ++sp;
      }
      if (y+1 < height && image[y*width+x+width] == old) {
        sp->x = x;     sp->y = y + 1; ++sp;
      }

      if (todo_end-sp < 4) {
          ptrdiff_t used  = sp-todo;
          ptrdiff_t size = todo_end - todo;
          size += size/4;
          struct Point* new_todo = realloc(todo, size * sizeof *todo );
          if(!new_todo) {
            free(todo);
            return -1;
          }
          todo = new_todo;
          sp   = &todo[used];
          todo_end = &todo[size];
      }
    }
  } while (sp != todo);

  free( todo );
  return 1;
}