Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Peter 'Shaggy' Haywood 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: References: 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!!