Re: filling area by color atack safety

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?
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.
But the naive recursive algorithm is O(N) (N = pixels to flood), and inherently we can't beat that without special hardware. The recursive one tends to be slow because calls are expensive. 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.
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?
And I need to run some tests, don't I?
 >

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?
--
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm