Re: filling area by color atack safety

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.