On Sat, 16 Mar 2024 18:21:38 GMT
scott@slp53.sl.home (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.
>
>

As a matter of fact, David Brown was not able to reason about depth of
recursion in fir's code. And you answered David's post without spotting
his mistake.
Now, I don't know if you didn't spot his mistake because you didn't read
this part of his message or because for you too it was hard to reason
about depth of recursion.

On Sun, 17 Mar 2024 13:23:55 +0000
bart <bc@freeuk.com> wrote:

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

'4' variant does not appear useful for changing colors of drawn shapes,
like lines or circles. Nor would it work for changing color of text
except when font is unusually bold.

bart <bc@freeuk.com> writes:

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

s/my/his/?

--
Ben.

On Sat, 16 Mar 2024 11:33:20 +0000, 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.
>
> Recursion make programs harder to reason about and prove correct.

I would have said that those unfamiliar with the concept of recursion
have a harder time reasoning about the effects of recursion, or proving
their recursive code correct.

Take fir's example code above; a simple single call to
RecolorizePixelAndAdjacentOnes() will effectively recolour the
origin cell multiple times, because of how the recursion is handled.

As an example:
RecolorizePixelAndAdjacentOnes(0,0,1 2)
will
SetPixelSafe(0,0,2);
then invoke
RecolorizePixelAndAdjacentOnes(1,0,1 2)
which will
SetPixelSafe(1,0,2)
and subsequently invoke
...
RecolorizePixelAndAdjacentOnes(0,0,1 2)
which will
SetPixelSafe(0,0,2);
and then invoke
RecolorizePixelAndAdjacentOnes(1,0,1 2)
etc.

[snip]

--
Lew Pitcher
"In Skills We Trust"

On 16/03/2024 15:09, Malcolm McLean wrote:
> 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?

> And I need to run some tests, don't I?
>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int floodfill_r(unsigned char *grey, int width, int height, int x, int y,
unsigned char target, unsigned char dest)
{ if (x < 0 || x >= width || y < 0 || y >= height)
return 0;
if (grey[y*width+x] != target)
return 0;
grey[y*width+x] = dest;
floodfill_r(grey, width, height, x - 1, y, target, dest);
floodfill_r(grey, width, height, x + 1, y, target, dest);
floodfill_r(grey, width, height, x, y - 1, target, dest);
floodfill_r(grey, width, height, x, y + 1, target, dest);

return 0;
}

/**
Floodfill4 - floodfill, 4 connectivity.

@param[in,out] grey - the image (formally it's greyscale but it could be
binary or indexed)
@param width - image width
@param height - image height
@param x - seed point x
@param y - seed point y
@param target - the colour to flood
@param dest - the colur to replace it by.
@returns Number of pixels flooded.
*/
int floodfill4(unsigned char *grey, int width, int height, int x, int y,
unsigned char target, unsigned char dest)
{ int *qx = 0;
int *qy = 0;
int qN = 0;
int qpos = 0;
int qcapacity = 0;
int wx, wy;
int ex, ey;
int tx, ty;
int ix;
int *temp;
int answer = 0;

if(grey[y * width + x] != target)
return 0;
qx = malloc(width * sizeof(int));
qy = malloc(width * sizeof(int));
if(qx == 0 || qy == 0)
goto error_exit;
qcapacity = width;
qx[qpos] = x;
qy[qpos] = y;
qN = 1;

while(qN != 0)
{
tx = qx[qpos];
ty = qy[qpos];
qpos++;
qN--;

if(qpos == 256)
{
memmove(qx, qx + 256, qN*sizeof(int));
memmove(qy, qy + 256, qN*sizeof(int));
qpos = 0;
}
if(grey[ty*width+tx] != target)
continue;
wx = tx;
wy = ty;
while(wx >= 0 && grey[wy*width+wx] == target)
wx--;
wx++;
ex = tx;
ey = ty;
while(ex < width && grey[ey*width+ex] == target)
ex++;
ex--;

for(ix=wx;ix<=ex;ix++)
{
grey[ty*width+ix] = dest;
answer++;
}

if(ty > 0)
for(ix=wx;ix<=ex;ix++)
{
if(grey[(ty-1)*width+ix] == target)
{
if(qpos + qN == qcapacity)
{
temp = realloc(qx, (qcapacity + width) * sizeof(int));
if(temp == 0)
goto error_exit;
qx = temp;
temp = realloc(qy, (qcapacity + width) * sizeof(int));
if(temp == 0)
goto error_exit;
qy = temp;
qcapacity += width;
}
qx[qpos+qN] = ix;
qy[qpos+qN] = ty-1;
qN++;
}
}
if(ty < height -1)
for(ix=wx;ix<=ex;ix++)
{
if(grey[(ty+1)*width+ix] == target)
{
if(qpos + qN == qcapacity)
{
temp = realloc(qx, (qcapacity + width) * sizeof(int));
if(temp == 0)
goto error_exit;
qx = temp;
temp = realloc(qy, (qcapacity + width) * sizeof(int));
if(temp == 0)
goto error_exit;
qy = temp;
qcapacity += width;
}
qx[qpos+qN] = ix;
qy[qpos+qN] = ty+1;
qN++;
}
}
}

free(qx);
free(qy);

return answer;
error_exit:
free(qx);
free(qy);
return -1;
}

int main(void)
{ unsigned char *image;
clock_t tick, tock;
int i;

image = malloc(100 * 100);
tick = clock();
for (i = 0 ; i < 10000; i++)
{
memset(image, 0, 100 * 100);
floodfill_r(image, 100, 100, 50, 50, 0, 1);
}
tock = clock();
printf("floodfill_r %g\n", ((double)(tock - tick))/CLOCKS_PER_SEC);

tick = clock();
for (i = 0 ; i < 10000; i++)
{
memset(image, 0, 100 * 100);
floodfill4(image, 100, 100, 50, 50, 0, 1);
}
tock = clock();
printf("floodfill4 %g\n", ((double)(tock - tick))/CLOCKS_PER_SEC);

return 0;
}

Let's give it a whirl

malcolm@Malcolms-iMac cscratch % gcc -O3 testfloodfill.c
malcolm@Malcolms-iMac cscratch % ./a.out
floodfill_r 1.69274
floodfill4 0.336705

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

On 17/03/2024 14:27, Lew Pitcher wrote:
> On Sat, 16 Mar 2024 11:33:20 +0000, 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.
>>
>> Recursion make programs harder to reason about and prove correct.
>
> I would have said that those unfamiliar with the concept of recursion
> have a harder time reasoning about the effects of recursion, or proving
> their recursive code correct.
>
> Take fir's example code above; a simple single call to
> RecolorizePixelAndAdjacentOnes() will effectively recolour the
> origin cell multiple times, because of how the recursion is handled.

I don't think so. It may look at the original cell, but it will only
recolour it (and recursively process its neighbours) if the colour
hasn't yet changed to the new one.

If I take a 100x100 image with 10,000 cells, which all have to be filled
to the new colour, then SetPixelSafe is called exactly 10,000 times.

The problem is that most of the work is done along a 10,000-deep chain
of nested calls.

On Sun, 17 Mar 2024 14:56:34 +0000
Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:

> On 16/03/2024 15:09, Malcolm McLean wrote:
> > 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?
> >
>
> > And I need to run some tests, don't I?
> >
>
> Let's give it a whirl
>

<snip>

> malcolm@Malcolms-iMac cscratch % gcc -O3 testfloodfill.c
> malcolm@Malcolms-iMac cscratch % ./a.out
> floodfill_r 1.69274
> floodfill4 0.336705
>
>

Now try the case in which original recursion is particularly deep.
Something like that:
*.***.**
*.*.*.*.
*.*.*.*.
*.*.*.*.
*.*.*.*.
*.*.*.*.
*.*.*.*.
***.***.

On Sun, 17 Mar 2024 14:56:34 +0000
Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:

> On 16/03/2024 15:09, Malcolm McLean wrote:
> > 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?
> >
>
> > And I need to run some tests, don't I?
> >
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> #include <time.h>
>
> int floodfill_r(unsigned char *grey, int width, int height, int x,
> int y, unsigned char target, unsigned char dest)
> {
> if (x < 0 || x >= width || y < 0 || y >= height)
> return 0;
> if (grey[y*width+x] != target)
> return 0;
> grey[y*width+x] = dest;
> floodfill_r(grey, width, height, x - 1, y, target, dest);
> floodfill_r(grey, width, height, x + 1, y, target, dest);
> floodfill_r(grey, width, height, x, y - 1, target, dest);
> floodfill_r(grey, width, height, x, y + 1, target, dest);
>
> return 0;
> }
>
> /**
> Floodfill4 - floodfill, 4 connectivity.
>
> @param[in,out] grey - the image (formally it's greyscale but it
> could be binary or indexed)
> @param width - image width
> @param height - image height
> @param x - seed point x
> @param y - seed point y
> @param target - the colour to flood
> @param dest - the colur to replace it by.
> @returns Number of pixels flooded.
> */
> int floodfill4(unsigned char *grey, int width, int height, int x, int
> y, unsigned char target, unsigned char dest)
> {
> int *qx = 0;
> int *qy = 0;
> int qN = 0;
> int qpos = 0;
> int qcapacity = 0;
> int wx, wy;
> int ex, ey;
> int tx, ty;
> int ix;
> int *temp;
> int answer = 0;
>
> if(grey[y * width + x] != target)
> return 0;
> qx = malloc(width * sizeof(int));
> qy = malloc(width * sizeof(int));
> if(qx == 0 || qy == 0)
> goto error_exit;
> qcapacity = width;
> qx[qpos] = x;
> qy[qpos] = y;
> qN = 1;
>
> while(qN != 0)
> {
> tx = qx[qpos];
> ty = qy[qpos];
> qpos++;
> qN--;
>
> if(qpos == 256)
> {
> memmove(qx, qx + 256, qN*sizeof(int));
> memmove(qy, qy + 256, qN*sizeof(int));
> qpos = 0;
> }
> if(grey[ty*width+tx] != target)
> continue;
> wx = tx;
> wy = ty;
> while(wx >= 0 && grey[wy*width+wx] == target)
> wx--;
> wx++;
> ex = tx;
> ey = ty;
> while(ex < width && grey[ey*width+ex] == target)
> ex++;
> ex--;
>
>
> for(ix=wx;ix<=ex;ix++)
> {
> grey[ty*width+ix] = dest;
> answer++;
> }
>
> if(ty > 0)
> for(ix=wx;ix<=ex;ix++)
> {
> if(grey[(ty-1)*width+ix] == target)
> {
> if(qpos + qN == qcapacity)
> {
> temp = realloc(qx, (qcapacity + width) * sizeof(int));
> if(temp == 0)
> goto error_exit;
> qx = temp;
> temp = realloc(qy, (qcapacity + width) * sizeof(int));
> if(temp == 0)
> goto error_exit;
> qy = temp;
> qcapacity += width;
> }
> qx[qpos+qN] = ix;
> qy[qpos+qN] = ty-1;
> qN++;
> }
> }
> if(ty < height -1)
> for(ix=wx;ix<=ex;ix++)
> {
> if(grey[(ty+1)*width+ix] == target)
> {
> if(qpos + qN == qcapacity)
> {
> temp = realloc(qx, (qcapacity + width) * sizeof(int));
> if(temp == 0)
> goto error_exit;
> qx = temp;
> temp = realloc(qy, (qcapacity + width) * sizeof(int));
> if(temp == 0)
> goto error_exit;
> qy = temp;
> qcapacity += width;
> }
> qx[qpos+qN] = ix;
> qy[qpos+qN] = ty+1;
> qN++;
> }
> }
> }
>
> free(qx);
> free(qy);
>
> return answer;
> error_exit:
> free(qx);
> free(qy);
> return -1;
> }
>
> int main(void)
> {
> unsigned char *image;
> clock_t tick, tock;
> int i;
>
> image = malloc(100 * 100);
> tick = clock();
> for (i = 0 ; i < 10000; i++)
> {
> memset(image, 0, 100 * 100);
> floodfill_r(image, 100, 100, 50, 50, 0, 1);
> }
> tock = clock();
> printf("floodfill_r %g\n", ((double)(tock -
> tick))/CLOCKS_PER_SEC);
>
> tick = clock();
> for (i = 0 ; i < 10000; i++)
> {
> memset(image, 0, 100 * 100);
> floodfill4(image, 100, 100, 50, 50, 0, 1);
> }
> tock = clock();
> printf("floodfill4 %g\n", ((double)(tock - tick))/CLOCKS_PER_SEC);
>
> return 0;
> }
>
>
> Let's give it a whirl
>
> malcolm@Malcolms-iMac cscratch % gcc -O3 testfloodfill.c
> malcolm@Malcolms-iMac cscratch % ./a.out
> floodfill_r 1.69274
> floodfill4 0.336705
>
>

I find your performance measurement non-decisive for two reasons:
(1) because your test case is too trivial and probably uncharacteristic
and
(2) because recursive variant could be trivially rewritten in a way
that reduces # of stack memory accesses by factor of 2 or 3.
Like that:

struct recursive_context_t {
unsigned char *grey;
int width, height;
unsigned char target, dest;
};

static void floodfill_r_core(const struct recursive_context_t* context,
int x, int y) {
if (x < 0 || x >= context->width || y < 0 || y >= context->height)
return;
if (context->grey[y*context->width+x] == context->target) {
context->grey[y*context->width+x] = context->dest;
floodfill_r_core(context, x - 1, y);
floodfill_r_core(context, x + 1, y);
floodfill_r_core(context, x, y - 1);
floodfill_r_core(context, x, y + 1);
}
}

int floodfill_r(
unsigned char *grey,
int width, int height,
int x, int y,
unsigned char target, unsigned char dest)
{ if (x < 0 || x >= width || y < 0 || y >= height)
return 0;
if (grey[y*width+x] != target)
return 0;
struct recursive_context_t context = {
.grey = grey,
.width = width,
.height = height,
.target = target,
.dest = dest,
};
floodfill_r_core(&context, x, y);
return 1;
}

On 16/03/2024 16:09, Malcolm McLean wrote:
> 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?

I don't know who "David Borwn" might be, nor what "ture" means. If you
can't type, and can't spell, then at least pay the group the respect of
using a spell-checker.

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

It is badly designed code. It is a jumble of wildly different concepts,
thrown together in one huge function with no structure or organisation,
and with meaningless names for the variables and absurd names for the
parameters.

The OP's code is simple and obvious, as is its correctness (assuming
reasonable definitions of the pixel access and setting functions) and
its time and space requirements. Yours is not.

