Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Malcolm McLean <malcolm.arthur.mclean@gmail.com>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety
Date: Sun, 17 Mar 2024 14:56:34 +0000
Organization: A noiseless patient Spider
Lines: 209
Message-ID: <ut70b4$3itvb$1@dont-email.me>
References: <ut3669$21eur$1@i2pn2.org> <ut4020$2s8ov$1@dont-email.me>
 <ut4b09$2uhpm$1@dont-email.me> <ut4cnc$2ut2t$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 17 Mar 2024 14:56:36 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="1302203e67d64edb589b5f20956e00a5";
	logging-data="3766251"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+0mNb3zbpYUX2Eg4Lrohecrlebe5zvdTM="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:xjzENMIi63EWgpMfGeLLvLjG3Ww=
In-Reply-To: <ut4cnc$2ut2t$1@dont-email.me>
Content-Language: en-GB
Bytes: 6327

On 16/03/2024 15:09, Malcolm McLean wrote:
> On 16/03/2024 14:40, David Brown wrote:
>> On 16/03/2024 12:33, Malcolm McLean wrote:
>>
>>> And here's some code I wrote a while ago. Use that as a pattern. But 
>>> not sure how well it works. Haven't used it for a long time.
>>>
>>> https://github.com/MalcolmMcLean/binaryimagelibrary/blob/master/drawbinary.c
>>>
>>
>> Your implementation is a mess, /vastly/ more difficult to prove 
>> correct than the OP's original one, and unlikely to be very much 
>> faster (it will certainly scale in the same way in both time and 
>> memory usage).
>>
> Now is this David Brown being David Borwn, ot its it actaully ture?

> And I need to run some tests, don't I?
> 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

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;
    grey[y*width+x] = dest;
    floodfill_r(grey, width, height, x - 1, y, target, dest);
    floodfill_r(grey, width, height, x + 1, y, target, dest);
    floodfill_r(grey, width, height, x, y - 1, target, dest);
    floodfill_r(grey, width, height, x, y + 1, target, dest);

    return 0;
}

/**
   Floodfill4 - floodfill, 4 connectivity.

   @param[in,out] grey - the image (formally it's greyscale but it could be
binary or indexed)
   @param width - image width
   @param height - image height
   @param x - seed point x
   @param y - seed point y
   @param target - the colour to flood
   @param dest - the colur to replace it by.
   @returns Number of pixels flooded.
*/
int floodfill4(unsigned char *grey, int width, int height, int x, int y,
unsigned char target, unsigned char dest)
{
   int *qx = 0;
   int *qy = 0;
   int qN = 0;
   int qpos = 0;
   int qcapacity = 0;
   int wx, wy;
   int ex, ey;
   int tx, ty;
   int ix;
   int *temp;
   int answer = 0;

   if(grey[y * width + x] != target)
     return 0;
   qx = malloc(width * sizeof(int));
   qy = malloc(width * sizeof(int));
   if(qx == 0 || qy == 0)
     goto error_exit;
   qcapacity = width;
   qx[qpos] = x;
   qy[qpos] = y;
   qN = 1;

   while(qN != 0)
   {
     tx = qx[qpos];
     ty = qy[qpos];
     qpos++;
     qN--;

     if(qpos == 256)
     {
       memmove(qx, qx + 256, qN*sizeof(int));
       memmove(qy, qy + 256, qN*sizeof(int));
       qpos = 0;
     }
     if(grey[ty*width+tx] != target)
       continue;
     wx = tx;
     wy = ty;
     while(wx >= 0 && grey[wy*width+wx] == target)
       wx--;
     wx++;
     ex = tx;
     ey = ty;
     while(ex < width && grey[ey*width+ex] == target)
       ex++;
     ex--;


     for(ix=wx;ix<=ex;ix++)
     {
       grey[ty*width+ix] = dest;
       answer++;
     }

     if(ty > 0)
       for(ix=wx;ix<=ex;ix++)
       {
	    if(grey[(ty-1)*width+ix] == target)
	    {
           if(qpos + qN == qcapacity)
	      {
             temp = realloc(qx, (qcapacity + width) * sizeof(int));
             if(temp == 0)
               goto error_exit;
             qx = temp;
             temp = realloc(qy, (qcapacity + width) * sizeof(int));
             if(temp == 0)
               goto error_exit;
             qy = temp;
             qcapacity += width;
	      }
           qx[qpos+qN] = ix;
           qy[qpos+qN] = ty-1;
           qN++;
	    }
       }
     if(ty < height -1)
       for(ix=wx;ix<=ex;ix++)
       {
         if(grey[(ty+1)*width+ix] == target)
	    {
           if(qpos + qN == qcapacity)
	      {
             temp = realloc(qx, (qcapacity + width) * sizeof(int));
             if(temp == 0)
               goto error_exit;
             qx = temp;
             temp = realloc(qy, (qcapacity + width) * sizeof(int));
             if(temp == 0)
               goto error_exit;
             qy = temp;
             qcapacity += width;
	      }
           qx[qpos+qN] = ix;
           qy[qpos+qN] = ty+1;
           qN++;
	    }
       }
   }

   free(qx);
   free(qy);

   return answer;
  error_exit:
   free(qx);
   free(qy);
   return -1;
}

int main(void)
{
    unsigned char *image;
    clock_t tick, tock;
    int i;

    image = malloc(100 * 100);
    tick = clock();
    for (i = 0 ; i < 10000; i++)
    {
========== REMAINDER OF ARTICLE TRUNCATED ==========