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