Your algorithm could be used in a proper implementation, with separate
functions to handle the different parts (such as the stack). The
algorithm itself is not bad, it's the implementation that is the main
problem.

>
> But the naive recursive algorithm is O(N) (N = pixels to flood), and
> inherently we can't beat that without special hardware.

Assuming you are measuring the number of pixels read or written here,
then that is, I think, correct.

> The recursive
> one tends to be slow because calls are expensive.

Yes, I agree that recursion can be slow (unless it is simple enough for
the compiler to turn it into a loop). And it typically takes more stack
space than you'd need for a dedicated queue. But whether or not that
makes a significant difference depends on the code in question, and how
much work you are doing within the code. If step of the algorithm takes
a lot of time anyway, the call overhead will be of less relevance.

I would expect that your code would be several times faster than the
OP's, with similar scaling. But the OP's is understandable and easily
seen to be correct, unlike yours, and correctness trumps speed every time.

And starting from a correct recursive version, it's possible to improve
on it in many ways while retaining correctness.

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

True.

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

I have no idea if your code is "out of date" or not. It seems to be
written for images consisting of unsigned chars, so I a not sure it was
ever designed for real-world images.

What is clear is that you have taken an okay algorithm - not state of
the art, but not the worst - and made a dog's breakfast of an
implementation in your attempts to micro-optimise. This means you have
code that can't be easily analysed or seen to be correct, cannot be
improved algorithmically, and cannot be expanded or gain new features
without a massive re-write.

