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 */