Re: filling area by color atack safety

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

On 16/03/2024 14:40, David Brown wrote:

On 16/03/2024 12:33, Malcolm McLean wrote:
>

And here's some code I wrote a while ago. Use that as a pattern. But not sure how well it works. Haven't used it for a long time.
>
https://github.com/MalcolmMcLean/binaryimagelibrary/blob/master/drawbinary.c
>

>
Your implementation is a mess, /vastly/ more difficult to prove correct than the OP's original one, and unlikely to be very much faster (it will certainly scale in the same way in both time and memory usage).
>

Now is this David Brown being David Borwn, ot its it actaully ture?

I don't know who "David Borwn" might be, nor what "ture" means.  If you can't type, and can't spell, then at least pay the group the respect of using a spell-checker.

It's not designed to be eay to prove correct, that's true. And the maintain it's mess is that we are managing the queue manually for speed.

It is badly designed code.  It is a jumble of wildly different concepts, thrown together in one huge function with no structure or organisation, and with meaningless names for the variables and absurd names for the parameters.
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.
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.

 But the naive recursive algorithm is O(N) (N = pixels to flood), and inherently we can't beat that without special hardware.

Assuming you are measuring the number of pixels read or written here, then that is, I think, correct.

The recursive one tends to be slow because calls are expensive.

Yes, I agree that recursion can be slow (unless it is simple enough for the compiler to turn it into a loop).  And it typically takes more stack space than you'd need for a dedicated queue.  But whether or not that makes a significant difference depends on the code in question, and how much work you are doing within the code.  If step of the algorithm takes a lot of time anyway, the call overhead will be of less relevance.
I would expect that your code would be several times faster than the OP's, with similar scaling.  But the OP's is understandable and easily seen to be correct, unlike yours, and correctness trumps speed every time.
And starting from a correct recursive version, it's possible to improve on it in many ways while retaining correctness.

And mine makes calls to malloc() and realloc to manage the queue. And of course whilst we might blow the stack, we are much less likely to run out of heap.

True.

 And it's been tweaked abit in hacky way to make it faster on real images. And whilst it's still going to work, is it out of date?
 

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.
What is clear is that you have taken an okay algorithm - not state of the art, but not the worst - and made a dog's breakfast of an implementation in your attempts to micro-optimise.  This means you have code that can't be easily analysed or seen to be correct, cannot be improved algorithmically, and cannot be expanded or gain new features without a massive re-write.

And I need to run some tests, don't I?
 

If you like.

 >

There are a variety of different flood-fill algorithms, with different advantages and disadvantages.  Speeds will often depend as much on the way the get/set pixel code works, especially if the flood-fill is on live displayed data rather than in a buffer off-screen.  But typically you need to get a /lot/ more advanced (i.e., not your algorithm) to improve on the OP's version by an order of magnitude, so if speed is not essential but understanding that it is correct is important, then it makes more sense to stick to the original recursive version.
>

 What are these / lot / more advanced algorithms? Maybe they exist. But don't people deserve some sort of link?
 

<https://gprivate.com/6a2yp>
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.