> And I need to run some tests, don't I?
>

If you like.

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

<https://gprivate.com/6a2yp>

I don't know if it is fair to call them a /lot/ more advanced, but
certainly a bit more advanced. And certainly better implementations are
possible.

On Sun, 17 Mar 2024 14:10:15 +0000
Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> bart <bc@freeuk.com> writes:
>
> > His algorithm is the same as that presented in my textbook, where it is
> > called FloodFill4.
>
> s/my/his/?

What is mentioned in <ut4v4r$32mgb$1@dont-email.me> : "I've just looked in
my Computer Graphics Principles and Practice book" .

On 17/03/2024 11: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.
>

I also have dyslexia. I am dependent on a spell checker to spell
accurately. And that is one of the reasons why Malcolm should do a
better job of writing accurately - it is much easier for others to read
posts when the spelling and the grammar is correct. I would, of course,
also like him to do a better job at his grammar, but using a
spell-checker is so simple and low-cost that it is inexcusable for him
not to use one.

I have nothing bad to say about people who can't spell well, or who
can't type well, and I have nothing but respect for people who are
trying their best to write in a second (or third, or more) language.

But Malcolm is a native English speaker with a degree in English. He is
not dyslexic (or at least, the mistakes he makes are not typical signs
of dyslexia). He is simply a poor typist and too lazy to make an effort
to correct his errors.

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

