i was writing simple editor (something like paint but more custom for my
eventual needs) for big pixel (low resolution) drawing

it showed in a minute i need a click for changing given drawed area of
of one color into another color (becouse if no someone would need to do
it by hand pixel by pixel and the need to change color of given element
is very common)

there is very simple method of doing it - i men i click in given color
pixel then replace it by my color and call the same function on adjacent
4 pixels (only need check if it is in screen at all and if the color to
change is that initial color

int RecolorizePixelAndAdjacentOnes(int x, int y, unsigned old_color,
unsigned new_color)
{ if(old_color == new_color) return 0;

if(XYIsInScreen( x, y))
if(GetPixelUnsafe(x,y)==old_color)
{
SetPixelSafe(x,y,new_color);
RecolorizePixelAndAdjacentOnes(x+1, y, old_color, new_color);
RecolorizePixelAndAdjacentOnes(x-1, y, old_color, new_color);
RecolorizePixelAndAdjacentOnes(x, y-1, old_color, new_color);
RecolorizePixelAndAdjacentOnes(x, y+1, old_color, new_color);
return 1;
}

return 0;
}

it work but im not quite sure how to estimate the safety of this -
incidentally as i said i use this editor to low res graphics like
200x200 pixels or less, and it is only a toll of private use,
yet i got no time to work on it more than 1-2-3 days i guess but still

is there maybe simple way to improve it?

On 16/03/2024 04:11, fir wrote:
> i was writing simple editor (something like paint but more custom for my
> eventual needs) for big pixel (low resolution) drawing
>
> it showed in a minute i need a click for changing given drawed area of
> of one color into another color (becouse if no someone would need to do
> it  by hand pixel by pixel and the need to change color of given element
> is very common)
>
> there is very simple method of doing it - i men i click in given color
> pixel then replace it by my color and call the same function on adjacent
> 4 pixels (only need check if it is in screen at all and if the color to
> change is that initial color
>
> int RecolorizePixelAndAdjacentOnes(int x, int y, unsigned old_color,
> unsigned new_color)
> {
>   if(old_color == new_color) return 0;
>
>   if(XYIsInScreen( x,  y))
>   if(GetPixelUnsafe(x,y)==old_color)
>   {
>     SetPixelSafe(x,y,new_color);
>     RecolorizePixelAndAdjacentOnes(x+1, y,  old_color, new_color);
>     RecolorizePixelAndAdjacentOnes(x-1, y,  old_color, new_color);
>     RecolorizePixelAndAdjacentOnes(x, y-1,  old_color, new_color);
>     RecolorizePixelAndAdjacentOnes(x, y+1,  old_color, new_color);
>     return 1;
>   }
>
>   return 0;
> }
>
> it work but im not quite sure how to estimate the safety of this  -
> incidentally as i said i use this editor to low res graphics  like
> 200x200 pixels or less, and it is only a toll of private use,
> yet i got no time to work on it more than 1-2-3 days i guess but still
>
> is there maybe simple way to improve it?
>
This is a cheap and cheerful fllod fill. And it's easy to get right and
shouldn't afall over. But but makes an awful not of unnecessary calls,
and on a small system and large image might even blow the stack.

Recursion make programs harder to reason about and prove correct.

So a real flood fill doesn't work like that. You use a queue and put the
pixels to be filled into that, and trace lines.

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

--
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> Recursion make programs harder to reason about and prove correct.

Are you prepared to offer any evidence to support this astonishing
statement or can we just assume it's another Malcolmism?

--
Ben.

On 16/03/2024 12:33, Malcolm McLean wrote:
> On 16/03/2024 04:11, fir wrote:
>> i was writing simple editor (something like paint but more custom for
>> my eventual needs) for big pixel (low resolution) drawing
>>
>> it showed in a minute i need a click for changing given drawed area of
>> of one color into another color (becouse if no someone would need to
>> do it  by hand pixel by pixel and the need to change color of given
>> element is very common)
>>
>> there is very simple method of doing it - i men i click in given color
>> pixel then replace it by my color and call the same function on
>> adjacent 4 pixels (only need check if it is in screen at all and if
>> the color to change is that initial color
>>
>> int RecolorizePixelAndAdjacentOnes(int x, int y, unsigned old_color,
>> unsigned new_color)
>> {
>>    if(old_color == new_color) return 0;
>>
>>    if(XYIsInScreen( x,  y))
>>    if(GetPixelUnsafe(x,y)==old_color)
>>    {
>>      SetPixelSafe(x,y,new_color);
>>      RecolorizePixelAndAdjacentOnes(x+1, y,  old_color, new_color);
>>      RecolorizePixelAndAdjacentOnes(x-1, y,  old_color, new_color);
>>      RecolorizePixelAndAdjacentOnes(x, y-1,  old_color, new_color);
>>      RecolorizePixelAndAdjacentOnes(x, y+1,  old_color, new_color);
>>      return 1;
>>    }
>>
>>    return 0;
>> }
>>
>> it work but im not quite sure how to estimate the safety of this  -
>> incidentally as i said i use this editor to low res graphics  like
>> 200x200 pixels or less, and it is only a toll of private use,
>> yet i got no time to work on it more than 1-2-3 days i guess but still
>>
>> is there maybe simple way to improve it?
> >
> This is a cheap and cheerful fllod fill. And it's easy to get right and
> shouldn't afall over. But but makes an awful not of unnecessary calls,
> and on a small system and large image might even blow the stack.

It is not going to lead to stack overflow on any reasonable system. If
the image size is 200 x 200, as the OP said, it will never reach a depth
of more than 400 calls (the maximum path length before back-tracking is
inevitable). Even for big images, I can't see it being a problem. I
remember using the same method on a 16K ZX Spectrum as a teenager.

>
> Recursion make programs harder to reason about and prove correct.

As a general statement, that is simply wrong. It is no coincidence that
most provably correct software development is done using functional
programming languages, which are based entirely on recursion. Recursion
maps well to inductive proofs, and avoids variables, and is thus often
much easier to work with for proving code correct.

>
> So a real flood fill doesn't work like that. You use a queue and put the
> pixels to be filled into that, and trace lines.
>

That might be a bit more efficient, but not significantly so (at least,
not in your implementation below). You are using a queue instead of the
stack, but it will grow in exactly the same manner.

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

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.

On 16/03/2024 13:55, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>
>> Recursion make programs harder to reason about and prove correct.
>
> Are you prepared to offer any evidence to support this astonishing
> statement or can we just assume it's another Malcolmism?

You have evidence to suggest that the opposite is true?

I personally find recursion hard work and errors much harder to debug.
It is also becomes much more important to show that will not cause stack
overflow.

On 16/03/2024 13:55, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>
>> Recursion make programs harder to reason about and prove correct.
>
> Are you prepared to offer any evidence to support this astonishing
> statement or can we just assume it's another Malcolmism?
>

Example given. A recursive algorithm which is hard to reason about and
prove correct, because we don't really know whether under perfectly
reasonable assumptions it will or will not blow the stack.
--
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm

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

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>On 16/03/2024 13:55, Ben Bacarisse wrote:
>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>
>>> Recursion make programs harder to reason about and prove correct.
>>
>> Are you prepared to offer any evidence to support this astonishing
>> statement or can we just assume it's another Malcolmism?
>>
>
>Example given. A recursive algorithm which is hard to reason about and

Perhaps hard for _you_ to reason about. That doesn't
generalize to every other programmer that might read that
code.

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

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

On 16/03/2024 04:11, fir wrote:
> i was writing simple editor (something like paint but more custom for my
> eventual needs) for big pixel (low resolution) drawing
>
> it showed in a minute i need a click for changing given drawed area of
> of one color into another color (becouse if no someone would need to do
> it  by hand pixel by pixel and the need to change color of given element
> is very common)
>
> there is very simple method of doing it - i men i click in given color
> pixel then replace it by my color and call the same function on adjacent
> 4 pixels (only need check if it is in screen at all and if the color to
> change is that initial color
>
> int RecolorizePixelAndAdjacentOnes(int x, int y, unsigned old_color,
> unsigned new_color)
> {
>   if(old_color == new_color) return 0;
>
>   if(XYIsInScreen( x,  y))
>   if(GetPixelUnsafe(x,y)==old_color)
>   {
>     SetPixelSafe(x,y,new_color);
>     RecolorizePixelAndAdjacentOnes(x+1, y,  old_color, new_color);
>     RecolorizePixelAndAdjacentOnes(x-1, y,  old_color, new_color);
>     RecolorizePixelAndAdjacentOnes(x, y-1,  old_color, new_color);
>     RecolorizePixelAndAdjacentOnes(x, y+1,  old_color, new_color);
>     return 1;
>   }
>
>   return 0;
> }
>
> it work but im not quite sure how to estimate the safety of this  -

On my machine, it's OK up to a 400x400 image (starting with all one
colour and filling from the centre with another colour).

At 500x500, I get stack overflow. The 400x400 the maximum recursion
depth is 80,000 calls.

I don't an alternative ATM, I'm just reporting what I saw with my test
program shown below, since some here don't believe that recursion can be
problematical.

--------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned char byte;

enum {dimx=400};
enum {dimy=dimx};
byte image[dimx][dimy];
int maxdepth;

byte getpixel(int x, int y) {
return image[x][y];
}

void setpixel(int x, int y, byte newcol) {
image[x][y]=newcol;
}

int onscreen(int x, int y) {
return x>=0 && x<dimx && y>=0 && y<dimy;
}

void fill(int x, int y, unsigned old_color, unsigned new_color)
{ if(old_color == new_color) return;
static int depth=0;

++depth;
if (depth>maxdepth) maxdepth=depth;

if(onscreen( x, y)) {
//printf("FILL %d %d %d depth:%d\n",x,y, onscreen(x,y), depth);
if(getpixel(x,y)==old_color)
{
setpixel(x,y,new_color);
fill(x+1, y, old_color, new_color);
fill(x-1, y, old_color, new_color);
fill(x, y-1, old_color, new_color);
fill(x, y+1, old_color, new_color);
--depth;
return;
}
}
--depth;
return;
}

static void writepgm(byte* file) {
int x, y;
void* f;
f = fopen(file,"w");
fprintf(f,"%s\n","P2");
fprintf(f,"%d %d\n",dimx,dimy);
fprintf(f,"255\n");
for (y=0; y<dimy; ++y) {
for (x=0; x<dimx; ++x) {
fprintf(f,"%u%s",image[y][x]," ");
}
fprintf(f,"\n");
}
fclose(f);
}

int main(void) {

fill(dimx/2, dimy/2, 0, 80);

printf("maxdepth=%d\n",maxdepth);
puts("");

puts("Writing test.ppm:");
writepgm("test.ppm");

}

On 16/03/2024 18:21, Scott Lurndal wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>> On 16/03/2024 13:55, Ben Bacarisse wrote:
>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>>
>>>> Recursion make programs harder to reason about and prove correct.
>>>
>>> Are you prepared to offer any evidence to support this astonishing
>>> statement or can we just assume it's another Malcolmism?
>>>
>>
>> Example given. A recursive algorithm which is hard to reason about and
>
> Perhaps hard for _you_ to reason about. That doesn't
> generalize to every other programmer that might read that
> code.
>
>
From experience this one blows the stack, but not always. Sometimes
it's OK to use.

Since you can reason about it so easily, you can tell the others when
you're OK and when you are not, in a handy intuitive way so that someone
thinking of implementing it will know.

On 16/03/2024 19:13, bart wrote:
> On 16/03/2024 04:11, fir wrote:
>> i was writing simple editor (something like paint but more custom for
>> my eventual needs) for big pixel (low resolution) drawing
>>
>> it showed in a minute i need a click for changing given drawed area of
>> of one color into another color (becouse if no someone would need to
>> do it  by hand pixel by pixel and the need to change color of given
>> element is very common)
>>
>> there is very simple method of doing it - i men i click in given color
>> pixel then replace it by my color and call the same function on
>> adjacent 4 pixels (only need check if it is in screen at all and if
>> the color to change is that initial color
>>
>> int RecolorizePixelAndAdjacentOnes(int x, int y, unsigned old_color,
>> unsigned new_color)
>> {
>>    if(old_color == new_color) return 0;
>>
>>    if(XYIsInScreen( x,  y))
>>    if(GetPixelUnsafe(x,y)==old_color)
>>    {
>>      SetPixelSafe(x,y,new_color);
>>      RecolorizePixelAndAdjacentOnes(x+1, y,  old_color, new_color);
>>      RecolorizePixelAndAdjacentOnes(x-1, y,  old_color, new_color);
>>      RecolorizePixelAndAdjacentOnes(x, y-1,  old_color, new_color);
>>      RecolorizePixelAndAdjacentOnes(x, y+1,  old_color, new_color);
>>      return 1;
>>    }
>>
>>    return 0;
>> }
>>
>> it work but im not quite sure how to estimate the safety of this  -
>
> On my machine, it's OK up to a 400x400 image (starting with all one
> colour and filling from the centre with another colour).
>
> At 500x500, I get stack overflow. The 400x400 the maximum recursion
> depth is 80,000 calls.

For an NxN image filling from the centre, the max depth is N*N/2, or
from one corner, it's N*N.

The depth with an N*1 image starting from one end seems to just N.

It appears to fill as much as possible (in my tests, all remaining
pixels), before returning from any call, at which point, the work is done.

I've just looked in my Computer Graphics Principles and Practice book
(after blowing off the dust), and the algorithm above is exactly the
'FloodFill4' one in the book. It mentions the problems with the stack;
maybe I should have looked in there first.

It talks about better approaches, but it doesn't give a better algorithm
that I can see. Perhaps the OP should just do an online search for one.

On 3/16/2024 1:02 PM, Malcolm McLean wrote:
> On 16/03/2024 18:21, Scott Lurndal wrote:
>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>> On 16/03/2024 13:55, Ben Bacarisse wrote:
>>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>>>
>>>>> Recursion make programs harder to reason about and prove correct.
>>>>
>>>> Are you prepared to offer any evidence to support this astonishing
>>>> statement or can we just assume it's another Malcolmism?
>>>>
>>>
>>> Example given. A recursive algorithm which is hard to reason about and
>>
>> Perhaps hard for _you_ to reason about.  That doesn't
>> generalize to every other programmer that might read that
>> code.
>>
>>
> From experience this one blows the stack, but not always. Sometimes
> it's OK to use.

Blowing the stack is not good at all. However, sometimes, I consider a
recursive algorithm easier to understand. So, I build it first... Get it
working, _then_ think about an iterative solution...

>
> Since you can reason about it so easily, you can tell the others when
> you're OK and when you are not, in a handy intuitive way so that someone
> thinking of implementing it will know.
>

On 16/03/2024 20:23, bart wrote:
> On 16/03/2024 19:13, bart wrote:
>> On 16/03/2024 04:11, fir wrote:
>>> i was writing simple editor (something like paint but more custom for
>>> my eventual needs) for big pixel (low resolution) drawing
>>>
>>> it showed in a minute i need a click for changing given drawed area of
>>> of one color into another color (becouse if no someone would need to
>>> do it  by hand pixel by pixel and the need to change color of given
>>> element is very common)
>>>
>>> there is very simple method of doing it - i men i click in given
>>> color pixel then replace it by my color and call the same function on
>>> adjacent 4 pixels (only need check if it is in screen at all and if
>>> the color to change is that initial color
>>>
>>> int RecolorizePixelAndAdjacentOnes(int x, int y, unsigned old_color,
>>> unsigned new_color)
>>> {
>>>    if(old_color == new_color) return 0;
>>>
>>>    if(XYIsInScreen( x,  y))
>>>    if(GetPixelUnsafe(x,y)==old_color)
>>>    {
>>>      SetPixelSafe(x,y,new_color);
>>>      RecolorizePixelAndAdjacentOnes(x+1, y,  old_color, new_color);
>>>      RecolorizePixelAndAdjacentOnes(x-1, y,  old_color, new_color);
>>>      RecolorizePixelAndAdjacentOnes(x, y-1,  old_color, new_color);
>>>      RecolorizePixelAndAdjacentOnes(x, y+1,  old_color, new_color);
>>>      return 1;
>>>    }
>>>
>>>    return 0;
>>> }
>>>
>>> it work but im not quite sure how to estimate the safety of this  -
>>
>> On my machine, it's OK up to a 400x400 image (starting with all one
>> colour and filling from the centre with another colour).
>>
>> At 500x500, I get stack overflow. The 400x400 the maximum recursion
>> depth is 80,000 calls.
>
> For an NxN image filling from the centre, the max depth is N*N/2, or
> from one corner, it's N*N.
>
> The depth with an N*1 image starting from one end seems to just N.
>
> It appears to fill as much as possible (in my tests, all remaining
> pixels), before returning from any call, at which point, the work is done.
>
> I've just looked in my Computer Graphics Principles and Practice book
> (after blowing off the dust), and the algorithm above is exactly the
> 'FloodFill4' one in the book. It mentions the problems with the stack;
> maybe I should have looked in there first.
>
> It talks about better approaches, but it doesn't give a better algorithm
> that I can see. Perhaps the OP should just do an online search for one.
>
>
>
Now think about adding some barriers. But don't make life too easy for
Scott.

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.

--
Ben.

bart <bc@freeuk.com> writes:

> On 16/03/2024 13:55, Ben Bacarisse wrote:
>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>
>>> Recursion make programs harder to reason about and prove correct.
>> Are you prepared to offer any evidence to support this astonishing
>> statement or can we just assume it's another Malcolmism?
>
> You have evidence to suggest that the opposite is true?

No, which is why I did not make such an assertion.

--
Ben.

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On 16/03/2024 13:55, Ben Bacarisse wrote:
>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>
>>> Recursion make programs harder to reason about and prove correct.
>> Are you prepared to offer any evidence to support this astonishing
>> statement or can we just assume it's another Malcolmism?
>
> Example given. A recursive algorithm which is hard to reason about and
> prove correct, because we don't really know whether under perfectly
> reasonable assumptions it will or will not blow the stack.

Had you offered a proof that your code neither "blows the stack" nor
runs out of any other resource we'd have a starting point for
comparison, but you have not done that.

Mind you, had you done that, we would have something that might
eventually become only one piece of evidence for what is an
astonishingly general remark. Broadly applicable remarks require either
broadly applicable evidence or a wealth of distinct cases.

Your "rule" suggests that all reasoning is impeded by the presence of
recursion and I don't think you can support that claim. This is
characteristic of many of your remarks -- they are general "rules" that
often remain rules even when there is evidence to the contrary.

I'll make another point in the hope of clarifying the matter. An
algorithm or code is usually proved correct (or not!) under the
assumption that it has adequate resources -- usually time and storage.
Further reasoning may then be done to determine the resource
requirements since this is so often dependent on context. This
separation is helpful as you don't usually want to tie "correctness" to
some specific installation. The code might run on a system with a
dynamically allocated stack, for example, that has very similar
limitations to "heap" memory.

To put is more generally, we often want to prove properties of code that
are independent of physical constraints. Your remark includes this kind
reasoning. Did you intend it to?

--
Ben.

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

On 17/03/2024 11:25, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>
>> On 16/03/2024 13:55, Ben Bacarisse wrote:
>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>>
>>>> Recursion make programs harder to reason about and prove correct.
>>> Are you prepared to offer any evidence to support this astonishing
>>> statement or can we just assume it's another Malcolmism?
>>
>> Example given. A recursive algorithm which is hard to reason about and
>> prove correct, because we don't really know whether under perfectly
>> reasonable assumptions it will or will not blow the stack.
>
> Had you offered a proof that your code neither "blows the stack" nor
> runs out of any other resource we'd have a starting point for
> comparison, but you have not done that.
>
> Mind you, had you done that, we would have something that might
> eventually become only one piece of evidence for what is an
> astonishingly general remark. Broadly applicable remarks require either
> broadly applicable evidence or a wealth of distinct cases.
>
> Your "rule" suggests that all reasoning is impeded by the presence of
> recursion and I don't think you can support that claim. This is
> characteristic of many of your remarks -- they are general "rules" that
> often remain rules even when there is evidence to the contrary.
>
> I'll make another point in the hope of clarifying the matter. An
> algorithm or code is usually proved correct (or not!) under the
> assumption that it has adequate resources -- usually time and storage.
> Further reasoning may then be done to determine the resource
> requirements since this is so often dependent on context. This
> separation is helpful as you don't usually want to tie "correctness" to
> some specific installation. The code might run on a system with a
> dynamically allocated stack, for example, that has very similar
> limitations to "heap" memory.
>
> To put is more generally, we often want to prove properties of code that
> are independent of physical constraints. Your remark includes this kind
> reasoning. Did you intend it to?
>
The convetional wisdom is the opposite, But here, conventional wisdom
fails. Because heaps are unlimited whilst stacks are not.

--
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm

On Sat, 16 Mar 2024 11:33:20 +0000
Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:

> On 16/03/2024 04:11, fir wrote:
> > i was writing simple editor (something like paint but more custom
> > for my eventual needs) for big pixel (low resolution) drawing
> >
> > it showed in a minute i need a click for changing given drawed area
> > of of one color into another color (becouse if no someone would
> > need to do it  by hand pixel by pixel and the need to change color
> > of given element is very common)
> >
> > there is very simple method of doing it - i men i click in given
> > color pixel then replace it by my color and call the same function
> > on adjacent 4 pixels (only need check if it is in screen at all and
> > if the color to change is that initial color
> >
> > int RecolorizePixelAndAdjacentOnes(int x, int y, unsigned
> > old_color, unsigned new_color)
> > {
> >   if(old_color == new_color) return 0;
> >
> >   if(XYIsInScreen( x,  y))
> >   if(GetPixelUnsafe(x,y)==old_color)
> >   {
> >     SetPixelSafe(x,y,new_color);
> >     RecolorizePixelAndAdjacentOnes(x+1, y,  old_color, new_color);
> >     RecolorizePixelAndAdjacentOnes(x-1, y,  old_color, new_color);
> >     RecolorizePixelAndAdjacentOnes(x, y-1,  old_color, new_color);
> >     RecolorizePixelAndAdjacentOnes(x, y+1,  old_color, new_color);
> >     return 1;
> >   }
> >
> >   return 0;
> > }
> >
> > it work but im not quite sure how to estimate the safety of this  -
> > incidentally as i said i use this editor to low res graphics  like
> > 200x200 pixels or less, and it is only a toll of private use,
> > yet i got no time to work on it more than 1-2-3 days i guess but
> > still
> >
> > is there maybe simple way to improve it?
> >
> This is a cheap and cheerful fllod fill. And it's easy to get right
> and shouldn't afall over.

Except I don't understand why it works it all.
Can't fill area have sub-areas that only connected through diagonal?

On 17/03/2024 12:28, Malcolm McLean wrote:
> 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.

I'd been planning to create a square spiral. But I found I got N*N/2
behaviour even with a blank image which was filled in from one corner.

After thinking about it, it became obvious that the potential call depth
wasn't the distance to a boundary in any direction, but the number of
pixels in the area to be eventually filled in, which could be a big
chunk of the N*N total.

On 17/03/2024 12:46, Michael S wrote:
> On Sat, 16 Mar 2024 11:33:20 +0000
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
>
>> On 16/03/2024 04:11, fir wrote:
>>> i was writing simple editor (something like paint but more custom
>>> for my eventual needs) for big pixel (low resolution) drawing
>>>
>>> it showed in a minute i need a click for changing given drawed area
>>> of of one color into another color (becouse if no someone would
>>> need to do it  by hand pixel by pixel and the need to change color
>>> of given element is very common)
>>>
>>> there is very simple method of doing it - i men i click in given
>>> color pixel then replace it by my color and call the same function
>>> on adjacent 4 pixels (only need check if it is in screen at all and
>>> if the color to change is that initial color
>>>
>>> int RecolorizePixelAndAdjacentOnes(int x, int y, unsigned
>>> old_color, unsigned new_color)
>>> {
>>>   if(old_color == new_color) return 0;
>>>
>>>   if(XYIsInScreen( x,  y))
>>>   if(GetPixelUnsafe(x,y)==old_color)
>>>   {
>>>     SetPixelSafe(x,y,new_color);
>>>     RecolorizePixelAndAdjacentOnes(x+1, y,  old_color, new_color);
>>>     RecolorizePixelAndAdjacentOnes(x-1, y,  old_color, new_color);
>>>     RecolorizePixelAndAdjacentOnes(x, y-1,  old_color, new_color);
>>>     RecolorizePixelAndAdjacentOnes(x, y+1,  old_color, new_color);
>>>     return 1;
>>>   }
>>>
>>>   return 0;
>>> }
>>>
>>> it work but im not quite sure how to estimate the safety of this  -
>>> incidentally as i said i use this editor to low res graphics  like
>>> 200x200 pixels or less, and it is only a toll of private use,
>>> yet i got no time to work on it more than 1-2-3 days i guess but
>>> still
>>>
>>> is there maybe simple way to improve it?
>> >
>> This is a cheap and cheerful fllod fill. And it's easy to get right
>> and shouldn't afall over.
>
> Except I don't understand why it works it all.
> Can't fill area have sub-areas that only connected through diagonal?

Suppose you have an image which is a chessboard. You want to fill one of
the black squares so that it is red.

If you allow connectivity through the diagonals (so two notionally
square pixels that only meet at their corners would be connected), then
all the black squares would turn red, not just one.

Groovy hepcat fir was jivin' in comp.lang.c on Sat, 16 Mar 2024 03:11
pm. It's a cool scene! Dig it.

> i was writing simple editor (something like paint but more custom for
> my eventual needs) for big pixel (low resolution) drawing
>
> it showed in a minute i need a click for changing given drawed area of
> of one color into another color (becouse if no someone would need to
> do
> it by hand pixel by pixel and the need to change color of given
> element is very common)

Not really a C question, but I'll forgive that for now.
What you're looking for (and can easily find on Google, Duck Duck Go
or any other search engine, if you but utilise any of those services)
is called a "flood fill" algorithm.
But a word of advice: recursion can be tricky if you don't understand
the effect. Your method creates a very large recursive chain. This is
best avoided. Try it out "by hand". Get a piece of graph paper and draw
some shapes on it, including some complex ones. Now choose one of these
shapes and choose a starting pixel within this area and try applying
your algorithm. With a coloured pencil, colour in each square as you
go, just as the algorithm would. Also make note of the level of
recursion as you go. I think you'll be amazed. Repeat for all the
shapes on your graph paper.

--

----- Dig the NEW and IMPROVED news sig!! -----

-------------- Shaggy was here! ---------------
Ain't I'm a dawg!!

On Sun, 17 Mar 2024 12:54:34 +0000
bart <bc@freeuk.com> wrote:

> On 17/03/2024 12:46, Michael S wrote:
> > On Sat, 16 Mar 2024 11:33:20 +0000
> > Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
> >
> >> On 16/03/2024 04:11, fir wrote:
> >>> i was writing simple editor (something like paint but more custom
> >>> for my eventual needs) for big pixel (low resolution) drawing
> >>>
> >>> it showed in a minute i need a click for changing given drawed
> >>> area of of one color into another color (becouse if no someone
> >>> would need to do it  by hand pixel by pixel and the need to
> >>> change color of given element is very common)
> >>>
> >>> there is very simple method of doing it - i men i click in given
> >>> color pixel then replace it by my color and call the same function
> >>> on adjacent 4 pixels (only need check if it is in screen at all
> >>> and if the color to change is that initial color
> >>>
> >>> int RecolorizePixelAndAdjacentOnes(int x, int y, unsigned
> >>> old_color, unsigned new_color)
> >>> {
> >>>   if(old_color == new_color) return 0;
> >>>
> >>>   if(XYIsInScreen( x,  y))
> >>>   if(GetPixelUnsafe(x,y)==old_color)
> >>>   {
> >>>     SetPixelSafe(x,y,new_color);
> >>>     RecolorizePixelAndAdjacentOnes(x+1, y,  old_color,
> >>> new_color); RecolorizePixelAndAdjacentOnes(x-1, y,  old_color,
> >>> new_color); RecolorizePixelAndAdjacentOnes(x, y-1,  old_color,
> >>> new_color); RecolorizePixelAndAdjacentOnes(x, y+1,  old_color,
> >>> new_color); return 1;
> >>>   }
> >>>
> >>>   return 0;
> >>> }
> >>>
> >>> it work but im not quite sure how to estimate the safety of this
> >>> - incidentally as i said i use this editor to low res graphics
> >>> like 200x200 pixels or less, and it is only a toll of private use,
> >>> yet i got no time to work on it more than 1-2-3 days i guess but
> >>> still
> >>>
> >>> is there maybe simple way to improve it?
> >> >
> >> This is a cheap and cheerful fllod fill. And it's easy to get right
> >> and shouldn't afall over.
> >
> > Except I don't understand why it works it all.
> > Can't fill area have sub-areas that only connected through
> > diagonal?
>
> Suppose you have an image which is a chessboard. You want to fill one
> of the black squares so that it is red.
>
> If you allow connectivity through the diagonals (so two notionally
> square pixels that only meet at their corners would be connected),
> then all the black squares would turn red, not just one.
>

That's what I want.
Do fir wants something else?

On 17/03/2024 13:15, Michael S wrote:
> On Sun, 17 Mar 2024 12:54:34 +0000
> bart <bc@freeuk.com> wrote:
>
>> On 17/03/2024 12:46, Michael S wrote:
>>> On Sat, 16 Mar 2024 11:33:20 +0000
>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
>>>
>>>> On 16/03/2024 04:11, fir wrote:
>>>>> i was writing simple editor (something like paint but more custom
>>>>> for my eventual needs) for big pixel (low resolution) drawing
>>>>>
>>>>> it showed in a minute i need a click for changing given drawed
>>>>> area of of one color into another color (becouse if no someone
>>>>> would need to do it  by hand pixel by pixel and the need to
>>>>> change color of given element is very common)
>>>>>
>>>>> there is very simple method of doing it - i men i click in given
>>>>> color pixel then replace it by my color and call the same function
>>>>> on adjacent 4 pixels (only need check if it is in screen at all
>>>>> and if the color to change is that initial color
>>>>>
>>>>> int RecolorizePixelAndAdjacentOnes(int x, int y, unsigned
>>>>> old_color, unsigned new_color)
>>>>> {
>>>>>   if(old_color == new_color) return 0;
>>>>>
>>>>>   if(XYIsInScreen( x,  y))
>>>>>   if(GetPixelUnsafe(x,y)==old_color)
>>>>>   {
>>>>>     SetPixelSafe(x,y,new_color);
>>>>>     RecolorizePixelAndAdjacentOnes(x+1, y,  old_color,
>>>>> new_color); RecolorizePixelAndAdjacentOnes(x-1, y,  old_color,
>>>>> new_color); RecolorizePixelAndAdjacentOnes(x, y-1,  old_color,
>>>>> new_color); RecolorizePixelAndAdjacentOnes(x, y+1,  old_color,
>>>>> new_color); return 1;
>>>>>   }
>>>>>
>>>>>   return 0;
>>>>> }
>>>>>
>>>>> it work but im not quite sure how to estimate the safety of this
>>>>> - incidentally as i said i use this editor to low res graphics
>>>>> like 200x200 pixels or less, and it is only a toll of private use,
>>>>> yet i got no time to work on it more than 1-2-3 days i guess but
>>>>> still
>>>>>
>>>>> is there maybe simple way to improve it?
>>>> >
>>>> This is a cheap and cheerful fllod fill. And it's easy to get right
>>>> and shouldn't afall over.
>>>
>>> Except I don't understand why it works it all.
>>> Can't fill area have sub-areas that only connected through
>>> diagonal?
>>
>> Suppose you have an image which is a chessboard. You want to fill one
>> of the black squares so that it is red.
>>
>> If you allow connectivity through the diagonals (so two notionally
>> square pixels that only meet at their corners would be connected),
>> then all the black squares would turn red, not just one.
>>
>
> That's what I want.
> Do fir wants something else?
>

His algorithm is the same as that presented in my textbook, where it is
called FloodFill4.

If I reread the notes I see now the significance of the '4', as it talks
about 4-connected and 8-connected versions.

Presumably you want the 8-connected version, which will have 4 extra
calls for the pixels at each corner.