Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Peter 'Shaggy' Haywood <phaywood@alphalink.com.au>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety
Date: Fri, 22 Mar 2024 13:04:39 +1100
Organization: A noiseless patient Spider
Lines: 75
Message-ID: <ni5vck-5r1.ln1@hendrix.foo>
References: <ut3669$21eur$1@i2pn2.org> <ut4r0q$31rir$1@dont-email.me> <utdbp4$2edhm$1@i2pn2.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7Bit
Injection-Info: dont-email.me; posting-host="9aff0501fa51684d5564c47ba05b513a";
	logging-data="3092699"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX183Wg7s2oacZ7UCmaH7gUBkqf3mlSgKHEw="
User-Agent: KNode/0.10.9
Cancel-Lock: sha1:hadMo7h/Q3q2JOzVt20uD3rfY4o=
Bytes: 3723

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).

-- 


----- Dig the NEW and IMPROVED news sig!! -----


-------------- Shaggy was here! ---------------
              Ain't I'm a dawg!!