On 17/03/2024 14:37, Michael S wrote:
> On Sun, 17 Mar 2024 13:23:55 +0000
> bart <bc@freeuk.com> wrote:
>
>> 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.
>>
>>
>
> '4' variant does not appear useful for changing colors of drawn shapes,
> like lines or circles. Nor would it work for changing color of text
> except when font is unusually bold.
>

An 8-connected flood fill is typically too much, and a 4-connected flood
fill is often too little. Neither is perfect for all cases, but I think
the 4-connected version is the most commonly used.

And as they stand, both are useless for images that are come from
realistic pictures (as distinct from drawings), since real colours
change gradually.

That's why graphics programs have feathered selection and masking, fuzzy
fills, and so on.

On 2024-03-17, Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
> The convetional wisdom is the opposite, But here, conventional wisdom
> fails. Because heaps are unlimited whilst stacks are not.

The strawman, absolutist conventional wisdom that "recursion is always
easier to analyze than iteration" is wrong in the first place.

Any program graph based on nothing but IF and GOTO primitives can be
mechanically transliterated into a (tail) recursive structure that has
the same shape, and is no easier to understand.

Your point is not very well made, though. Even though recursion may run
into a resource limit, its structure can still help analyze the logic of
the algorithm apart from that resource issue. The resource issue can be
separately analyzed and provisions made for the algorithm to handle the
required inputs, and reject others.

Most algorithms (especially ones working with all inputs in memory)
are constrained by resources. The iterative version of that image
processing algorithm might handle larger images than the recursive
one, but there are yet image sizes it won't handle.

The idea of calling algorithm implementations "incorrect" if they have
any limitations on their input sizes and such isn't particularly
informative or useful.

Obviously it is incorrect if something has limitations, and is used
in such a way that they are exceeded. E.g. the C <int> + <int>
operation when a result is implied that is beyond INT_MIN or INT_MAX.
Oops, + is not "correct"; don't use it!

Now, there is a bit of value in algorithms that will successfully
operate on any object that was successfully fit into memory. Do
these really exist though? Pretty much any algorithm implementation
requires some space to do its work, even if that space is small and
fixed. It's possible that the input fit into memory, yet that small and
fixed amount of space is not available.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

