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