Re: filling area by color atack safety

On 17/03/2024 10:31, Ben Bacarisse wrote:

scott@slp53.sl.home (Scott Lurndal) writes:
 

David Brown <david.brown@hesbynett.no> writes:

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

>
Malcolm can't even spell 'integer' correctly in that code blob :-).

 As someone with dyslexia I have never liked mocking remarks about
spelling errors.  Using "even" suggests that a superficial issue hints
at deeper problems.  This is rarely the case.
 However, I /would/ urge Malcolm to correct the spelling if Bresenham
since the intent was clearly to credit the discoverer.  Also,
misspellings don't play well with library databases.
 

Certainly the intent of Fir's algorithm is easily discerned from
his code.   I can't say that about Malcolms.

 I have some reservations about the code, but he posted a link so there
is no indication that he wants a review of it.
 

Tbe main intent was to help fir. That algorithm does tend to blow the stack though of course it depends on the image. However worst case is a pattern which is pixel wide line, e.g. a spiral or a maze or a series of alterante light and dark bands with a lirtel gaps at each end. And you achieve that by filling half the pixels. So foe a 100x100 image your worst case is 10,000 = 5,000 recursive calls, and the stack is blown.
And so not that that hard to reason about. However no-one actually took up the challenge and actually did so.
And mine only maes a few subroutines calls to standard library functions, so you can tell at a glance that the stack won't be blown. But it's not as clear what the worst case of for heap is, but it can't be more than 2xNxlow integers, where 2 is 2 integers for the pixel x, y cordinates, N is the number of pixels, and low is the catastrophic worst case scenario, which can't be over about 4. And that's not going to be a problem for most computers. Assuming things aren't bugged.
And I suggest that fir just replace the direct buffer reads and writes with calls, and job done. But the code is fair game. If you can make it better, that's a good thing, not a humiliation.
--
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm