Re: filling area by color atack safety

On 16/03/2024 19:13, bart 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  -

>
On my machine, it's OK up to a 400x400 image (starting with all one colour and filling from the centre with another colour).
>
At 500x500, I get stack overflow. The 400x400 the maximum recursion depth is 80,000 calls.

 For an NxN image filling from the centre, the max depth is N*N/2, or from one corner, it's N*N.
 The depth with an N*1 image starting from one end seems to just N.
 It appears to fill as much as possible (in my tests, all remaining pixels), before returning from any call, at which point, the work is done.
 I've just looked in my Computer Graphics Principles and Practice book (after blowing off the dust), and the algorithm above is exactly the 'FloodFill4' one in the book. It mentions the problems with the stack; maybe I should have looked in there first.
 It talks about better approaches, but it doesn't give a better algorithm that I can see. Perhaps the OP should just do an online search for one.