Re: filling area by color atack safety

On Tue, 19 Mar 2024 21:43:33 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

Michael S <already5chosen@yahoo.com> writes:
 

On Tue, 19 Mar 2024 11:57:53 +0000
Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
 

No.  Mine takes horizontal scan lines and extends them, then places
the pixels above and below in a queue to be considered as seeds for
the next scan line.  (It's not mine, but I don't know who invented
it. It wasn't me.)
>
Tim, now what does it do?  Essentially it's the recursive fill
algorithm but with the data only on the stack instead of the call
and the data.  And todo is actually a queue rather than a stack.
>
Now why would it be slower?  Probaby because you usually only hit a
pixel three times with mine - once below, once above, and once for
the scan line itself, while you consider it 5 times for Tim's -
once for each neighbour and once for itself.  Then horizontally
adjacent pixels are more likely to be in the same cache line than
vertically adjacent pixels, so processing images in scan lines
tends to be a bit faster. 

>
Below is a variant of recursive algorithm that is approximately as
fast as your code (1.25x faster for filling solid rectangle, 1.43x
slower for filling snake shape).
The code is a bit long, but I hope that the logic is still obvious
and there is no need to prove correctness.  [...] 

 
To me it looks like this recursive algorithm doesn't find all
pixels that need coloring in some situations.

Yesterday night I had few doubts myself, but after further thinking
came to conclusion that it it works in all situations.