On Sun, 17 Mar 2024 13:19:29 -0700
"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> wrote:

> 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!
>
> :^)
>

I did.
After a bit of polish applied to corners (on x86-64) it consumes
approximately 60 times less extra memory than recursive variant of
Malcolm and is approximately 2.5 faster than non-naive recursion.
But it still decisively slower than Malcolm's non-recursive code:
~4x for 'snake' shape, ~2x for solid rectangle.
Malcolm's algorithm is simply better than recursive one.
Most likely because it visits already re-colored pixels less often.

For those interested, here is 'explicit stack' variant of recursive
algorithm:

int floodfill_r_explicite_stack(
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;

const ptrdiff_t initial_stack_sz = 256;
char* stack = malloc(initial_stack_sz*sizeof(*stack));
if (!stack)
return -1;
char* sp = stack;
char* end_stack = &stack[initial_stack_sz];

enum { ST_LEFT, ST_RIGHT, ST_UP, ST_DOWN, };
for (;;) {
do {
if (grey[y*width+x] != target)
break; // back to caller

grey[y*width+x] = dest;
x -= 1;
// push state to stack
if (sp == end_stack) { // allocate more stack space
ptrdiff_t old_sz = sp-stack;
ptrdiff_t new_sz = old_sz + old_sz/2;
stack = realloc(stack, new_sz*sizeof(*stack));
if (!stack)
return -1;
sp = &stack[old_sz];
end_stack = &stack[new_sz];
}
*sp++ = ST_LEFT; // recursive call
} while (x >= 0);

for (;;) {
if (sp == stack) { // we are back at top level
free(stack);
return 1; // done
}

char state = *--sp; // pop stack (back to caller)
switch (state) {
case ST_LEFT:
x += 2;
if (x < width) {
*sp++ = ST_RIGHT; // recursive call
break;
}
// fall throw

case ST_RIGHT:
x -= 1;
y -= 1;
if (y >= 0) {
*sp++ = ST_UP; // recursive call
break;
}
// fall throw

case ST_UP:
y += 2;
if (y < height) {
*sp++ = ST_DOWN; // recursive call
break;
}
// fall throw

case ST_DOWN:
y -= 1;
continue; // back to caller
}
break;
}
}
}

On 18/03/2024 10:26, Malcolm McLean wrote:
> 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.

To be clear - I don't claim that recursive code is /always/ easier to
analyse. I claim it is easier in this case, and in many other cases
(thus countering your claim that it is /always/ harder).

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

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

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

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

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

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

That is a, shall we say, "interesting" attitude.

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

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

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

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

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

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

> And while this code is in C, the same algorithm could be implemented in
> other languages.  A language that uses a VM might be fine with a much
> higher recursion depth - or it might be much lower.  A language for
> which recursion is a major tool (such as a functional programming
> language) might automatically convert some recursive code to a
> queue-based non-recursive solution.  (I'd be impressed to see one do
> that for this algorithm, however.)
>
>> Now a 100x100 woked fine an my machine  - I just checked the main
>> stack, and it's 8MB by default. BUt of cuuurse the bigger than
>> machine, the bigger the image th euser might want to load.
>>
>
> You still haven't considered using a spell-checker, even though you use
> a news client with one built in?  Perhaps you need a better keyboard?
>
I'll try it out. Since you're dyslexic. Normal readers can read English
text with just the initial and terminal letters right and the rest
jumbled, at similar speed to normal text.
>
> The worst case is either going to be the stripy path example given by
> Michael S., or a completely blank image - it depends on how the
> east-west stripes affect the queue depth.  It should not be hard to try
> these.  So that would be either approximately half the total pixel
> count, or the total pixel count.  And I can't think how you could
> specify a "typical" image and "typical" flood fill request - without
> specifying this in some way, you need to collect lots of statistics of
> real-world use, or it's mere guesswork.
>
Pixels usually represent objects. Take a glance around your. How many
objects of a similar colour are spider's webs, lace curtains, long
wires, and so on. And how many are pieces of paper, coffee cups.
computer mice, and so on? And of course it mustn't fall over on the
unusual objects, but the main consideration is usually that it is fast
and efficient on the common ones.

