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.