On Sun, 17 Mar 2024 18:25:20 +0200
Michael S <already5chosen@yahoo.com> wrote:

> On Sun, 17 Mar 2024 14:56:34 +0000
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
>
> > On 16/03/2024 15:09, Malcolm McLean wrote:
> > > 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?
> >
> > > And I need to run some tests, don't I?
> > >
> > #include <stdio.h>
> > #include <stdlib.h>
> > #include <string.h>
> > #include <time.h>
> >
> > int floodfill_r(unsigned char *grey, int width, int height, int x,
> > int y, unsigned char target, unsigned char dest)
> > {
> > if (x < 0 || x >= width || y < 0 || y >= height)
> > return 0;
> > if (grey[y*width+x] != target)
> > return 0;
> > grey[y*width+x] = dest;
> > floodfill_r(grey, width, height, x - 1, y, target, dest);
> > floodfill_r(grey, width, height, x + 1, y, target, dest);
> > floodfill_r(grey, width, height, x, y - 1, target, dest);
> > floodfill_r(grey, width, height, x, y + 1, target, dest);
> >
> > return 0;
> > }
> >
> > /**
> > Floodfill4 - floodfill, 4 connectivity.
> >
> > @param[in,out] grey - the image (formally it's greyscale but it
> > could be binary or indexed)
> > @param width - image width
> > @param height - image height
> > @param x - seed point x
> > @param y - seed point y
> > @param target - the colour to flood
> > @param dest - the colur to replace it by.
> > @returns Number of pixels flooded.
> > */
> > int floodfill4(unsigned char *grey, int width, int height, int x,
> > int y, unsigned char target, unsigned char dest)
> > {
> > int *qx = 0;
> > int *qy = 0;
> > int qN = 0;
> > int qpos = 0;
> > int qcapacity = 0;
> > int wx, wy;
> > int ex, ey;
> > int tx, ty;
> > int ix;
> > int *temp;
> > int answer = 0;
> >
> > if(grey[y * width + x] != target)
> > return 0;
> > qx = malloc(width * sizeof(int));
> > qy = malloc(width * sizeof(int));
> > if(qx == 0 || qy == 0)
> > goto error_exit;
> > qcapacity = width;
> > qx[qpos] = x;
> > qy[qpos] = y;
> > qN = 1;
> >
> > while(qN != 0)
> > {
> > tx = qx[qpos];
> > ty = qy[qpos];
> > qpos++;
> > qN--;
> >
> > if(qpos == 256)
> > {
> > memmove(qx, qx + 256, qN*sizeof(int));
> > memmove(qy, qy + 256, qN*sizeof(int));
> > qpos = 0;
> > }
> > if(grey[ty*width+tx] != target)
> > continue;
> > wx = tx;
> > wy = ty;
> > while(wx >= 0 && grey[wy*width+wx] == target)
> > wx--;
> > wx++;
> > ex = tx;
> > ey = ty;
> > while(ex < width && grey[ey*width+ex] == target)
> > ex++;
> > ex--;
> >
> >
> > for(ix=wx;ix<=ex;ix++)
> > {
> > grey[ty*width+ix] = dest;
> > answer++;
> > }
> >
> > if(ty > 0)
> > for(ix=wx;ix<=ex;ix++)
> > {
> > if(grey[(ty-1)*width+ix] == target)
> > {
> > if(qpos + qN == qcapacity)
> > {
> > temp = realloc(qx, (qcapacity + width) * sizeof(int));
> > if(temp == 0)
> > goto error_exit;
> > qx = temp;
> > temp = realloc(qy, (qcapacity + width) * sizeof(int));
> > if(temp == 0)
> > goto error_exit;
> > qy = temp;
> > qcapacity += width;
> > }
> > qx[qpos+qN] = ix;
> > qy[qpos+qN] = ty-1;
> > qN++;
> > }
> > }
> > if(ty < height -1)
> > for(ix=wx;ix<=ex;ix++)
> > {
> > if(grey[(ty+1)*width+ix] == target)
> > {
> > if(qpos + qN == qcapacity)
> > {
> > temp = realloc(qx, (qcapacity + width) * sizeof(int));
> > if(temp == 0)
> > goto error_exit;
> > qx = temp;
> > temp = realloc(qy, (qcapacity + width) * sizeof(int));
> > if(temp == 0)
> > goto error_exit;
> > qy = temp;
> > qcapacity += width;
> > }
> > qx[qpos+qN] = ix;
> > qy[qpos+qN] = ty+1;
> > qN++;
> > }
> > }
> > }
> >
> > free(qx);
> > free(qy);
> >
> > return answer;
> > error_exit:
> > free(qx);
> > free(qy);
> > return -1;
> > }
> >
> > int main(void)
> > {
> > unsigned char *image;
> > clock_t tick, tock;
> > int i;
> >
> > image = malloc(100 * 100);
> > tick = clock();
> > for (i = 0 ; i < 10000; i++)
> > {
> > memset(image, 0, 100 * 100);
> > floodfill_r(image, 100, 100, 50, 50, 0, 1);
> > }
> > tock = clock();
> > printf("floodfill_r %g\n", ((double)(tock -
> > tick))/CLOCKS_PER_SEC);
> >
> > tick = clock();
> > for (i = 0 ; i < 10000; i++)
> > {
> > memset(image, 0, 100 * 100);
> > floodfill4(image, 100, 100, 50, 50, 0, 1);
> > }
> > tock = clock();
> > printf("floodfill4 %g\n", ((double)(tock -
> > tick))/CLOCKS_PER_SEC);
> >
> > return 0;
> > }
> >
> >
> > Let's give it a whirl
> >
> > malcolm@Malcolms-iMac cscratch % gcc -O3 testfloodfill.c
> > malcolm@Malcolms-iMac cscratch % ./a.out
> > floodfill_r 1.69274
> > floodfill4 0.336705
> >
> >
>
> I find your performance measurement non-decisive for two reasons:
> (1) because your test case is too trivial and probably
> uncharacteristic and
> (2) because recursive variant could be trivially rewritten in a way
> that reduces # of stack memory accesses by factor of 2 or 3.
> Like that:
>
> struct recursive_context_t {
> unsigned char *grey;
> int width, height;
> unsigned char target, dest;
> };
>
> static void floodfill_r_core(const struct recursive_context_t*
> context, int x, int y) {
> if (x < 0 || x >= context->width || y < 0 || y >= context->height)
> return;
> if (context->grey[y*context->width+x] == context->target) {
> context->grey[y*context->width+x] = context->dest;
> floodfill_r_core(context, x - 1, y);
> floodfill_r_core(context, x + 1, y);
> floodfill_r_core(context, x, y - 1);
> floodfill_r_core(context, x, y + 1);
> }
> }
>
> int floodfill_r(
> unsigned char *grey,
> int width, int height,
> int x, int y,
> unsigned char target, unsigned char dest)
> {
> if (x < 0 || x >= width || y < 0 || y >= height)
> return 0;
> if (grey[y*width+x] != target)
> return 0;
> struct recursive_context_t context = {
> .grey = grey,
> .width = width,
> .height = height,
> .target = target,
> .dest = dest,
> };
> floodfill_r_core(&context, x, y);
> return 1;
> }
>
>