But not always of course, Sometimes results must in in under 0.1
seconds, and so 0.09 is as good as 0.01, but 0.11 on a rare spider's web
is catastrophic.
>
> That would be the "royal we", I presume?  I know /I/ would have no use
> for a flood-fill routine that did not support colour styles I use.
>

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

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>On 18/03/2024 16:28, David Brown wrote:
>> On 18/03/2024 10:26, Malcolm McLean wrote:
>>
>> It is completely normal for correctness proofs to make assumptions about
>> things like resources.  An analysis of your code for correctness would
>> also generally assume that the heap would be big enough - if the heap
>> runs out, your code will not correctly flood-fill the image.  Analysis
>> of efficiency in time and space is a separate issue - related, but
>> separate.  Things like maximum recursion depth (and heap size) are very
>> implementation-specific, and thus need to be considered separately from
>> the algorithm itself.
>>
>
>It's trivial to engineer a system with a large stack and very small
>heap. But unlikley anyone would actually do so on a system on which
>floodfill would run.

The first sentence is correct. Although with modern systems, 'small'
is relative (my 12 year old workstation has 16GB RAM) and defaults
to an 8MB stack, which can easily be increased on a per process or
per user basis.

The second is your opinion. What evidence do you have that
your opinion is fact?

>> And while this code is in C, the same algorithm could be implemented in
>> other languages.  A language that uses a VM might be fine with a much
>> higher recursion depth - or it might be much lower.  A language for
>> which recursion is a major tool (such as a functional programming
>> language) might automatically convert some recursive code to a
>> queue-based non-recursive solution.  (I'd be impressed to see one do
>> that for this algorithm, however.)
>>
>>> Now a 100x100 woked fine an my machine  - I just checked the main
>>> stack, and it's 8MB by default. BUt of cuuurse the bigger than
>>> machine, the bigger the image th euser might want to load.
>>>
>>
>> You still haven't considered using a spell-checker, even though you use
>> a news client with one built in?  Perhaps you need a better keyboard?
>>
>I'll try it out. Since you're dyslexic.

I believe you're conflating David with someone else
who made that claim.

> Normal readers can read English

Ah, a not-so-subtle insult to those who happen to suffer from dyslexia.

>text with just the initial and terminal letters right and the rest
>jumbled, at similar speed to normal text.

>Pixels usually represent objects. Take a glance around your. How many
>objects of a similar colour are spider's webs, lace curtains, long
>wires, and so on. And how many are pieces of paper, coffee cups.
>computer mice, and so on? And of course it mustn't fall over on the
>unusual objects, but the main consideration is usually that it is fast
>and efficient on the common ones.

The main consideration must be that it sufficient, readable and
maintainable. Fast and efficient aren't always a driving goal,
particularly for rarely used operations.

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
> On 18/03/2024 16:28, David Brown wrote:
[...]
>> You still haven't considered using a spell-checker, even though you
>> use a news client with one built in?  Perhaps you need a better
>> keyboard?
>>
> I'll try it out. Since you're dyslexic. Normal readers can read
> English text with just the initial and terminal letters right and the
> rest jumbled, at similar speed to normal text.

I will not speculate about why you seem to be unaware that calling
someone dyslexic is insulting, both to the person you're addressing and
to people with dyslexia.

You need to stop making disparaging personal comments.

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Medtronic
void Void(void) { Void(); } /* The recursive call of the void */

Michael S <already5chosen@yahoo.com> writes:

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

>>> [a floodfill routine posted by Malcolm]

>> [...]
>>
>> [a recursive area fill written by Michael S]
>
> I did my own measurements with snake-like image from my first
> response to Malcolm. For this shape, recursive version (after my
> improvement) is almost exactly 10 times slower than Malcolm's
> iterative code. And suspect to stack overflow although a little
> less so than original.

It's hard to write a recursive area fill routine if one wants to
guarantee worst case behavior in all cases. This problem is not
a good fit to using recursion without there being some kind of
constraints on what the inputs will be.

> Even if in Big Oh sense they are the same, it does look like
> Malcolm's variant is decisively faster in practice.

I've done some tests with Malcolm's code. Some observations:

It uses more memory than it needs to.

It's anisotropic, which is to say it behaves differently with
respect to changes in width than it does to changes in height.

It doesn't scale well. In particular worst case performance
scaling is worse than O(N) (as determined experimentally, not
theoretically).

