Re: filling area by color atack safety

On 18/03/2024 16:28, David Brown wrote:

On 18/03/2024 10:26, Malcolm McLean wrote:
>
It is completely normal for correctness proofs to make assumptions about things like resources.  An analysis of your code for correctness would also generally assume that the heap would be big enough - if the heap runs out, your code will not correctly flood-fill the image.  Analysis of efficiency in time and space is a separate issue - related, but separate.  Things like maximum recursion depth (and heap size) are very implementation-specific, and thus need to be considered separately from the algorithm itself.
 

It's trivial to engineer a system with a large stack and very small heap. But unlikley anyone would actually do so on a system on which floodfill would run.

And while this code is in C, the same algorithm could be implemented in other languages.  A language that uses a VM might be fine with a much higher recursion depth - or it might be much lower.  A language for which recursion is a major tool (such as a functional programming language) might automatically convert some recursive code to a queue-based non-recursive solution.  (I'd be impressed to see one do that for this algorithm, however.)
 

Now a 100x100 woked fine an my machine  - I just checked the main stack, and it's 8MB by default. BUt of cuuurse the bigger than machine, the bigger the image th euser might want to load.
>

 You still haven't considered using a spell-checker, even though you use a news client with one built in?  Perhaps you need a better keyboard?
 

I'll try it out. Since you're dyslexic. Normal readers can read English text with just the initial and terminal letters right and the rest jumbled, at similar speed to normal text.

>
The worst case is either going to be the stripy path example given by Michael S., or a completely blank image - it depends on how the east-west stripes affect the queue depth.  It should not be hard to try these.  So that would be either approximately half the total pixel count, or the total pixel count.  And I can't think how you could specify a "typical" image and "typical" flood fill request - without specifying this in some way, you need to collect lots of statistics of real-world use, or it's mere guesswork.
 

Pixels usually represent objects. Take a glance around your. How many objects of a similar colour are spider's webs,  lace curtains, long wires, and so on. And how many are pieces of paper, coffee cups. computer mice, and so on? And of course it mustn't fall over on the unusual objects, but the main consideration is usually that it is fast and efficient on the common ones.
But not always of course, Sometimes results must in in under 0.1 seconds, and so 0.09 is as good as 0.01, but 0.11 on a rare spider's web is catastrophic.

 That would be the "royal we", I presume?  I know /I/ would have no use for a flood-fill routine that did not support colour styles I use.
 

This routine is part of the binary image processing library, so of course it is written to be easy to use with binary images, or binary images which have been processed and are no longer strictly binary images. But if people want to take it and use it as pattern for a general flood fill, then of course I'm perfectly happy that they have found the code to be of use.
--
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm