Re: filling area by color atack safety

On Wed, 20 Mar 2024 10:01:10 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

Michael S <already5chosen@yahoo.com> writes:
 

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

Michael S <already5chosen@yahoo.com> writes:
 

On Mon, 18 Mar 2024 22:42:14 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
 

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
[...]
>
Here is the refinement that uses a resizing rather than
fixed-size buffer.
[code] 

>
This variant is significantly slower than Malcolm's.
2x slower for solid rectangle, 6x slower for snake shape. 

>
Slower with some shapes, faster in others. 

>
In my small test suit I found no cases where this specific code is
measurably faster than code of Malcolm. 

 
My test cases include pixel fields of 32k by 32k, with for
example filling the entire field starting at the center point.
Kind of a stress test but it turned up some interesting results.
 

I did find one case in which they are approximately equal.  I call
it "slalom shape" and it's more or less designed to be the worst
case for algorithms that are trying to speed themselves by take
advantage of straight lines.
The slalom shape is generated by following code:
[code] 

 
Thanks, I may try that.
 

In any case
the code was written for clarity of presentation, with
no attention paid to low-level performance. 

>
Yes, your code is easy to understand.  Could have been easier
still if persistent indices had more meaningful names. 

 
I have a different view on that question.  However I take your
point.
 

In other post I showed optimized variant of your algorithm:  -
4-neighbors loop unrolled.  Majority of the speed up come not from
unrolling itself, but from specialization of in-rectangle check
enabled by unroll.
 - Todo queue implemented as circular buffer.
 - Initial size of queue increased.
This optimized variant is more competitive with 'line-grabby'
algorithms in filling solid shapes and faster than them in
'slalom' case. 

 
Yes, unrolling is an obvious improvement.  I deliberately chose a
simple (and non-optimized) method to make it easier to see how it
works.  Simple optimizations are left as an exercise for the
reader. :)
 

Generally, I like your algorithm.
It was surprising for me that queue can work better than stack, my
intuition suggested otherwise, but facts are facts. 

 
Using a stack is like a depth-first search, and a queue is like a
breadth-first search.  For a pixel field of size N x N, doing a
depth-first search can lead to memory usage of order N**2,
whereas a breadth-first search has a "frontier" at most O(N).
Another way to think of it is that breadth-first gets rid of
visited nodes as fast as it can, but depth-first keeps them
around for a long time when everything is reachable from anywhere
(as will be the case in large simple reasons).
>

For my test cases the FIFO depth of your algorithm never exceeds
min(width,height)*2+2. I wonder if existence of this or similar limit
can be proven theoretically.