Path: ...!2.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Michael S <already5chosen@yahoo.com>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety - worst memory size
Date: Fri, 3 May 2024 18:33:05 +0300
Organization: A noiseless patient Spider
Lines: 339
Message-ID: <20240503183305.000079e0@yahoo.com>
References: <ut3669$21eur$1@i2pn2.org>
	<86h6h3nvyz.fsf@linuxsc.com>
	<865xxiok09.fsf@linuxsc.com>
	<20240319131842.00002138@yahoo.com>
	<86o7b9ms7d.fsf@linuxsc.com>
	<20240320115416.00001ab5@yahoo.com>
	<86zfusltwp.fsf@linuxsc.com>
	<20240324193352.000062e9@yahoo.com>
	<86jzlrk0f6.fsf@linuxsc.com>
	<20240405173033.00006145@yahoo.com>
	<868r1k1uq8.fsf@linuxsc.com>
	<20240411152033.00007173@yahoo.com>
	<86bk6ez9te.fsf@linuxsc.com>
	<20240417004609.000010aa@yahoo.com>
	<86plunyj82.fsf@linuxsc.com>
	<20240417224126.0000727a@yahoo.com>
	<86a5lpxbd3.fsf@linuxsc.com>
	<20240420211023.000067cc@yahoo.com>
	<20240425175606.000059d5@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 03 May 2024 17:33:10 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="24f79386f11d1cfdbf24e001dc1c4c6c";
	logging-data="624660"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX193zUa1HjNcbVXhorbmoQhJaI9ijqiqXGY="
Cancel-Lock: sha1:HwgZ+6vq7JAbmx51yMug/uCaUP8=
X-Newsreader: Claws Mail 4.1.1 (GTK 3.24.34; x86_64-w64-mingw32)
Bytes: 12487

On Thu, 25 Apr 2024 17:56:06 +0300
Michael S <already5chosen@yahoo.com> wrote:

> On Sat, 20 Apr 2024 21:10:23 +0300
> Michael S <already5chosen@yahoo.com> wrote:
> 
> > On Fri, 19 Apr 2024 14:59:20 -0700
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >   
> > > 
> > > Did you mean you some algorithms whose worst case memory
> > > behavior is strictly less than O( total number of pixels )?
> > > 
> > > I think it would be helpful to adopt a standard terminology
> > > where the pixel field is of size M x N, otherwise I'm not
> > > sure what O(N) refers to.
> > >     
> > 
> > No, I mean O(max(M,N)) plus possibly some logarithmic component that
> > loses significance when images grow bigger.
> > More so, if bounding rectangle of the shape is A x B then I'd like
> > memory requirements to be O(max(A,B)), but so far it does not appear
> > to be possible, or at least not possible without significant
> > complications and further slowdown. So, as an intermediate goal I am
> > willing to accept that allocation would be O(max(M,N)). but amount
> > of touched memory is O(max(A,B)).
> >   
> > > > but so
> > > > far they are all unreasonably slow - ~5 times slower than
> > > > the best.      
> > > 
> > > I'm no longer working on the problem but I'm interested to
> > > hear what you come up with.    
> > 
> >   
> 
> Here is what I had in mind.
> I tried to optimize as little as I can in order to make it as simple
> as I can. Unfortunately, I am not particularly good at it, so, code
> still contains few unnecessary "tricks" that make understanding a
> little harder.
> The code uses VLA and recursion for the same purpose of making it less
> tricky.
> If desired, the memory footprint could be easily reduced by factor of
> 8 through use of packed bit arrays instead arrays of _Bool.
> 
> Even in this relatively crude form for majority of shapes this code is
> blazingly fast.
> Unfortunately, in the worst case (both 'slalom' shapes) an execution
> time is O(max(A,B)**3) which makes it unfit as general-purpose
> routine. At the moment I don't see a solution for this problem.
> Overall, it's probably a dead end.
>

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.


#include <stddef.h>
#include <string.h>

typedef unsigned char Color;

enum coordinate_axes {
  x_i = 0, y_i,    // index of pos[], ld[], 1st index of limits[][],
todo[][] };
enum from_to {
  from_i = 0, to_i // 2nd index of limits[][], todo[][],  I use 0 and 1
more commonly };
enum { // indices of todo[] lists
  le_i = x_i*2+from_i, ri_i = x_i*2+to_i,
  up_i = y_i*2+from_i, dn_i = y_i*2+to_i,
};

#define IDX2INC(ft_idx)   ((int)(ft_idx)*2 - 1)
#define X2Y(axis)         ((axis) ^ 1)

typedef struct {
  Color* image;
  Color old_color, new_color;
  ptrdiff_t ld[2];        // {1, width}
  int       limits[2][2]; // {{0, width-1}, {0, height-1}
} floodfill4_param;

typedef struct {
  int *todo[4];     // {left,right, up, down} - first item holds the #
of active entries int limits[2][2]; // {{x0, x1}, {y0, y1}};
  int pos[2];       // {x, y}
} floodfill4_state;

static void floodfill4_core(
  const floodfill4_param* prm,
  const floodfill4_state* arg);
static _Bool floodfill4_expand(
  const floodfill4_param* prm,
  floodfill4_state* s,
  enum coordinate_axes axis, enum from_to ft_idx);

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;

  if (image[(size_t)width*y+x] != old_color)
    return 0;

  int lr_todo[2][height+1];
  int ud_todo[2][width+1];
  floodfill4_param prm = {
    .image = image,
    .ld[x_i] = 1,
    .ld[y_i] = width,
    .limits = {{ 0, width-1}, {0, height-1}},
    .old_color = old_color,
    .new_color = new_color,
  };
  floodfill4_state s = {
    .todo[le_i] = lr_todo[0],
    .todo[ri_i] = lr_todo[1],
    .todo[up_i] = ud_todo[0],
    .todo[dn_i] = ud_todo[1],
    .limits[x_i] = {x,  x},
    .limits[y_i] = {y,  y},
    .pos[x_i]  = x, .pos[y_i]  = y,
  };
  for (int i = 0; i < 4; ++i)
    *s.todo[i] = 0;

  // process central 1x1 rectangle
  floodfill4_core(&prm, &s);

  // expansion loop
  for (unsigned idx = 0; idx < 4;) {
    if (floodfill4_expand(&prm, &s, idx/2, idx % 2)) { // try to expand
      idx = 0; // expansion succeed - restart from beginning
      continue;
    }
    ++idx;
  }
========== REMAINDER OF ARTICLE TRUNCATED ==========