Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: David Brown <david.brown@hesbynett.no>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety
Date: Sat, 16 Mar 2024 15:40:09 +0100
Organization: A noiseless patient Spider
Lines: 90
Message-ID: <ut4b09$2uhpm$1@dont-email.me>
References: <ut3669$21eur$1@i2pn2.org> <ut4020$2s8ov$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 16 Mar 2024 14:40:09 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="2d79e9313fe696e13669cd0ceaff0321";
	logging-data="3098422"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+Tj1e6GuC5wug0/VUCKYXMMtPVQd9yRXk="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:p7Aa5e8cYOW6yzWYzy6dS8X8YAo=
Content-Language: en-GB
In-Reply-To: <ut4020$2s8ov$1@dont-email.me>
Bytes: 5131

On 16/03/2024 12:33, Malcolm McLean wrote:
> On 16/03/2024 04:11, fir wrote:
>> i was writing simple editor (something like paint but more custom for 
>> my eventual needs) for big pixel (low resolution) drawing
>>
>> it showed in a minute i need a click for changing given drawed area of
>> of one color into another color (becouse if no someone would need to 
>> do it  by hand pixel by pixel and the need to change color of given 
>> element is very common)
>>
>> there is very simple method of doing it - i men i click in given color 
>> pixel then replace it by my color and call the same function on 
>> adjacent 4 pixels (only need check if it is in screen at all and if 
>> the color to change is that initial color
>>
>> int RecolorizePixelAndAdjacentOnes(int x, int y, unsigned old_color, 
>> unsigned new_color)
>> {
>>    if(old_color == new_color) return 0;
>>
>>    if(XYIsInScreen( x,  y))
>>    if(GetPixelUnsafe(x,y)==old_color)
>>    {
>>      SetPixelSafe(x,y,new_color);
>>      RecolorizePixelAndAdjacentOnes(x+1, y,  old_color, new_color);
>>      RecolorizePixelAndAdjacentOnes(x-1, y,  old_color, new_color);
>>      RecolorizePixelAndAdjacentOnes(x, y-1,  old_color, new_color);
>>      RecolorizePixelAndAdjacentOnes(x, y+1,  old_color, new_color);
>>      return 1;
>>    }
>>
>>    return 0;
>> }
>>
>> it work but im not quite sure how to estimate the safety of this  - 
>> incidentally as i said i use this editor to low res graphics  like 
>> 200x200 pixels or less, and it is only a toll of private use,
>> yet i got no time to work on it more than 1-2-3 days i guess but still
>>
>> is there maybe simple way to improve it?
>  >
> This is a cheap and cheerful fllod fill. And it's easy to get right and 
> shouldn't afall over. But but makes an awful not of unnecessary calls, 
> and on a small system and large image might even blow the stack.

It is not going to lead to stack overflow on any reasonable system.  If 
the image size is 200 x 200, as the OP said, it will never reach a depth 
of more than 400 calls (the maximum path length before back-tracking is 
inevitable).  Even for big images, I can't see it being a problem.  I 
remember using the same method on a 16K ZX Spectrum as a teenager.

> 
> Recursion make programs harder to reason about and prove correct.

As a general statement, that is simply wrong.  It is no coincidence that 
most provably correct software development is done using functional 
programming languages, which are based entirely on recursion.  Recursion 
maps well to inductive proofs, and avoids variables, and is thus often 
much easier to work with for proving code correct.

> 
> So a real flood fill doesn't work like that. You use a queue and put the 
> pixels to be filled into that, and trace lines.
> 

That might be a bit more efficient, but not significantly so (at least, 
not in your implementation below).  You are using a queue instead of the 
stack, but it will grow in exactly the same manner.

> And here's some code I wrote a while ago. Use that as a pattern. But not 
> sure how well it works. Haven't used it for a long time.
> 
> https://github.com/MalcolmMcLean/binaryimagelibrary/blob/master/drawbinary.c
> 

Your implementation is a mess, /vastly/ more difficult to prove correct 
than the OP's original one, and unlikely to be very much faster (it will 
certainly scale in the same way in both time and memory usage).

There are a variety of different flood-fill algorithms, with different 
advantages and disadvantages.  Speeds will often depend as much on the 
way the get/set pixel code works, especially if the flood-fill is on 
live displayed data rather than in a buffer off-screen.  But typically 
you need to get a /lot/ more advanced (i.e., not your algorithm) to 
improve on the OP's version by an order of magnitude, so if speed is not 
essential but understanding that it is correct is important, then it 
makes more sense to stick to the original recursive version.