An Efficient Flood Visit Algorithm

Listing 1 An algorithm which prevents a child's shadow from falling on its parent line

/*****************************************************
 * UFLOOD.C - unoptimized flood visit
 *
 * for ANSI C
 *
 * by Anton Treuenfels
 * last revision:  04/12/94
 ****************************************************/

/*****************************
 * HEADER SECTION - UFLOOD.H *
 ****************************/

#ifndef SEEN_UFLOOD
#define SEEN_UFLOOD

/* function prototype */

int uflood(int, int, int (*)(int. int));

#endif

/***************************
 * CODE SECTION - UFLOOD.C *
 **************************/

#include <stdlib.h>

#include "usrdef.h"

/* line shadow */

typedef struct shdw {
   struct shdw *next;  /* forward link */
   int lft, rgt;       /* endpoints */
   int row, par;       /* row and parent row */
   Boolean ok;         /* valid flag */
} shadow;

/* shadow variables */

static shadow *seedShadow;  /* current shadow */
static shadow *shadowHead;  /* other pending shadows */

/* visit coordinate function */

static int (*isInterior)(int, int);

/****************************************************/

/* make new shadow */

static void newshadow(int slft, int srgt, int srow, int prow) {

   shadow *new;

   if ((new = malloc(sizeof(shadow))) == NULL)
      exit(EXIT_FAILURE);

   new->lft = slft;    new->rgt = srgt;
   new->row = srow;    new->par = prow;
   new->ok = TRUE;
   new->next = shadowHead;
   shadowHead = new;
}

/* clip off ends of overlapped shadow */

static void clipshadow(shadow *s, shadow *clip) {

   if (s->lft < (clip->lft - 1))
      newshadow(s->lft, clip->lft - 2, s->row, s->par);
   if (s->rgt > (clip->rgt + 1))
      newshadow(clip->rgt + 2, s->rgt, s->row, s->par);
}

/* remove overlapped segment from shadow pair */

static void removeoverlap(shadow *o) {

   shadow *s;

   for (s = shadowHead; s; s = s->next) {
      if ((s->row == o->par) && (s->ok) &&
         (s->lft <= o->rgt) && (s->rgt >= o->lft)) {
            clipshadow(s, o);
            if (o != seedShadow)
               clipshadow(o, s);
            s->ok= o->ok = FALSE;
            return;
      }
   }
}

/* make shadows of one child line */

static void makeshadows(int lft, int rgt, int row) {

   shadow *p;

   newshadow(lft, rgt, row + 1, row);
   newshadow(lft, rgt, row - 1, row);

   removeoverlap(seedShadow);

   for (p = shadowHead; p; p = p->next) {
      if ((p->row == row) && (p->ok) &&
            !((p->lft > rgt) || (p->rgt < lft)))
         removeoverlap(p);
   }
}

/* fill all child lines found within one shadow */

static void fillshadow(void) {

   int col, row, lft;

    row = seedShadow->row;

   for (col = seedShadow->lft; col <= seedShadow->rgt;
          col++) {
      if ((*isInterior)(col, row)) {
         if ((lft = col) == seedShadow->lft) {
            while ((*isInterior)(--lft, row))
               ;
            lft++;
         }
         while ((*isInterior)(++col, row))
            ;

         makeshadows(lft, col - 1, row);
      }
   }
}

/* flood visit */

int uflood(int seedx, int seedy, int (*visit)(int, int)) {

   isInterior = visit;
   shadowHead = NULL;
   newshadow(seedx, seedx, seedy. seedy);
   while (shadowHead) {
      seedShadow = shadowHead;
      shadowHead = shadowHead-->next;
      if (seedShadow-->ok)
         fillshadow();
      free(seedShadow);
   }
}

/* End of File