Path: ...!weretis.net!feeder8.news.weretis.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
Date: Tue, 19 Mar 2024 15:49:00 +0200
Organization: A noiseless patient Spider
Lines: 124
Message-ID: <20240319154900.00001dca@yahoo.com>
References: <ut3669$21eur$1@i2pn2.org>
	<86h6h3nvyz.fsf@linuxsc.com>
	<865xxiok09.fsf@linuxsc.com>
	<20240319131842.00002138@yahoo.com>
	<utbuk3$qed7$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Info: dont-email.me; posting-host="a8871862f6b018cf47b195a984142ca8";
	logging-data="789293"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/S2BWZBvAqPTkTnU9Doe5wReFkv5XiCVs="
Cancel-Lock: sha1:DRppXLT87mFrrT7/WNl6m7fcKJs=
X-Newsreader: Claws Mail 3.19.1 (GTK+ 2.24.33; x86_64-w64-mingw32)
Bytes: 5676

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