Re: filling area by color atack safety

On 17/03/2024 19:28, Malcolm McLean wrote:

On 17/03/2024 16:45, David Brown wrote:

On 16/03/2024 16:09, Malcolm McLean wrote:

>

The OP's code is simple and obvious, as is its correctness (assuming reasonable definitions of the pixel access and setting functions) and its time and space requirements.  Yours is not.
>

Except it is not. You didn't give the right answer for the space requirements.

Unfortunately, I am still fallible - /easier/ does not mean I'll get it right :-(  And I apologise for unhelpfully rushing that and getting it wrong.
However, I stand by my claim that the recursive version is much easier to analyse.

Your algorithm could be used in a proper implementation, with separate functions to handle the different parts (such as the stack).  The algorithm itself is not bad, it's the implementation that is the main problem.
>

It's better to have one function. Subroutines have a way of getting lost.>

Seriously?  "Subroutines get lost" ?  So your answer is to put all your ideas in a mixer and scrunch them up until any semblance of logic and structure is lost, and the code works (if it does) by trial and error? And then the whole mess is cut-and-paste duplicated - along with any subtle bugs it might have - for 8-connected version.  And that's better, in your eyes, than re-using code?

I have no idea if your code is "out of date" or not.  It seems to be written for images consisting of unsigned chars, so I a not sure it was ever designed for real-world images.
>

It was written a long time ago. But it is writeen in a conservative subset of ANSI C, and so of course it still works, and should work for along time to come. But the 256 integer queue tweak might be out of date. And cache use is far more important now that it was on big processors. So it might be a bit long in the tooth.
 

I have been most interested in being able to be sure the algorithm is correct, rather than considering its absolute (rather than "big O") efficiency in different systems.  It is certainly the case that cache considerations are more relevant now than they used to be on many systems.  And for working on PC's, you would likely dispense with your growing stack entirely and simply allocate a queue big enough for every pixel in the image.

And it's part of the binary image library, and it's designed for marking 8- or 4- connected sections of those images by setting the 1 to a different value. And then further processing. The binary images are often derived from photographs by Otsu thresholding, which is in the same library. But they aren't usually meant for human viewing by end users.

>
I don't know if it is fair to call them a /lot/ more advanced, but certainly a bit more advanced.  And certainly better implementations are possible.
>

And are you going to be constructive or not? Suggest one which might be better? Even implement it?
 

I suggested separating the code into functions - that is /definitely/ constructive.  I suggested using sensible names for parameters and variables (well, the suggestion was implied by my criticism).
And I am also suggesting now that you allocate a queue that is big enough for every pixel in the image.  Much of what you don't touch of that space, will probably never be physically allocated by the OS, depending on page sizes and free memory.
And I would also suggest you drop the requirement for coding in an ancient tongue, and instead switch to reasonably modern C.  Make abstractions for the types and the access functions - it will make the code far easier to follow, easier to show correct, and easier to modify and reuse, without affecting efficiency at run-time.