The code is much longer than is needed just to do an area fill.
A small fraction of that is simply layout style, but mostly it's
that the code is more complicated than it needs to be.

On 18/03/2024 17:42, Scott Lurndal wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>> On 18/03/2024 16:28, David Brown wrote:
>>> On 18/03/2024 10:26, Malcolm McLean wrote:
>>>
>>> It is completely normal for correctness proofs to make assumptions about
>>> things like resources.  An analysis of your code for correctness would
>>> also generally assume that the heap would be big enough - if the heap
>>> runs out, your code will not correctly flood-fill the image.  Analysis
>>> of efficiency in time and space is a separate issue - related, but
>>> separate.  Things like maximum recursion depth (and heap size) are very
>>> implementation-specific, and thus need to be considered separately from
>>> the algorithm itself.
>>>
>>
>> It's trivial to engineer a system with a large stack and very small
>> heap. But unlikley anyone would actually do so on a system on which
>> floodfill would run.
>
> The first sentence is correct. Although with modern systems, 'small'
> is relative (my 12 year old workstation has 16GB RAM) and defaults
> to an 8MB stack, which can easily be increased on a per process or
> per user basis.
>
> The second is your opinion. What evidence do you have that
> your opinion is fact?

It seems the most likely. People don't run programs whose sole purpose
is to floodfill, so that they can request a huge stack.

It will likely be part of a much larger application with conventional
stack usage.

The floodfill may be part of a library, and itself wrapped by another
library that the application knows about.

It is even possible that when the application is built, it doesn't know
that a floodfill routine is to be called. (For example, an interpreter
that will run a program that /might/ call a floodfill routine.)

As the author of such a routine, you don't want to have to rely on a
stack large enough to cope with, say, a 30Mpix image which might need a
30M-deep maximum call-depth, which could easily use up 500MB of memory.
stack.

On 18/03/2024 18:36, Tim Rentsch wrote:
>
>
> It doesn't scale well. In particular worst case performance
> scaling is worse than O(N) (as determined experimentally, not
> theoretically).
>

Is that because the queue is being memmoved instead of using a circular
buffer when it gets towards the end?

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

fir <fir@grunge.pl> writes:

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

As others have explained using simple recursion like this
runs the risk of producing a stack overflow.

Here is a short routine that uses allocated memory rather than
recursion, and so does not have the stack overflow risk that
the above recursive routine does.

The code below uses a slightly different interface to access
the pixel field but I expect you can see how to adapt it to
your interface.

Also the code uses a variably modified type in two places. It
should be easy to change the code to use ordinary types rather
than variably modified types if it's important to do that in
your environment. And it may be the case that changing to use
a different interface to access and change the pixel field will
get rid of the variably modified types so that they wouldn't be
needed anyway.

Oh, before I forget. If someone doesn't like using a single
fixed-size allocated area, it isn't hard to change the code
so that the allocated area grows as needed (and starting with
a smaller size, presumably). I leave doing that as an
exercise.

The code:

#include <assert.h>

typedef unsigned char Color;
typedef unsigned int UI;
typedef struct { UI x, y; } Point;
typedef unsigned int Index;

static _Bool change_it( UI w, UI h, Color [w][h], Point, Color, Color );

void
fill_area( UI w, UI h, Color pixels[w][h], Point p0, Color old, Color new ){
static const Point deltas[4] = { {1,0}, {0,1}, {-1,0}, {0,-1}, };
Index k = 0;
Index n = (w+h) *17 /16 +10;
Point *todo = malloc( n * sizeof *todo );

if( todo && change_it( w, h, pixels, p0, old, new ) ) todo[k++] = p0;

while( k > 0 ){
Index j = n-k;
memmove( todo + j, todo, k * sizeof *todo );
k = 0;

while( j < n ){
Point p = todo[ j++ ];
for( Index i = 0; i < 4; i++ ){
Point q = { p.x + deltas[i].x, p.y + deltas[i].y };
if( ! change_it( w, h, pixels, q, old, new ) ) continue;
assert( j > k );
todo[ k++ ] = q;
}
}
}

free( todo );
}

