Re: filling area by color atack safety

Michael S <already5chosen@yahoo.com> writes:

On Sun, 17 Mar 2024 18:25:20 +0200
Michael S <already5chosen@yahoo.com> wrote:
>

On Sun, 17 Mar 2024 14:56:34 +0000
Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:

[a floodfill routine posted by Malcolm]

[...]
>
[a recursive area fill written by Michael S]

>
I did my own measurements with snake-like image from my first
response to Malcolm.  For this shape, recursive version (after my
improvement) is almost exactly 10 times slower than Malcolm's
iterative code.  And suspect to stack overflow although a little
less so than original.

It's hard to write a recursive area fill routine if one wants to
guarantee worst case behavior in all cases.  This problem is not
a good fit to using recursion without there being some kind of
constraints on what the inputs will be.

Even if in Big Oh sense they are the same, it does look like
Malcolm's variant is decisively faster in practice.

I've done some tests with Malcolm's code.  Some observations:

It uses more memory than it needs to.

It's anisotropic, which is to say it behaves differently with
respect to changes in width than it does to changes in height.

It doesn't scale well.  In particular worst case performance
scaling is worse than O(N) (as determined experimentally, not
theoretically).

The code is much longer than is needed just to do an area fill.
A small fraction of that is simply layout style, but mostly it's
that the code is more complicated than it needs to be.