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

On Wed, 5 Jun 2024 17:45:45 +0300
Michael S <already5chosen@yahoo.com> wrote:

On Fri, 3 May 2024 18:33:05 +0300
Michael S <already5chosen@yahoo.com> wrote:
 

On Thu, 25 Apr 2024 17:56:06 +0300
Michael S <already5chosen@yahoo.com> wrote:
 
 
A solution (sort of) is in line with the famous quite of David
Wheeler
- to turn todo lists from bit maps into arrays of
abscesses-or-ordinates of contact points.
 
The cost is a memory footprint - 4x bigger than the previous
version, 32 times bigger than above-mentioned "packed" variant of
the previous version. But in BigO sense it's the same.
 
In my tests it reduced the worst case time from O(max(A,B)**3) to
O(A*B*log(max(A,B)). Which is non-ideal, but probably acceptable,
because the bad cases should be very rare in practice.
 
The real trouble is different - I don't know if my "worst case" is
really the worst.
 
The code below is for presentation of algorithm in both clear and
compact manner, with emphasis on symmetry between x and y
directions. It is not optimal in any sense and can be made
no-trivially faster both by algorithm enhancements an by
specialization of critical loops.
 
 

 
Following code improves on ideas from the previous post.
Unlike the previous one, it is purely iterative, with no recursion.
The algorithm is simpler and access storage in more compact manner,
i.e. all accessed memory area starts from beginning and grows
according to need. Previous attempt did not have this property.
It's still longer and less simple than I would like.
 

And here is something that I found by chance when developing the code
presented in the previous post.
Unlike for the previous one, I can not prove that memory requirements
of this algorithm are O(N). However, for all my tests cases it's not
just O(N), but consumes significantly less memory than the one above.
And it is simpler and shorter.

// HIS - todo stack of Horizontal Intervals
// with periodic Squeeze of empty intervals
#include <stddef.h>
#include <stdlib.h>
#include <stdint.h>

typedef unsigned char Color;

int floodfill4(
  Color* image,
  int width, int height,
  int x,     int y,
  Color old_color, Color new_color)
{
  if (width <= 0 || height <= 0)
    return 0;

  if (x < 0 || x >= width || y < 0 || y >= height)
    return 0;

  size_t w = width;
  Color* row = &image[w*y];
  if (row[x] != old_color)
    return 0;

  typedef struct {
    int x0, x1, y;
    int8_t from; // -1 => from y-1, +1 => from y+1
  } interval_t;

  enum {
    INITIAL_STACK_SIZE = 128,
    SQUEEZE_THR        = 32,
  };
  interval_t* stack_base =
  malloc(INITIAL_STACK_SIZE*sizeof(*stack_base));
  if (!stack_base)
    return -1;
  interval_t* stack_end = &stack_base[INITIAL_STACK_SIZE];
  interval_t* todo = stack_base;

  // recolor initial horizontal interval
  row[x] = new_color;
  // look backward
  int x00;
  for (x00 = x-1; x00 >= 0 && row[x00]==old_color; --x00)
    row[x00] = new_color;
  x00 += 1;
  // look forward
  int x01;
  for (x01 = x+1; x01 < width && row[x01]==old_color; ++x01)
    row[x01] = new_color;
  x01 -= 1;

  // push neighbors of initial interval on todo stack
  for (int from = -1; from <= 1; from += 2) {
    unsigned next_y = y-from;
    if (next_y < (unsigned)height) {
      todo->x0 = x00;
      todo->x1 = x01;
      todo->y  = next_y;
      todo->from = from;
      ++todo;
    }
  }

  interval_t* squeezed = stack_base;
  unsigned periodic_i = 0;
  while (todo != stack_base) {
    --todo; // pop interval from todo stack
    int xBeg = todo->x0;
    int xEnd = todo->x1;
    int y    = todo->y;

    if (todo < squeezed)
      squeezed = todo;

    // look for target points
    Color* row = &image[y*w];
    int x = xBeg;
    do {
      if (row[x] == old_color) { // target found
        row[x] = new_color;
        int x0 = x;
        if (x == xBeg) {
          // look backward
          for (x0 = x-1; x0 >= 0 && row[x0]==old_color; --x0)
            row[x0] = new_color;
          x0 += 1;
        }
        // look forward
        int x1;
        for (x1 = x+1; x1 < width && row[x1]==old_color; ++x1)
          row[x1] = new_color;
        x1 -= 1;

        int from = todo->from;
        // remaining part of current interval
        if (x1+2 <= xEnd) {
          todo->x0 = x+2;
          todo->x1 = xEnd;
          todo->y = y;
          todo->from = from;
          ++todo;
        }
        // forward continuation
        unsigned next_y = y-from;
        if (next_y < (unsigned)height) {
          todo->x0 = x0;
          todo->x1 = x1;
          todo->y = next_y;
          todo->from = from;
          ++todo;
        }
        // bounces
        y = y+from;
        if (xEnd+2 <= x1) { // bounce on the right side
          todo->x0 = xEnd+2;
          todo->x1 = x1;
          todo->y = y;
          todo->from = -from;
          ++todo;
        }
        if (x0 <= xBeg-2) { // bounce on the left side
          todo->x0 = x0;
          todo->x1 = xBeg-2;
          todo->y = y;
          todo->from = -from;
          ++todo;
        }
        break;
      }
      ++x;
    } while (x <= xEnd);

    ++periodic_i;
    if ((periodic_i & 31)==0) { // maintenance
      if (todo - squeezed >= SQUEEZE_THR) {
        // squeeze empty intervals
        interval_t* wr = squeezed;
        while (squeezed != todo) {
          Color* row = &image[squeezed->y*w];
          for (int x = squeezed->x0; x <= squeezed->x1; ++x) {
            if (row[x] == old_color) { // interval non-empty
              *wr = *squeezed;
              wr->x0 = x;
              ++wr;
              break;
            }
          }
          ++squeezed;
        }
        todo = squeezed = wr;
      }

      if (stack_end-todo < 67) {
        // Allocate more space
        size_t todo_i = todo - stack_base;
        size_t squeezed_i = squeezed - stack_base;
        size_t sz = stack_end - stack_base;
        sz += (sz/128)*64;
        interval_t* tmp = realloc(
              stack_base, sz*sizeof(*stack_base));
        if (!tmp) {
          free(stack_base);
          return -1;
        }
        stack_base = tmp;
        stack_end = &stack_base[sz];
        todo = &stack_base[todo_i];
        squeezed = &stack_base[squeezed_i];
      }
    }
  }

  free(stack_base);
  return 1;
}