_Bool
change_it( UI w, UI h, Color pixels[w][h], Point p, Color old, Color new ){
if( p.x >= w || p.y >= h || pixels[p.x][p.y] != old ) return 0;
return pixels[p.x][p.y] = new, 1;
}

Michael S <already5chosen@yahoo.com> writes:

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

Right. I said as much in another reply to you. This problem
is not well suited to a recursive solution.

To clarify my earlier comment, when I say I routinely use
recursion I do not mean I always use recursion. Part of
understanding programming in a functional style is knowing
when not to use recursion as well as when to use it.

In article <878r2f2yy7.fsf@nosuchdomain.example.com>,
Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
....
>I will not speculate about why blah, blah, blah.
>blah, blah, blah.
>blah, blah, blah.
>
>You need to stop making disparaging personal comments.

Is stating that someone has a cold an "insult"?

Yes, I get it, in keith-world, everything is an insult; this is borne out by
his posting history.

It must hurt to be Keith.

--
Reading any post by Fred Hodgin, you're always faced with the choice of:
lunatic, moron, or troll.

I always try to be generous and give benefit of the doubt, by assuming troll.

On 3/18/2024 10:25 AM, Malcolm McLean wrote:
> On 18/03/2024 16:28, David Brown wrote:
>> On 18/03/2024 10:26, Malcolm McLean wrote:

[...]

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

Ummmm... That is a rather harsh statement? ;^o

[...]

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

[...]

Here is the refinement that uses a resizing rather than
fixed-size buffer.

typedef unsigned char Color;
typedef unsigned int UI;
typedef struct { UI x, y; } Point;
typedef unsigned int Index;

static _Bool change_it( UI w, UI h, Color [w][h], Point, Color, Color );

void
fill_area( UI w, UI h, Color pixels[w][h], Point p0, Color old, Color new ){
static const Point deltas[4] = { {1,0}, {0,1}, {-1,0}, {0,-1}, };
UI k = 0;
UI n = 17;
Point *todo = malloc( n * sizeof *todo );

if( todo && change_it( w, h, pixels, p0, old, new ) ) todo[k++] = p0;

while( k > 0 ){
Index j = n-k;
memmove( todo + j, todo, k * sizeof *todo );
k = 0;

while( j < n ){
Point p = todo[ j++ ];
for( Index i = 0; i < 4; i++ ){
Point q = { p.x + deltas[i].x, p.y + deltas[i].y };
if( ! change_it( w, h, pixels, q, old, new ) ) continue;
todo[ k++ ] = q;
}

if( j-k < 3 ){
Index new_n = n+n/4;
Index new_j = new_n - (n-j);
Point *t = realloc( todo, new_n * sizeof *t );
if( !t ){ k = 0; break; }
memmove( t + new_j, t + j, (n-j) * sizeof *t );
todo = t, n = new_n, j = new_j;
}
}
}

free( todo );
}

_Bool
change_it( UI w, UI h, Color pixels[w][h], Point p, Color old, Color new ){
if( p.x >= w || p.y >= h || pixels[p.x][p.y] != old ) return 0;
return pixels[p.x][p.y] = new, 1;
}

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

> On 18/03/2024 09:30, Tim Rentsch wrote:
>
>> Michael S <already5chosen@yahoo.com> writes:
[...]
>>> 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.

It might be but it doesn't have to be.

Also different terminology should be used, since 4-connected
(also N-connected, for other integer N) has a specific meaning in
graph theory, and one very different than what is meant above.

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

> On 18/03/2024 18:36, Tim Rentsch wrote:
>>
>>
>> It doesn't scale well. In particular worst case performance
>> scaling is worse than O(N) (as determined experimentally, not
>> theoretically).
>
> Is that because the queue is being memmoved instead of using a
> circular buffer when it gets towards the end?

I'm sure I don't know, and I'm astonished that you would ask.
It's your code after all. IMO it should simply be thrown out and
re-written; it pains me just to look at it, let alone to try to
understand or fix it.

