Re: filling area by color atack safety - worst memory size

On Sun, 24 Mar 2024 10:24:45 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

Michael S <already5chosen@yahoo.com> writes:
 

On Wed, 20 Mar 2024 10:01:10 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
 

Michael S <already5chosen@yahoo.com> writes: 

 
[...]
 

Generally, I like your algorithm.
It was surprising for me that queue can work better than stack, my
intuition suggested otherwise, but facts are facts. 

>
Using a stack is like a depth-first search, and a queue is like a
breadth-first search.  For a pixel field of size N x N, doing a
depth-first search can lead to memory usage of order N**2,
whereas a breadth-first search has a "frontier" at most O(N).
Another way to think of it is that breadth-first gets rid of
visited nodes as fast as it can, but depth-first keeps them
around for a long time when everything is reachable from anywhere
(as will be the case in large simple reasons). 

>
For my test cases the FIFO depth of your algorithm never exceeds
min(width,height)*2+2.  I wonder if existence of this or similar
limit can be proven theoretically. 

 
I believe it is possible to prove the strict FIFO algorithm is
O(N) for an N x N pixel field, but I haven't tried to do so in
any rigorous way, nor do I know what the constant is.  It does
seem to be larger than 2.
>

It seems that in worst case the strict FIFO algorithm is the same as
the rest of them, i.e. O(NN) where NN is the number of re-colored
points. Below is an example of the shape for which I measured memory
consumption for 3840x2160 image almost exactly 4x as much as for
1920x1080.

static void make_fractal_tree_recursive(
  unsigned char* image,
  int            width,
  int            nx,
  int            ny,
  unsigned char  pen_c)
{
  if (nx < 3 && ny < 3) {
    // small rectangle - solid fill
    for (int y = 0; y < ny; ++y)
      for (int x = 0; x < nx; ++x)
        image[width*y+x] = pen_c;
    return;
  }
  if (nx >= ny) {
    int xc = (nx-1)/2;
    if (xc - 1 > 0) { // left sub-plot
      make_fractal_tree_recursive(image, width, xc - 1, ny, pen_c);
    }
    if (xc + 2 < nx) { // right sub-plot
      make_fractal_tree_recursive(&image[xc+2], width,
        nx - (xc + 2), ny, pen_c);
    }
    // draw vertical cross
    for (int y = 0; y < ny; ++y)
      image[width*y+xc] = pen_c;
    int yc = (ny-1)/2;
    image[width*yc+xc-1] = pen_c;
    image[width*yc+xc+1] = pen_c;
  } else {
    int yc = (ny-1)/2;
    if (yc - 1 > 0) { // upper sub-plot
      make_fractal_tree_recursive(image, width, nx, yc - 1, pen_c);
    }
    if (yc + 2 < ny) { // lower sub-plot
      make_fractal_tree_recursive(&image[(yc+2)*width], width, nx,
          ny -(yc + 2), pen_c);
    }
    // draw horizontal cross
    for (int x = 0; x < nx; ++x)
      image[width*yc+x] = pen_c;
    int xc = (nx-1)/2;
    image[width*(yc-1)+xc] = pen_c;
    image[width*(yc+1)+xc] = pen_c;
  }
}

static void make_fractal_tree(
  unsigned char* image,
  int            width,
  int            height,
  unsigned char  background_c,
  unsigned char  pen_c)
{
  memset(image, background_c, width*height);
  make_fractal_tree_recursive(image, width, width, height, pen_c);
}