Michael S <
already5chosen@yahoo.com> writes:
On Sun, 24 Mar 2024 10:24:45 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
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.
Before I do anything else I should correct a bug in my earlier
FIFO algorithm. The initialization of the variable jx should
read
Index const jx = used*3 < open ? k : j+open/3 &m;
rather than what it used to. (The type may have changed but that
is incidental; what matters is the value of the initializing
expression.) I don't know what I was thinking when I wrote the
previous version, it's just completely wrong.
It seems that in worst case the strict FIFO algorithm is the same as
the rest of them, i.e. O(NN) where NN is the number of re-colored
points. Below is an example of the shape for which I measured memory
consumption for 3840x2160 image almost exactly 4x as much as for
1920x1080.
I agree, the empirical evidence here and in my own tests is quite
compelling.
That said, the constant factor for the FIFO algorithm is lower
than the stack-based algorithms, even taking into account the
difference in sizes for queue and stack elements. Moreover cases
where FIFO algorithms are O( NxN ) are unusual and sparse,
whereas the stack-based algorithms tend to use a lot of memory
in lots of common and routine cases. On the average FIFO
algorithms typically use a lot less memory (or so I conjecture).
[code to generate fractal tree pattern]
Thank you for this. I incorporated it into my set of test
patterns more or less as soon as it was posted.
Now that I have taken some time to play around with different
algorithms and have been more systematic in doing speed
comparisons between different algorithms, on different patterns,
and with a good range of sizes, I have some general thoughts
to offer.
Stack-based methods tend to do well on long skinny patterns and
tend to do not as well on fatter patterns such as circles or
squares. The fractal pattern is ideal for a stack-based method.
Conversely, patterns that are mostly solid shapes don't fare as
well under stack-based methods, at least not the ones that have
been posted in this thread, and also they tend to use more memory
in those cases.
I've been playing around with a more elaborate, mostly FIFO
method, in hopes of getting something that offers the best
of both worlds. The results so far are encouraging, but a
fair amount of tuning has been necessary (and perhaps more
still is), and comparisons have been done on just the one
test server I have available. So I don't know how well it
would hold up on other hardware, including especially more
recent hardware. Under these circumstances I feel it is
premature to post actual code, especially since the code
is still in flux.
This topic has been more interesting that I was expecting, and
also more challenging. I have a strong rule against writing
functions more than about 60 lines long. For the problem of
writing an acceptably quick flood-fill algorithm, I think it would
at the very least be a lot of work to write code to do that while
still observing a limit on function length of even 100 lines, let
alone 60.
filling area by color atack safety
Re: filling area by color atack safety
