Re: filling area by color atack safety

On 18/03/2024 18:25, Malcolm McLean wrote:

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.

It is unlikely (that is how the word is spelt) that people would use your code for a flood fill either - but I fully agree that it is unlikely that a simple recursive flood fill algorithm is much use as a practical way to do flood fills in any real-world software.

 

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.

You are fond of making up "Malcolm facts" about the cognitive effort involved in understanding things like nested parentheses.  Poor spelling, typos, grammatical errors, and the like similarly increase the cognitive effort in reading your posts.  When it takes too much effort to figure out what you are trying to say, it is not worth the bother.
I am not looking for perfection here - mistakes happen.  I am merely looking for a minimum of effort on your part, such as using the spell-checker built into your newsreader.  And I don't expect you to do this for /me/, or because I or anyone else is dyslexic.  I consider it a basic level of politeness and respect for others.  I find it extraordinary that you have been so reluctant to take this step before now.

>
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.

There is nothing that I or anyone else can see that could possibly be considered a "typical" image - though there are clearly things that are commonly seen.  And simple colour-matching flood fills are totally pointless on any real image (photographs, realistic renderings, etc.).

 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.

I cannot imagine the situation where you would have a hard real-time limit of 0.1 seconds to do a simplistic flood fill on a rare spider's web (or picture thereof).
I think it would suffice to test the code on a few worst-case samples, and a few examples of images you have yourself that you need to flood-fill.  If the speed is good enough on your computer during such tests, that would be all you need.  You are not making a real-world reusable graphics library or a serious image manipulation tool here.

>
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.