Re: filling area by color atack safety

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.