An Efficient Flood Visit Algorithm

Listing 3 An algorithm that tests uflood.c and flood.c

/*******************************************************
 * FLOODTST.C -- exercise the flood visit algorithm.
 *
 * This module assumes a 100 by 100 coordinate space.
 * Called routines in other modules are responsible
 * for mapping these virtual coordinates to whatever
 * coordinate space is actually supported by the video
 * hardware before performing requested operations.
 *
 * for ANSI C
 *
 * by Anton Treuenfels
 * last revision:  04/11/94
 ******************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <time.h>

#include "usrdef.h"
#include "bgigrh.h"
#include "bgipixel.h"
#include "egapixel.h"

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

/* fill empty screen */

static void set_test0(int *seedx, int *seedy) {

   *seedx = *seedy = 50;
}

/* fill empty box */

static void set_test1(int *seedx, int *seedy) {

   grhrect(10, 10, 90, 90);
   *seedx = *seedy = 50;
}

/* fill space between concentric boxes */

static void set_test2(int *seedx, int *seedy) {

   grhrect(10, 10, 90, 90);
   grhrect(30, 30, 70, 70);
   *seedx = 15; *seedy = 50;
}

/* fill large open non--convex figure */

static void set_test3(int *seedx, int *seedy) {

   grhrect(10, 10, 90, 90);
   grhfpair(20, 20, 80, 80);
   *seedx = 15; *seedy = 50;
}

/* draw staggered arrangement */

static void drawstaggered(int *seedx, int *seedy, int dx, int dy,
                      void (*figure)(int, int, int, int)) {

   int ix, iy, i, j;
   
   ix = 3 * dx; iy = 3 * dy / 2;
   
   for (i = dx/2; i < 100 -- dx; i += ix) {
      for (j = dy/2; j < 100 -- dy; j += iy) 
         (*figure)(i, j, i+dx, j+dy);
   }
   
   for (i = 2*dx; i < 100 -- dx; i += ix) {
      for (j = dy; j < 100 -- dy; j += iy)
         (*figure)(i, j, i+dx, j+dy);
   }
   
   *seedx = 2 * dx; *seedy = dy / 2;
}

/* fill staggered boxes */

static void set_test4(int *sx, int *sy) {

   drawstaggered(sx, sy, 2, 3, grhrect);
}

/* fill staggered circles */

static void set_test6(int *sx, int *sy) {

   drawstaggered(sx, sy, 2, 3, grhcircle);
}

/* fill staggered open non--convex figures */

static void set_test8(int *sx, int *sy) {

   drawstaggered(sx, sy, 8, 9, grhfpair);
}

/* draw regularly spaced arrangement */

static void drawregular(int *seedx, int *seedy, int dx, int dy,
                    void (*figure)(int, int, int, int)) {

   int ix, iy, i, j;
   
   ix = 3 * dx / 2;  iy = 3 * dy / 2;
   
   for (i = dx/2; i < 100 -- dx; i += ix) {
      for (j = dy/2; j < 100 -- dy; j += iy)
         (*figure)(i, j, i+dx, j+dy);
   }
   
   *seedx = 0; *seedy = 50;
}

/* fill regular boxes */

static void set_test5(int *sx, int *sy) {

   drawregular(sx, sy, 2, 3, grhrect);
}

/* fill regular circles */

static void set_test7(int *sx, int *sy) {

   drawregular(sx, sy, 2, 3, grhcircle);
}

/* fill random figures */

static void set_test9(int *seedx, int *seedy) {

   void (*draw[])(int, int, int, int) = {
      grhrect, grhcircle, grhfpair
      };

   int i, j, dx, dy, rx, ry;
   int lft, top, bot, rgt;
   
   dx = 10; dy = 10;
   
   rx = dx/2; ry = dy/2;
   
   randomize();
   
   for (i = 2; i < 100 -- 2* dx; i += dx) {
      for (j = 0; j < 100 -- 2 * dx; j += dy) {
         lft = i + random(rx);
         top = j + random(ry);
         rgt = lft + random(dx) + rx;
         bot = top + random(ry) + dy;
         (*draw[random(3)])(lft, top, rgt, bot);
      }
   }
   
   *seedx = 1; *seedy = 50;
}

/* wait for and return one char from keyboard */

static int onechar(void) {
   fflush(stdin);
   return(toupper(getchar()));
}

/* execute test */

static void xtest(int num, Boolean fastfill, Boolean fastvisit) {

   void (*settest[])(int *, int *) = {
      set_test0, set_test1, set_test2,
      set_test3, set_test4, set_test5,
      set_test6, set_test7, set_test8,
      set_test9
      };

   int x, y;
   
   grhopen();
   (*settest[num])(&x, &y);
   if (fastvisit)
      egaflood(x, y, fastfill);
   else
      checkflood(x, y, fastfill);
   (void)onechar();
   grhclose();
}

/* da supervisor */

int main(void) {

   int c;
   Boolean keepgoing, fastfill, fastvisit;
   
   fastfill = fastvisit = FALSE;
   keepgoing = TRUE;
   while (keepgoing) {
      printf("\n\n%s fill algorithm enabled.",
            fastfill ? "Optimized" : "Unoptimized");
      printf("\n%s visit function enabled.",
            fastvisit ? "Fast" : "Checking");
      printf("\n\nCommands: 0-->9= test,");
      printf(" F)iller, V)isitor, Q)uit");
      printf("\nWhat next?  ");
      c = onechar();
      if (isdigit(c))
         xtest(c -- '0', fastfill, fastvisit);
      else {
         switch (c) {
         case 'F':
            fastfill = !fastfill;
            break;
         case 'V':
            fastvisit = !fastvisit;
            break;
         case 'Q': case EOF:
            keepgoing = FALSE;
            break;
         default:
            printf("\nDon't know that choice");
         }
      }
   }
   return(EXIT_SUCCESS);
}

/* End of File