Path: csiph.com!news.swapon.de!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: Sun, 24 Mar 2024 10:24:45 -0700
Organization: A noiseless patient Spider
Lines: 67
Message-ID: <86jzlrk0f6.fsf@linuxsc.com>
References: <ut3669$21eur$1@i2pn2.org> <86h6h3nvyz.fsf@linuxsc.com> <865xxiok09.fsf@linuxsc.com> <20240319131842.00002138@yahoo.com> <86o7b9ms7d.fsf@linuxsc.com> <20240320115416.00001ab5@yahoo.com> <86zfusltwp.fsf@linuxsc.com> <20240324193352.000062e9@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: dont-email.me; posting-host="ba786330f332cc3d5ff45a8f861eda2e"; logging-data="527788"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/x/uQzdxH8vHKpG1A1cvglrlZIzuPwJGA="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:pgLq89Hyh8D6GOqoW5kVgTj2VdQ= sha1:3v5697zL3d0xUIz2Md/cCYOlGCA=
Xref: csiph.com comp.lang.c:383962

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.