On 18/03/2024 18:25, Malcolm McLean wrote:
> On 18/03/2024 16:28, David Brown wrote:
>> On 18/03/2024 10:26, Malcolm McLean wrote:
>>
>> It is completely normal for correctness proofs to make assumptions
>> about things like resources.  An analysis of your code for correctness
>> would also generally assume that the heap would be big enough - if the
>> heap runs out, your code will not correctly flood-fill the image.
>> Analysis of efficiency in time and space is a separate issue -
>> related, but separate.  Things like maximum recursion depth (and heap
>> size) are very implementation-specific, and thus need to be considered
>> separately from the algorithm itself.
>>
>
> It's trivial to engineer a system with a large stack and very small
> heap. But unlikley anyone would actually do so on a system on which
> floodfill would run.

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

>
>> And while this code is in C, the same algorithm could be implemented
>> in other languages.  A language that uses a VM might be fine with a
>> much higher recursion depth - or it might be much lower.  A language
>> for which recursion is a major tool (such as a functional programming
>> language) might automatically convert some recursive code to a
>> queue-based non-recursive solution.  (I'd be impressed to see one do
>> that for this algorithm, however.)
>>
>>> Now a 100x100 woked fine an my machine  - I just checked the main
>>> stack, and it's 8MB by default. BUt of cuuurse the bigger than
>>> machine, the bigger the image th euser might want to load.
>>>
>>
>> You still haven't considered using a spell-checker, even though you
>> use a news client with one built in?  Perhaps you need a better keyboard?
>>
> I'll try it out. Since you're dyslexic. Normal readers can read English
> text with just the initial and terminal letters right and the rest
> jumbled, at similar speed to normal text.

You are fond of making up "Malcolm facts" about the cognitive effort
involved in understanding things like nested parentheses. Poor
spelling, typos, grammatical errors, and the like similarly increase the
cognitive effort in reading your posts. When it takes too much effort
to figure out what you are trying to say, it is not worth the bother.

I am not looking for perfection here - mistakes happen. I am merely
looking for a minimum of effort on your part, such as using the
spell-checker built into your newsreader. And I don't expect you to do
this for /me/, or because I or anyone else is dyslexic. I consider it a
basic level of politeness and respect for others. I find it
extraordinary that you have been so reluctant to take this step before now.

>>
>> The worst case is either going to be the stripy path example given by
>> Michael S., or a completely blank image - it depends on how the
>> east-west stripes affect the queue depth.  It should not be hard to
>> try these.  So that would be either approximately half the total pixel
>> count, or the total pixel count.  And I can't think how you could
>> specify a "typical" image and "typical" flood fill request - without
>> specifying this in some way, you need to collect lots of statistics of
>> real-world use, or it's mere guesswork.
>>
> Pixels usually represent objects. Take a glance around your. How many
> objects of a similar colour are spider's webs,  lace curtains, long
> wires, and so on. And how many are pieces of paper, coffee cups.
> computer mice, and so on? And of course it mustn't fall over on the
> unusual objects, but the main consideration is usually that it is fast
> and efficient on the common ones.

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

>
> But not always of course, Sometimes results must in in under 0.1
> seconds, and so 0.09 is as good as 0.01, but 0.11 on a rare spider's web
> is catastrophic.

I cannot imagine the situation where you would have a hard real-time
limit of 0.1 seconds to do a simplistic flood fill on a rare spider's
web (or picture thereof).

I think it would suffice to test the code on a few worst-case samples,
and a few examples of images you have yourself that you need to
flood-fill. If the speed is good enough on your computer during such
tests, that would be all you need. You are not making a real-world
reusable graphics library or a serious image manipulation tool here.

>>
>> That would be the "royal we", I presume?  I know /I/ would have no use
>> for a flood-fill routine that did not support colour styles I use.
>>
>
> This routine is part of the binary image processing library, so of
> course it is written to be easy to use with binary images, or binary
> images which have been processed and are no longer strictly binary
> images. But if people want to take it and use it as pattern for a
> general flood fill, then of course I'm perfectly happy that they have
> found the code to be of use.

On 18/03/2024 18:42, Scott Lurndal wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>> On 18/03/2024 16:28, David Brown wrote:

>>> You still haven't considered using a spell-checker, even though you use
>>> a news client with one built in?  Perhaps you need a better keyboard?
>>>
>> I'll try it out. Since you're dyslexic.
>
> I believe you're conflating David with someone else
> who made that claim.

I did, in another post, say that I am mildly dyslexic. The context was
that I understand spelling can be difficult - my spelling, without a
spell-checker, is often terrible. But my reading level is very high.

