Path: ...!2.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Michael S <already5chosen@yahoo.com>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety
Date: Fri, 22 Mar 2024 18:31:16 +0300
Organization: A noiseless patient Spider
Lines: 127
Message-ID: <20240322183116.00003ede@yahoo.com>
References: <ut3669$21eur$1@i2pn2.org>
	<ut4r0q$31rir$1@dont-email.me>
	<utdbp4$2edhm$1@i2pn2.org>
	<ni5vck-5r1.ln1@hendrix.foo>
	<20240322175526.00007505@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Info: dont-email.me; posting-host="52dd7f4c6c554a26e9df583221d221c8";
	logging-data="3134674"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/f5dbEfoh8gcVC9cp30aXGRElhn+cJJYg="
Cancel-Lock: sha1:+6iiat9yUzY5nypektzISvOrmiE=
X-Newsreader: Claws Mail 4.1.1 (GTK 3.24.34; x86_64-w64-mingw32)
Bytes: 4847

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;
}