On 17/03/2024 16:45, David Brown wrote:
> On 16/03/2024 16:09, Malcolm McLean wrote:
>>
> The OP's code is simple and obvious, as is its correctness (assuming
> reasonable definitions of the pixel access and setting functions) and
> its time and space requirements.  Yours is not.
>
Except it is not. You didn't give the right answer for the space
requirements.
> Your algorithm could be used in a proper implementation, with separate
> functions to handle the different parts (such as the stack).  The
> algorithm itself is not bad, it's the implementation that is the main
> problem.
>
It's better to have one function. Subroutines have a way of getting lost.>
> I have no idea if your code is "out of date" or not.  It seems to be
> written for images consisting of unsigned chars, so I a not sure it was
> ever designed for real-world images.
>
It was written a long time ago. But it is writeen in a conservative
subset of ANSI C, and so of course it still works, and should work for
along time to come. But the 256 integer queue tweak might be out of
date. And cache use is far more important now that it was on big
processors. So it might be a bit long in the tooth.

And it's part of the binary image library, and it's designed for marking
8- or 4- connected sections of those images by setting the 1 to a
different value. And then further processing. The binary images are
often derived from photographs by Otsu thresholding, which is in the
same library. But they aren't usually meant for human viewing by end users.
>
> I don't know if it is fair to call them a /lot/ more advanced, but
> certainly a bit more advanced.  And certainly better implementations are
> possible.
>
And are you going to be constructive or not? Suggest one which might be
better? Even implement it?

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

On 3/16/2024 1:29 PM, Chris M. Thomasson wrote:
> 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...

Gaining the iterative solution from a working recursive solution is the
fun part!

:^)

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

Spiros Bousbouras <spibou@gmail.com> writes:

> On Sun, 17 Mar 2024 14:10:15 +0000
> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>> bart <bc@freeuk.com> writes:
>>
>> > His algorithm is the same as that presented in my textbook, where it is
>> > called FloodFill4.
>>
>> s/my/his/?
>
> What is mentioned in <ut4v4r$32mgb$1@dont-email.me> : "I've just looked in
> my Computer Graphics Principles and Practice book" .

That context seems to have got lost, and MM was quoting from his
textbook (or book at any rate). Thanks for pointing out the missing
context.

--
Ben.

