An Efficient Flood Visit Algorithm

Listing 2 An algorithm that improves on uflood.c

/*********************************************************
 * FLOOD.C -- optimized flood visit
 *
 * This algorithm visits once each all 4--way connected
 * interior points on a finite plane which share a common
 * property, given a starting point which has the property
 * and a function which can determine whether any given
 * point also has it. The common points need not form a
 * convex region, that is, islands and peninsulas bounded
 * by points which do not share the common property may
 * exist within the region of points which do.
 *
 * for ANSI C
 *
 * by Anton Treuenfels
 * last revision:  04/12/94
 *
 * references:
 * Lieberman, Henry, "How To Color In A Coloring Book",
 *   in Computer Graphics. Vol. 12, No. 3, Aug 1978
 * Polik, William F., "Area Filling Algorithms",
 *   in Computer Language, Vol. 3, No. 5, May 1986
 * Wilton, Richard, "PC & PS/2 Video Systems",
 *   Microsoft Press, 1987
 *********************************************************/

/***************************
 *HEADER SECTION -- FLOOD.H *
 **************************/

#ifndef SEEN_FLOOD
#define SEEN_FL00D

/* function prototype */

int flood(int, int, int (*)(int, int));

#endif

/**************************
 * CODE SECTION -- FLOOD.C *
 *************************/

#include <stdlib.h>
#include <setjmp.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 int currRow;         /* current row */
static shadow *seedShadow;  /* current shadow */
static shadow *rowHead;     /* current row shadows */
static shadow *pendHead;    /* other pending shadows */
static shadow *freeHead;    /* unused shadow nodes */

/* visit coordinate function */

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

/* error recovery buffer */

static jmp_buf errBuf;

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

/* release shadow nodes */

static void freeshadows(shadow *s) {

   shadow *t;

   while (s) {
      t = s-->next;
      free(s);
      s = t;
   }
}

/* make new shadow */

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

   shadow *new;

   if ((new = freeHead) != NULL)
      freeHead = freeHead-->next;
   else if ((new = malloc(sizeof(shadow))) == NULL) {
      freeshadows(rowHead);
      freeshadows(pendHead);
      longjmp(errBuf, !0);
   }

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

/* make list of all shadows on one row */

static void makerow(void) {

   shadow *s, *t, *u;
   
   t = pendHead;
   pendHead = NULL;
   while ((s = t) != NULL) {
      t = t-->next;
      if (s-->ok) {
         if (rowHead == NULL) {
            currRow = s-->row;
            s-->next = NULL;
            rowHead = s;
         }
         else if (s-->row == currRow) {
            if (s-->lft <= rowHead-->lft) {
               s-->next = rowHead;
               rowHead = s;
            }
            else {
               for (u = rowHead; u-->next; u = u-->next)
                  if (s-->lft <= u-->next-->lft)
                     break;
               s-->next = u-->next;
               u-->next = s;
            }
         }
         else {
            s-->next = pendHead;
            pendHead = s;
         }
      }
      else {
         s-->next = freeHead;
         freeHead = s;
      }
   }
}

/* make new shadow(s) that don't overlap lines */

static void clipshadow(int lft, int rgt, int row, shadow *line) {

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

/* discard shadow segments which overlap lines */

static void removeoverlap(shadow *rw) {

   shadow *chld;

   for (chld = pendHead; chld-->row != rw-->par; chld = chld-->next)
      ;
   clipshadow(chld-->lft, chld-->rgt, chld-->row, rw);

   if (rw-->rgt > (chld-->rgt + 1))
      rw-->lft = chld-->rgt + 2;
   else
      rw-->ok = FALSE;
   chld-->ok = FALSE;
}

/* make shadows of one child line */

static void makeshadows(int lft, int rgt) {

   shadow *p;
   
   if (currRow > seedShadow-->par) {
      newshadow(1ft; rgt, currRow + 1, currRow);
      clipshadow(lft, rgt, currRow -- 1, seedShadow);
   }
   else if (currRow < seedShadow-->par) {
      newshadow(lft, rgt, currRow -- 1, currRow);
      clipshadow(lft, rgt, currRow + 1, seedShadow);
   }
   else {
      newshadow(1ft, rgt, currRow + 1, currRow);
      newshadow(1ft, rgt, curtRow -- 1, currRow);
   }
   
   for (p = rowHead; p && (p-->lft <= rgt); p = p-->next)
      if (p-->ok)
         removeoverlap(p);
}

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

static void visitshadow(void) {
   
   int col, lft;
   
   for (col = seedShadow-->lft; col <= seedShadow-->rgt; col++) {
      if ((*isInterior)(col, currRow)) {
         if ((lft = cold == seedShadow-->lft) {
            while ((*islnterior)(--lft, currRow))
               ;
            lft++;
         }
         while ((*isInterior)(++col, currRow))
            ;
            
         makeshadows(lft, col -- 1);
      }
   }
}

/* flood visit */

static void doflood(int seedx, int seedy, int (*visit)(int, int)) {

   isInterior = visit;
   pendHead = rowHead = freeHead = NULL;
   newshadow(seedx, seedx, seedy, seedy);
   while (pendHead) {
      makerow();
      while (rowHead) {
         seedShadow = rowHead;
         rowHead = rowHead-->next;
         if (seedShadow-->ok)
            visitshadow();
         seedShadow-->next = freeHead;
         freeHead = seedShadow;
      }
   }
   freeshadows(freeHead);
}

/* execute flood visit through guard function */

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

   if (setjmp(errBuf) != 0)
      return(FAIL);
   doflood(seedx, seedy, visit);
   return(OK);
}

/* End of File */