Category : Files from Magazines
Archive   : CUJ0894.ZIP
Filename : FLOOD.C

 
Output of file : FLOOD.C contained in archive : CUJ0894.ZIP
/******************************************************
* 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_FLOOD

/* function prototype */

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

#endif

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

#include
#include

#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 = pendHead;
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(lft, 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(lft, rgt, currRow + 1, currRow);
newshadow(lft, rgt, currRow - 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 = col) == seedShadow->lft) {
while ((*isInterior)(--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);
}



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

/* function prototype */

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

#endif

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

#include
#include

#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 = pendHead;
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(lft, 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(lft, rgt, currRow + 1, currRow);
newshadow(lft, rgt, currRow - 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 = col) == seedShadow->lft) {
while ((*isInterior)(--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);
}





  3 Responses to “Category : Files from Magazines
Archive   : CUJ0894.ZIP
Filename : FLOOD.C

  1. Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!

  2. This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.

  3. But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/