On 17/03/2024 22:14, Ben Bacarisse wrote:
> Spiros Bousbouras <spibou@gmail.com> writes:
>
>> On Sun, 17 Mar 2024 14:10:15 +0000
>> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>>> bart <bc@freeuk.com> writes:
>>>
>>>> His algorithm is the same as that presented in my textbook, where it is
>>>> called FloodFill4.
>>>
>>> s/my/his/?
>>
>> What is mentioned in <ut4v4r$32mgb$1@dont-email.me> : "I've just looked in
>> my Computer Graphics Principles and Practice book" .
>
> That context seems to have got lost, and MM was quoting from his
> textbook (or book at any rate). Thanks for pointing out the missing
> context.
>

'His' algorithm was the one in the OP posted by fir.

'My' (bart's) textbook was the CGPP book by Foley, van Dam, et al.

On 17/03/2024 19:28, Malcolm McLean wrote:
> On 17/03/2024 16:45, David Brown wrote:
>> On 16/03/2024 16:09, Malcolm McLean wrote:
>>>
>> The OP's code is simple and obvious, as is its correctness (assuming
>> reasonable definitions of the pixel access and setting functions) and
>> its time and space requirements.  Yours is not.
>>
> Except it is not. You didn't give the right answer for the space
> requirements.

Unfortunately, I am still fallible - /easier/ does not mean I'll get it
right :-( And I apologise for unhelpfully rushing that and getting it
wrong.

However, I stand by my claim that the recursive version is much easier
to analyse.

>> Your algorithm could be used in a proper implementation, with separate
>> functions to handle the different parts (such as the stack).  The
>> algorithm itself is not bad, it's the implementation that is the main
>> problem.
>>
> It's better to have one function. Subroutines have a way of getting lost.>

Seriously? "Subroutines get lost" ? So your answer is to put all your
ideas in a mixer and scrunch them up until any semblance of logic and
structure is lost, and the code works (if it does) by trial and error?
And then the whole mess is cut-and-paste duplicated - along with any
subtle bugs it might have - for 8-connected version. And that's better,
in your eyes, than re-using code?

>> I have no idea if your code is "out of date" or not.  It seems to be
>> written for images consisting of unsigned chars, so I a not sure it
>> was ever designed for real-world images.
>>
> It was written a long time ago. But it is writeen in a conservative
> subset of ANSI C, and so of course it still works, and should work for
> along time to come. But the 256 integer queue tweak might be out of
> date. And cache use is far more important now that it was on big
> processors. So it might be a bit long in the tooth.
>

I have been most interested in being able to be sure the algorithm is
correct, rather than considering its absolute (rather than "big O")
efficiency in different systems. It is certainly the case that cache
considerations are more relevant now than they used to be on many
systems. And for working on PC's, you would likely dispense with your
growing stack entirely and simply allocate a queue big enough for every
pixel in the image.

> And it's part of the binary image library, and it's designed for marking
> 8- or 4- connected sections of those images by setting the 1 to a
> different value. And then further processing. The binary images are
> often derived from photographs by Otsu thresholding, which is in the
> same library. But they aren't usually meant for human viewing by end users.
>>
>> I don't know if it is fair to call them a /lot/ more advanced, but
>> certainly a bit more advanced.  And certainly better implementations
>> are possible.
>>
> And are you going to be constructive or not? Suggest one which might be
> better? Even implement it?
>

I suggested separating the code into functions - that is /definitely/
constructive. I suggested using sensible names for parameters and
variables (well, the suggestion was implied by my criticism).

And I am also suggesting now that you allocate a queue that is big
enough for every pixel in the image. Much of what you don't touch of
that space, will probably never be physically allocated by the OS,
depending on page sizes and free memory.

And I would also suggest you drop the requirement for coding in an
ancient tongue, and instead switch to reasonably modern C. Make
abstractions for the types and the access functions - it will make the
code far easier to follow, easier to show correct, and easier to modify
and reuse, without affecting efficiency at run-time.

On 18/03/2024 06:58, David Brown wrote:
> On 17/03/2024 19:28, Malcolm McLean wrote:
>> On 17/03/2024 16:45, David Brown wrote:
>>> On 16/03/2024 16:09, Malcolm McLean wrote:
>>>>
>>> The OP's code is simple and obvious, as is its correctness (assuming
>>> reasonable definitions of the pixel access and setting functions) and
>>> its time and space requirements.  Yours is not.
>>>
>> Except it is not. You didn't give the right answer for the space
>> requirements.
>
> Unfortunately, I am still fallible - /easier/ does not mean I'll get it
> right :-(  And I apologise for unhelpfully rushing that and getting it
> wrong.
>
> However, I stand by my claim that the recursive version is much easier
> to analyse.
>
I this case it s very short code and easy to see that it is right, so a
win for recursion. Except that it is only right if the stack is bigger
than N/2 calls deep, where N is the number fo pixels in the image. 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.

>> It's better to have one function. Subroutines have a way of getting
>> lost.>
>
> Seriously?  "Subroutines get lost" ?  So your answer is to put all your
> ideas in a mixer and scrunch them up until any semblance of logic and
> structure is lost, and the code works (if it does) by trial and error?
> And then the whole mess is cut-and-paste duplicated - along with any
> subtle bugs it might have - for 8-connected version.  And that's better,
> in your eyes, than re-using code?
>
Exactly. If a routine ia leaf, you can cut and paste it and use it where
you will. If you have to take subroutines, you've got to explore the
code to understand what you neeed to take, then you have to out them
somewhere. So it's better to keep routines leaf is possible and fold a
few trivial operations into the code body, even if ideally they would be
subroutines. And I understand these trade offs. >
> I have been most interested in being able to be sure the algorithm is
> correct, rather than considering its absolute (rather than "big O")
> efficiency in different systems.  It is certainly the case that cache
> considerations are more relevant now than they used to be on many
> systems.  And for working on PC's, you would likely dispense with your
> growing stack entirely and simply allocate a queue big enough for every
> pixel in the image.
>
That is an idea. But a bit extravanagant. I'd like to try to work out
how much quue s actually used in typical as well as worst case.
>
> I suggested separating the code into functions - that is /definitely/
> constructive.  I suggested using sensible names for parameters and
> variables (well, the suggestion was implied by my criticism).
>
> And I am also suggesting now that you allocate a queue that is big
> enough for every pixel in the image.  Much of what you don't touch of
> that space, will probably never be physically allocated by the OS,
> depending on page sizes and free memory.
>
> And I would also suggest you drop the requirement for coding in an
> ancient tongue, and instead switch to reasonably modern C.  Make
> abstractions for the types and the access functions - it will make the
> code far easier to follow, easier to show correct, and easier to modify
> and reuse, without affecting efficiency at run-time.
>
>
And of course the entire binary image library has a consistent style.
And we don't want the user mee=ssing about with writing his own getpixel
/ setpixel functions, thouhg there would be a case for that for a
geneeral purpose flood fill.
--
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm

Michael S <already5chosen@yahoo.com> writes:

>> 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;
>>> }

