Re: filling area by color atack safety

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

Groovy hepcat fir was jivin' in comp.lang.c on Wed, 20 Mar 2024 11:48
am. It's a cool scene! Dig it.
 

i was slightly thinking a bit of this recursion more generally and
i observed that those very long depth chains are kinda problem of
this recursion becouse maybe it is more fitted to be run parrallel 

 
  I wasn't going to post this here, since it's really an algorithm
issue, rather than a C issue. But the thread seems to have gone on for
some time with you seeming to be unable to solve this. So I'll give
you this as a clue.
  The (or, at least, a) solution is only partially recursive. What I
have used is a line-based algorithm, each line being filled
iteratively (in a simple loop) from left to right. Recursion from
line to line completes the algorithm. Thus, the recursion level is
greatly reduced. And you should find that this approach fills an area
of any shape. Note, however, that for some pathological cases (very
large and complex shapes), this can still create a fairly large level
of recursion. Maybe a more complex approach can deal with this. What I
present here is just a very simple one which, in most cases, should
have a level of recursion well within reason.
  I use a two part approach. The first part (called floodfill in the
code below) just sets up for the second part. The second part (called
r_floodfill here, for recursive floodfill) does the actual work, but
is only called by floodfill(). It goes something like this (although
this is incomplete, untested and not code I've actually used, just an
example):
 
static void r_floodfill(unsigned y, unsigned x, pixel_t new_clr,
pixel_t old_clr)
{
  unsigned start, end;
 
  /* Find start and end of line within floodfill area. */
  start = end = x;
  while(old_clr == get_pixel(y, start - 1))
    --start;
  while(old_clr == get_pixel(y, end + 1))
    ++end;
 
  /* Fill line with new colour. */
  for(x = start; x <= end; x++)
    set_pixel(y, x, new_clr);
 
  /* Run along again, checking pixel colours above and below,
  and recursing if appropriate. */
  for(x = start; x <= end; x++)
  {
    if(old_clr == get_pixel(y - 1, x))
      r_floodfill(y - 1, x, new_clr, old_clr);
    if(old_clr == get_pixel(y + 1, x))
      r_floodfill(y + 1, x, new_clr, old_clr);
  }
}
 
void floodfill(unsigned y, unsigned x, pixel_t new_clr)
{
  pixel_t old_clr = get_pixel(y, x);
 
  /* Only proceed if colours differ. */
  if(new_clr != old_clr)
    r_floodfill(y, x, new_clr, old_clr);
}
 
  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.