Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety
Date: Tue, 19 Mar 2024 21:43:33 -0700
Organization: A noiseless patient Spider
Lines: 30
Message-ID: <86jzlxms22.fsf@linuxsc.com>
References: <ut3669$21eur$1@i2pn2.org> <86h6h3nvyz.fsf@linuxsc.com> <865xxiok09.fsf@linuxsc.com> <20240319131842.00002138@yahoo.com> <utbuk3$qed7$1@dont-email.me> <20240319154900.00001dca@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: dont-email.me; posting-host="7a780175fd21d30328a8a78d1217a04c";
	logging-data="1393396"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX198og/Rz9KOW46SXkRXkWxxpW9NxiIY2xo="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:DCKEVU9ImQaaojw8mXC8Xb4YtE4=
	sha1:Z7dwCO5YGBodXPtvyzLFFFtTM8o=
Bytes: 2497

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.