Re: filling area by color atack safety - worst memory size

Michael S <already5chosen@yahoo.com> writes:

On Wed, 10 Apr 2024 19:47:11 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>

Michael S <already5chosen@yahoo.com> writes:

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.

>
BTW, I am no longer agree with myself about "the rest of them".
By now, I know at least one method that is O(W*log(H)).  It is even
quite fast for majority of my test shapes.  Unfortunately, [in its
current form] it is abysmally slow (100x) for minority of tests.
[In it's current form] it has other disadvantages as well like
consuming non-trivial amount of memory when handling small spot in the
big image.  But that can be improved.  I am less sure that worst-case
speed can be improved enough to make it generally acceptable.
>
I think, I said enough for you to figure out a general principle of
this algorithm.  I don't want to post code here before I try few
improvements.

Thank you for the implied compliment.  At this point I think the
probability that I will figure it out anytime soon is pretty low.