Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch
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: <86h6h3nvyz.fsf@linuxsc.com> <865xxiok09.fsf@linuxsc.com> <20240319131842.00002138@yahoo.com> <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 writes:
> On Tue, 19 Mar 2024 11:57:53 +0000
> Malcolm McLean 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.