I expect most people here can figure out the words Malcolm meant to type
when he fails to press the right keys. But we should not have to do so.

On Mon, 18 Mar 2024 22:42:14 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
> [...]
>
> Here is the refinement that uses a resizing rather than
> fixed-size buffer.
>
>
> typedef unsigned char Color;
> typedef unsigned int UI;
> typedef struct { UI x, y; } Point;
> typedef unsigned int Index;
>
> static _Bool change_it( UI w, UI h, Color [w][h], Point, Color,
> Color );
>
> void
> fill_area( UI w, UI h, Color pixels[w][h], Point p0, Color old, Color
> new ){ static const Point deltas[4] = { {1,0}, {0,1}, {-1,0},
> {0,-1}, }; UI k = 0;
> UI n = 17;
> Point *todo = malloc( n * sizeof *todo );
>
> if( todo && change_it( w, h, pixels, p0, old, new ) )
> todo[k++] = p0;
>
> while( k > 0 ){
> Index j = n-k;
> memmove( todo + j, todo, k * sizeof *todo );
> k = 0;
>
> while( j < n ){
> Point p = todo[ j++ ];
> for( Index i = 0; i < 4; i++ ){
> Point q = { p.x + deltas[i].x, p.y + deltas[i].y };
> if( ! change_it( w, h, pixels, q, old, new ) )
> continue; todo[ k++ ] = q;
> }
>
> if( j-k < 3 ){
> Index new_n = n+n/4;
> Index new_j = new_n - (n-j);
> Point *t = realloc( todo, new_n * sizeof *t );
> if( !t ){ k = 0; break; }
> memmove( t + new_j, t + j, (n-j) * sizeof *t );
> todo = t, n = new_n, j = new_j;
> }
> }
> }
>
> free( todo );
> }
>
> _Bool
> change_it( UI w, UI h, Color pixels[w][h], Point p, Color old, Color
> new ){ if( p.x >= w || p.y >= h || pixels[p.x][p.y] != old )
> return 0; return pixels[p.x][p.y] = new, 1;
> }

This variant is significantly slower than Malcolm's.
2x slower for solid rectangle, 6x slower for snake shape.
Is it the same algorithm?

Besides, I don't think that use of VLA in library code is a good idea.
VLA is optional in latest C standards. And incompatible with C++.

On 18/03/2024 19:10, Keith Thompson wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>> On 18/03/2024 16:28, David Brown wrote:
> [...]
>>> You still haven't considered using a spell-checker, even though you
>>> use a news client with one built in?  Perhaps you need a better
>>> keyboard?
>>>
>> I'll try it out. Since you're dyslexic. Normal readers can read
>> English text with just the initial and terminal letters right and the
>> rest jumbled, at similar speed to normal text.
>
> I will not speculate about why you seem to be unaware that calling
> someone dyslexic is insulting, both to the person you're addressing and
> to people with dyslexia.
>
> You need to stop making disparaging personal comments.
>

I think Malcolm is truly unaware of how these kinds of comments could be
taken.

To be clear here, I did mention in another post that I am dyslexic. So
he was not saying it out of the blue.

