Re: filling area by color atack safety

Michael S <already5chosen@yahoo.com> writes:

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

Michael S <already5chosen@yahoo.com> writes:

[...]

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.

I believe it is possible to prove the strict FIFO algorithm is
O(N) for an N x N pixel field, but I haven't tried to do so in
any rigorous way, nor do I know what the constant is.  It does
seem to be larger than 2.

As for finding a worst case, try this (expressed in pseudo code):

   let pc = { width/2, height/2 }
   // assume pixel field 'field' starts out as all zeroes
   color 8 "legs" with the value '1' as follows:

      leg from {        1, pc.y-1 } to { pc.x -1, pc.y-1   }
      leg from {        1, pc.y+1 } to { pc.x -1, pc.y+1   }
      leg from { px.x + 1, pc.y-1 } to { width-2, pc.y-1   }
      leg from { px.x + 1, pc.y+1 } to { width-2, pc.y+1   }

      leg from { px.x - 1,      1 } to { px.x -1, pc.y-1   }
      leg from { px.x + 1,      1 } to { px.x +1, pc.y-1   }
      leg from { px.x - 1, pc.y+1 } to { px.x -1, height/2 }
      leg from { px.x + 1, pc.y+1 } to { px.x +1, height/2 }


So the pixel field should look like this (with longer legs for a
bigger pixel field), with '-' being 0 and '*' being 1:

    +-----------------------+
    | - - - - - - - - - - - |
    | - - - - * - * - - - - |
    | - - - - * - * - - - - |
    | - - - - * - * - - - - |
    | - * * * * - * * * * - |
    | - - - - - - - - - - - |
    | - * * * * - * * * * - |
    | - - - - * - * - - - - |
    | - - - - * - * - - - - |
    | - - - - * - * - - - - |
    | - - - - - - - - - - - |
    +-----------------------+

Now start coloring at the center point with a new value
of 2.