[...]

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

It is customary in raster graphics to count pixels as adjacent
only if they share an edge, not if they just share a corner.
Usually that gives better results; the exceptions tend to need
special handling anyway and not just connecting through
diagonals.

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?

The claim is that recursion always makes programs harder to reason
about and prove correct. It's easy to find examples that show
recursion does not always makes programs harder to reason about and
prove correct.

> I personally find recursion hard work and errors much harder to
> debug.

Most likely that's because you haven't had the relevant background
in learning how to program in a functional style. That matches my
own experience: it was only after learning how to write programs in
a functional style that I really started to appreciate the benefits
of using recursion, and to understand how to write and reason about
recursive programs.

> It is also becomes much more important to show that will not cause
> stack overflow.

In most cases it's enough to show that the stack depth never exceeds
log N for an input of size N. I use recursion quite routinely
without there being any significant danger of stack overflow. It's
a matter of learning which patterns are safe and which patterns are
potentially dangerous, and avoiding the dangerous patterns (unless
certain guarantees can be made to make them safe again).

bart <bc@freeuk.com> writes:

P.S. You deserve credit for pointing out that the worst case
for flood fill is changing the color of the entire pixel
field. Maybe it was obvious to other people but I appreciate
it.

On 18/03/2024 09:30, Tim Rentsch wrote:
> Michael S <already5chosen@yahoo.com> writes:
>
>>> 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;
>>>> }
>
> [...]
>
>> Except I don't understand why it works it all.
>> Can't fill area have sub-areas that only connected through diagonal?
>
> It is customary in raster graphics to count pixels as adjacent
> only if they share an edge, not if they just share a corner.
> Usually that gives better results; the exceptions tend to need
> special handling anyway and not just connecting through
> diagonals.
>
Though with a binary image, if the foreground is 4-connected, the
background must therefore be 8-connected.
--
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm

On Mon, 18 Mar 2024 03:00:32 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> 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?
>
> The claim is that recursion always makes programs harder to reason
> about and prove correct. It's easy to find examples that show
> recursion does not always makes programs harder to reason about and
> prove correct.
>
> > I personally find recursion hard work and errors much harder to
> > debug.
>
> Most likely that's because you haven't had the relevant background
> in learning how to program in a functional style. That matches my
> own experience: it was only after learning how to write programs in
> a functional style that I really started to appreciate the benefits
> of using recursion, and to understand how to write and reason about
> recursive programs.
>
> > It is also becomes much more important to show that will not cause
> > stack overflow.
>
> In most cases it's enough to show that the stack depth never exceeds
> log N for an input of size N. I use recursion quite routinely
> without there being any significant danger of stack overflow. It's
> a matter of learning which patterns are safe and which patterns are
> potentially dangerous, and avoiding the dangerous patterns (unless
> certain guarantees can be made to make them safe again).

The problem in this case is that max. depth of recursion is O(N) where N
is total number of pixels to change color. So far I didn't find an
obvious way to cut the worst case by more than small factor without
turning recursive algorithm into something that is unrecognizably
different from original and require proof of correction of its own.
Classic 'divide and conquer smaller part first" strategy does not
appear applicable here, or at least not obviously.