Bitmap/Flood fill
You are encouraged to solve this task according to the task description, using any language you may know.
Implement a flood fill.
A flood fill is a way of filling an area using color banks to define the area. (In the Wikipedia therminology, the color banks is the targetcolor). It works almost like a water flooding from a point towards the banks: if there's a hole in the banks, the flood is not contained and all the image get filled.
To accomplish the task, you need implementing just one of the possible algorithms (examples are on Wikipedia. Variations on the theme are allowed (e.g. adding a tolerance parameter or argument for color-matching of the banks color).
Testing: the basic algorithm is not suitable for truecolor images; a possible test image is the one shown on the right box; you can try to fill the white area, or the black inner circle.
C
The sys/queue.h is not POSIX. (See FIFO)
<lang c>#include <math.h>
- include <sys/queue.h>
typedef struct {
color_component red, green, blue;
} rgb_color; typedef rgb_color *rgb_color_p;
typedef struct _ffill_node {
int px, py; TAILQ_ENTRY(_ffill_node) nodes;
} _ffill_node_t; TAILQ_HEAD(_ffill_queue_s, _ffill_node); typedef struct _ffill_queue_s _ffill_queue;
inline void _ffill_removehead(_ffill_queue *q) {
_ffill_node_t *n = q->tqh_first;
if ( n != NULL ) {
TAILQ_REMOVE(q, n, nodes);
free(n);
}
}
inline void _ffill_enqueue(_ffill_queue *q, int px, int py) {
_ffill_node_t *node;
node = malloc(sizeof(_ffill_node_t));
if ( node != NULL ) {
node->px = px; node->py = py;
TAILQ_INSERT_TAIL(q, node, nodes);
}
}
inline double color_distance( rgb_color_p a, rgb_color_p b ) {
return sqrt( (double)(a->red - b->red)*(a->red - b->red) +
(double)(a->green - b->green)*(a->green - b->green) + (double)(a->blue - b->blue)*(a->blue - b->blue) ) / (256.0*sqrt(3.0)); }
inline void _ffill_rgbcolor(image img, rgb_color_p tc, int px, int py) {
tc->red = GET_PIXEL(img, px, py)[0]; tc->green = GET_PIXEL(img, px, py)[1]; tc->blue = GET_PIXEL(img, px, py)[2];
}
- define NSOE(X,Y) do { \
if ( ((X)>=0)&&((Y)>=0) && ((X)<img->width)&&((Y)<img->height)) { \
_ffill_rgbcolor(img, &thisnode, (X), (Y)); \
if ( color_distance(&thisnode, bankscolor) > tolerance ) { \
if (color_distance(&thisnode, rcolor) > 0.0) { \ put_pixel_unsafe(img, (X), (Y), rcolor->red, \ rcolor->green, \ rcolor->blue); \ _ffill_enqueue(&head, (X), (Y)); \ pixelcount++; \ } \
} \ } \ } while(0)
unsigned int floodfill(image img, int px, int py,
rgb_color_p bankscolor,
rgb_color_p rcolor)
{
_ffill_queue head; rgb_color thisnode; unsigned int pixelcount = 0; double tolerance = 0.05;
if ( (px < 0) || (py < 0) || (px >= img->width) || (py >= img->height) ) return;
TAILQ_INIT(&head);
_ffill_rgbcolor(img, &thisnode, px, py); if ( color_distance(&thisnode, bankscolor) <= tolerance ) return;
_ffill_enqueue(&head, px, py);
while( head.tqh_first != NULL ) {
_ffill_node_t *n = head.tqh_first;
_ffill_rgbcolor(img, &thisnode, n->px, n->py);
if ( color_distance(&thisnode, bankscolor) > tolerance ) {
put_pixel_unsafe(img, n->px, n->py, rcolor->red, rcolor->green, rcolor->blue);
pixelcount++;
}
int tx = n->px, ty = n->py;
_ffill_removehead(&head);
NSOE(tx - 1, ty);
NSOE(tx + 1, ty);
NSOE(tx, ty - 1);
NSOE(tx, ty + 1);
}
return pixelcount;
}</lang>
The pixelcount could be used to know the area of the filled region. The internal parameter tolerance can be tuned to cope with antialiasing, bringing "sharper" resuts.
Usage example
(Comments show changes to fill the white area instead of the black circle)
<lang c>#include <stdio.h>
- include <stdlib.h>
- include "imglib.h"
int main(int argc, char **argv) {
image animage; rgb_color ic; rgb_color rc;
if ( argc > 1 ) {
animage = read_image(argv[1]);
if ( animage != NULL ) {
ic.red = 255; /* = 0; */
ic.green = 255; /* = 0; */
ic.blue = 255; /* = 0; */
rc.red = 0;
rc.green = 255;
rc.blue = 0;
floodfill(animage, 100, 100, &ic, &rc);
/* 150, 150 */
print_jpg(animage, 90);
free(animage);
}
}
return 0;
}</lang>