However, it does not seem that he has a very good idea of what dyslexia,
in all its forms and variations, actually is. My dyslexia does not
affect my reading at all (as far as any measurements have ever shown),
but it affects my spelling quite a lot. (It has other effects too, but
we don't need to cover everything here.)

(Malcolm's comment about "normal readers" reading jumbled text has a
grain of truth to it, but not much more than a grain.)

On 19/03/2024 05:54, Tim Rentsch wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>
>> On 18/03/2024 09:30, Tim Rentsch wrote:
>>
>>> Michael S <already5chosen@yahoo.com> writes:
> [...]
>>>> 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.
>
> It might be but it doesn't have to be.
>
> Also different terminology should be used, since 4-connected
> (also N-connected, for other integer N) has a specific meaning in
> graph theory, and one very different than what is meant above.

That is the terminology in binary image processing. The pixels are
4-connected or 8-connected depending on whether a shared corner is
considered to make the group of pixels two objects or one object.

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

On 19/03/2024 11:18, Michael S wrote:
> On Mon, 18 Mar 2024 22:42:14 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>> [...]
>>
>> Here is the refinement that uses a resizing rather than
>> fixed-size buffer.
>>
>>
>> typedef unsigned char Color;
>> typedef unsigned int UI;
>> typedef struct { UI x, y; } Point;
>> typedef unsigned int Index;
>>
>> static _Bool change_it( UI w, UI h, Color [w][h], Point, Color,
>> Color );
>>
>> void
>> fill_area( UI w, UI h, Color pixels[w][h], Point p0, Color old, Color
>> new ){ static const Point deltas[4] = { {1,0}, {0,1}, {-1,0},
>> {0,-1}, }; UI k = 0;
>> UI n = 17;
>> Point *todo = malloc( n * sizeof *todo );
>>
>> if( todo && change_it( w, h, pixels, p0, old, new ) )
>> todo[k++] = p0;
>>
>> while( k > 0 ){
>> Index j = n-k;
>> memmove( todo + j, todo, k * sizeof *todo );
>> k = 0;
>>
>> while( j < n ){
>> Point p = todo[ j++ ];
>> for( Index i = 0; i < 4; i++ ){
>> Point q = { p.x + deltas[i].x, p.y + deltas[i].y };
>> if( ! change_it( w, h, pixels, q, old, new ) )
>> continue; todo[ k++ ] = q;
>> }
>>
>> if( j-k < 3 ){
>> Index new_n = n+n/4;
>> Index new_j = new_n - (n-j);
>> Point *t = realloc( todo, new_n * sizeof *t );
>> if( !t ){ k = 0; break; }
>> memmove( t + new_j, t + j, (n-j) * sizeof *t );
>> todo = t, n = new_n, j = new_j;
>> }
>> }
>> }
>>
>> free( todo );
>> }
>>
>> _Bool
>> change_it( UI w, UI h, Color pixels[w][h], Point p, Color old, Color
>> new ){ if( p.x >= w || p.y >= h || pixels[p.x][p.y] != old )
>> return 0; return pixels[p.x][p.y] = new, 1;
>> }
>
> This variant is significantly slower than Malcolm's.
> 2x slower for solid rectangle, 6x slower for snake shape.
> Is it the same algorithm?
>

No. Mine takes horizontal scan lines and extends them, then places the
pixels above and below in a queue to be considered as seeds for the next
scan line. (It's not mine, but I don't know who invented it. It wasn't me.)

Tim, now what does it do? Essentially it's the recursive fill algorithm
but with the data only on the stack instead of the call and the data.
And todo is actually a queue rather than a stack.

Now why would it be slower? Probaby because you usually only hit a pixel
three times with mine - once below, once above, and once for the scan
line itself, whilst you consider it 5 times for Tim's - once for each
neighbour and once for itself. Then horizontally adjacent pixels are
more likely to be in the same cache line than vertically adjacent
pixels, so processing images in scan lines tends to be a bit faster.

> Besides, I don't think that use of VLA in library code is a good idea.
> VLA is optional in latest C standards. And incompatible with C++.
>
>

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

On 19/03/2024 06:10, Tim Rentsch wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>
>> On 18/03/2024 18:36, Tim Rentsch wrote:
>>>
>>>
>>> It doesn't scale well. In particular worst case performance
>>> scaling is worse than O(N) (as determined experimentally, not
>>> theoretically).
>>
>> Is that because the queue is being memmoved instead of using a
>> circular buffer when it gets towards the end?
>
> I'm sure I don't know, and I'm astonished that you would ask.
> It's your code after all. IMO it should simply be thrown out and
> re-written; it pains me just to look at it, let alone to try to
> understand or fix it.

Yes, but I wrote it years ago. I can't remember why the value of 256
pixels was put in. But I do remember why the queue isn't very efficient
- for the small images I expected to be processed, I judged that the
added complexity of maintaining a circular queue wouldn't be worth it,
given that I wanted the routine to be leaf. However if you can somehow
trigger catastrophic big O behaviour, it won't be a surprise.

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

On 19/03/2024 10:41, David Brown wrote:
>
> I expect most people here can figure out the words Malcolm meant to type
> when he fails to press the right keys.  But we should not have to do so.
>

So ... the poster should make the effort once, rather than the 1000s of
readers should be made to make the effort 1000s of times.

This is usenet etiquette 101.

Groovy hepcat Lew Pitcher was jivin' in comp.lang.c on Mon, 18 Mar 2024
01:27 am. It's a cool scene! Dig it.

>> On 16/03/2024 04:11, fir wrote:

[Snip.]

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

[Snippity doo dah.]

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

No, I don't think so. You seem to have missed the fact that it checks
the colour of the "current" pixel, and only continues (setting new
colour & recursing) if it is the old colour.
Of course, I'm infering (guessing) the functionality, at least
partially (Unsafe? Safe?), of GetPixelUnsafe() and SetPixelSafe() based
on their names.

[Snip Lew's examples.]

--

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

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

On Tue, 19 Mar 2024 11:57:53 +0000
Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:

>
> No. Mine takes horizontal scan lines and extends them, then places
> the pixels above and below in a queue to be considered as seeds for
> the next scan line. (It's not mine, but I don't know who invented it.
> It wasn't me.)
>
> Tim, now what does it do? Essentially it's the recursive fill
> algorithm but with the data only on the stack instead of the call and
> the data. And todo is actually a queue rather than a stack.
>
> Now why would it be slower? Probaby because you usually only hit a
> pixel three times with mine - once below, once above, and once for
> the scan line itself, whilst you consider it 5 times for Tim's - once
> for each neighbour and once for itself. Then horizontally adjacent
> pixels are more likely to be in the same cache line than vertically
> adjacent pixels, so processing images in scan lines tends to be a bit
> faster.
>

Below is a variant of recursive algorithm that is approximately as
fast as your code (1.25x faster for filling solid rectangle, 1.43x
slower for filling snake shape).
The code is a bit long, but I hope that the logic is still obvious and
there is no need to prove correctness.
I have a micro-optimized variant of the same algorithm that is as fast
or faster than yours in all cases that I tested, but posting
micro-optimized code on c.l.c is a bad sportsmanship.
Recursion depth of this algorithm for typical solid shape is
O(max(width,height)), but for a worst case it still very bad, about N/4.
And since there are more local variable to preserve, the worst case
size of occupied stack is likely even bigger than in simple (but
non-naive) recursion. So, while fast, I wouldn't use this algorithm in
general-purpose library.
But it can serve as a reference point for implementation with explicit
stack.

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

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

static void floodfill_r_core(const struct recursive_context_t* context,
int x, int y) {
// point (x,y) is in target rectangle and has target color. It's
guaranteed by caller

// Find maximal cross (of Saint George's variety) with target color
and center at (x,y) // go left
int x0;
for (x0 = x-1; x0 >= 0 &&
context->grey[y*context->width+x0] == context->target; --x0); ++x0;
// go right
int x1;
for (x1 = x+1; x1 < context->width &&
context->grey[y*context->width+x1] == context->target; ++x1); // go up
int y0;
for (y0 = y-1; y0 >= 0 &&
context->grey[y0*context->width+x] == context->target; --y0); ++y0;
// go down
int y1;
for (y1 = y+1; y1 < context->height &&
context->grey[y1*context->width+x] == context->target; ++y1);

// Fill cross with destination color
for (int i = x0; i < x1; ++i)
context->grey[y*context->width+i] = context->dest;
for (int i = y0; i < y1; ++i)
context->grey[i*context->width+x] = context->dest;

if (y > 0) { // recursion into points above horizontal line
unsigned char *row = &context->grey[(y-1)*context->width];
for (int i = x0; i < x1; ++i)
if (row[i] == context->target)
floodfill_r_core(context, i, y-1);
}
if (y+1 < context->height) { // recursion into points below
horizontal line unsigned char *row =
&context->grey[(y+1)*context->width]; for (int i = x0; i < x1; ++i)
if (row[i] == context->target)
floodfill_r_core(context, i, y+1);
}
if (x > 0) { // recursion into points left of vertical line
unsigned char *col = &context->grey[x-1];
for (int i = y0; i < y1; ++i)
if (col[i*context->width] == context->target)
floodfill_r_core(context, x-1, i);
}
if (x+1 < context->width) { // recursion into points right of
vertical line unsigned char *col = &context->grey[x+1];
for (int i = y0; i < y1; ++i)
if (col[i*context->width] == context->target)
floodfill_r_core(context, x+1, i);
}
}