Re: filling area by color atack safety

On 17/03/2024 14:27, Lew Pitcher wrote:

On Sat, 16 Mar 2024 11:33:20 +0000, 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.
>
Recursion make programs harder to reason about and prove correct.

 I would have said that those unfamiliar with the concept of recursion
have a harder time reasoning about the effects of recursion, or proving
their recursive code correct.
 Take fir's example code above; a simple single call to
RecolorizePixelAndAdjacentOnes() will effectively recolour the
origin cell multiple times, because of how the recursion is handled.

I don't think so. It may look at the original cell, but it will only recolour it (and recursively process its neighbours) if the colour hasn't yet changed to the new one.
If I take a 100x100 image with 10,000 cells, which all have to be filled to the new colour, then SetPixelSafe is called exactly 10,000 times.
The problem is that most of the work is done along a 10,000-deep chain of nested calls.