Bitmap/Flood fill: Difference between revisions

From Rosetta Code
Content added Content deleted
(correction on the task text (and wikipedia terminology))
(fortran)
Line 147: Line 147:
return 0;
return 0;
}</lang>
}</lang>

=={{header|Fortran}}==
{{works with|Fortran|90 and later}}

Here the ''target color'' paradigm is used. Again the <code>matchdistance</code> parameter can be tuned to ignore small differences that could come because of antialiasing.

<lang fortran>module RCImageArea
use RCImageBasic
use RCImagePrimitive
implicit none

real, parameter, private :: matchdistance = 0.2

private :: northsouth, eastwest

contains

subroutine northsouth(img, p0, tcolor, fcolor)
type(rgbimage), intent(inout) :: img
type(point), intent(in) :: p0
type(rgb), intent(in) :: tcolor, fcolor

integer :: npy, spy, y
type(rgb) :: pc

npy = p0%y - 1
do
if ( inside_image(img, p0%x, npy) ) then
call get_pixel(img, p0%x, npy, pc)
if ( ((pc .dist. tcolor) > matchdistance ) .or. ( pc == fcolor ) ) exit
else
exit
end if
npy = npy - 1
end do
npy = npy + 1
spy = p0%y + 1
do
if ( inside_image(img, p0%x, spy) ) then
call get_pixel(img, p0%x, spy, pc)
if ( ((pc .dist. tcolor) > matchdistance ) .or. ( pc == fcolor ) ) exit
else
exit
end if
spy = spy + 1
end do
spy = spy - 1
call draw_line(img, point(p0%x, spy), point(p0%x, npy), fcolor)
do y = min(spy, npy), max(spy, npy)
if ( y == p0%y ) cycle
call eastwest(img, point(p0%x, y), tcolor, fcolor)
end do
end subroutine northsouth


subroutine eastwest(img, p0, tcolor, fcolor)
type(rgbimage), intent(inout) :: img
type(point), intent(in) :: p0
type(rgb), intent(in) :: tcolor, fcolor

integer :: npx, spx, x
type(rgb) :: pc

npx = p0%x - 1
do
if ( inside_image(img, npx, p0%y) ) then
call get_pixel(img, npx, p0%y, pc)
if ( ((pc .dist. tcolor) > matchdistance ) .or. ( pc == fcolor ) ) exit
else
exit
end if
npx = npx - 1
end do
npx = npx + 1
spx = p0%x + 1
do
if ( inside_image(img, spx, p0%y) ) then
call get_pixel(img, spx, p0%y, pc)
if ( ((pc .dist. tcolor) > matchdistance ) .or. ( pc == fcolor ) ) exit
else
exit
end if
spx = spx + 1
end do
spx = spx - 1
call draw_line(img, point(spx, p0%y), point(npx, p0%y), fcolor)
do x = min(spx, npx), max(spx, npx)
if ( x == p0%x ) cycle
call northsouth(img, point(x, p0%y), tcolor, fcolor)
end do
end subroutine eastwest

subroutine floodfill(img, p0, tcolor, fcolor)
type(rgbimage), intent(inout) :: img
type(point), intent(in) :: p0
type(rgb), intent(in) :: tcolor, fcolor
type(rgb) :: pcolor

if ( .not. inside_image(img, p0%x, p0%y) ) return
call get_pixel(img, p0%x, p0%y, pcolor)
if ( (pcolor .dist. tcolor) > matchdistance ) return

call northsouth(img, p0, tcolor, fcolor)
call eastwest(img, p0, tcolor, fcolor)
end subroutine floodfill

end module RCImageArea</lang>

Usage example excerpt (which on the test image will fill with green the inner black circle):

<lang fortran> call floodfill(animage, point(100,100), rgb(0,0,0), rgb(0,255,0))</lang>

Revision as of 15:17, 19 February 2009

Task
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 contained area or a target color which "determines" the area (the valley that can be flooded; Wikipedia uses the term target color). It works almost like a water flooding from a point towards the banks (or: inside the valley): if there's a hole in the banks, the flood is not contained and all the image (or all the "connected valleys") 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 or target color).

File:Unfilledcirc.jpg

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>

  1. 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];

}


  1. 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>

  1. include <stdlib.h>
  2. 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>

Fortran

Works with: Fortran version 90 and later

Here the target color paradigm is used. Again the matchdistance parameter can be tuned to ignore small differences that could come because of antialiasing.

<lang fortran>module RCImageArea

 use RCImageBasic
 use RCImagePrimitive
 implicit none
 real, parameter, private :: matchdistance = 0.2
 private :: northsouth, eastwest

contains

 subroutine northsouth(img, p0, tcolor, fcolor)
   type(rgbimage), intent(inout) :: img
   type(point), intent(in) :: p0
   type(rgb), intent(in) :: tcolor, fcolor
   integer :: npy, spy, y
   type(rgb) :: pc
   npy = p0%y - 1
   do
      if ( inside_image(img, p0%x, npy) ) then
         call get_pixel(img, p0%x, npy, pc)
         if ( ((pc .dist. tcolor) > matchdistance ) .or. ( pc == fcolor ) ) exit
      else
         exit
      end if
      npy = npy - 1
   end do
   npy = npy + 1
   spy = p0%y + 1
   do
      if ( inside_image(img, p0%x, spy) ) then
         call get_pixel(img, p0%x, spy, pc)
         if ( ((pc .dist. tcolor) > matchdistance ) .or. ( pc == fcolor ) ) exit
      else
         exit
      end if
      spy = spy + 1       
   end do
   spy = spy - 1
   call draw_line(img, point(p0%x, spy), point(p0%x, npy), fcolor)
   
   do y = min(spy, npy), max(spy, npy)
      if ( y == p0%y ) cycle
      call eastwest(img, point(p0%x, y), tcolor, fcolor)
   end do
   
 end subroutine northsouth


 subroutine eastwest(img, p0, tcolor, fcolor)
   type(rgbimage), intent(inout) :: img
   type(point), intent(in) :: p0
   type(rgb), intent(in) :: tcolor, fcolor
   integer :: npx, spx, x
   type(rgb) :: pc
   npx = p0%x - 1
   do
      if ( inside_image(img, npx, p0%y) ) then
         call get_pixel(img, npx, p0%y, pc)
         if ( ((pc .dist. tcolor) > matchdistance ) .or. ( pc == fcolor ) ) exit
      else
         exit
      end if
      npx = npx - 1
   end do
   npx = npx + 1
   spx = p0%x + 1
   do
      if ( inside_image(img, spx, p0%y) ) then
         call get_pixel(img, spx, p0%y, pc)
         if ( ((pc .dist. tcolor) > matchdistance ) .or. ( pc == fcolor ) ) exit
      else
         exit
      end if
      spx = spx + 1       
   end do
   spx = spx - 1
   call draw_line(img, point(spx, p0%y), point(npx, p0%y), fcolor)
   
   do x = min(spx, npx), max(spx, npx)
      if ( x == p0%x ) cycle
      call northsouth(img, point(x, p0%y), tcolor, fcolor)
   end do
   
 end subroutine eastwest
 subroutine floodfill(img, p0, tcolor, fcolor)
   type(rgbimage), intent(inout) :: img
   type(point), intent(in) :: p0
   type(rgb), intent(in) :: tcolor, fcolor
   
   type(rgb) :: pcolor
   if ( .not. inside_image(img, p0%x, p0%y) ) return
   call get_pixel(img, p0%x, p0%y, pcolor)
   if ( (pcolor .dist. tcolor) > matchdistance ) return
   call northsouth(img, p0, tcolor, fcolor)
   call eastwest(img, p0, tcolor, fcolor)
 end subroutine floodfill

end module RCImageArea</lang>

Usage example excerpt (which on the test image will fill with green the inner black circle):

<lang fortran> call floodfill(animage, point(100,100), rgb(0,0,0), rgb(0,255,0))</lang>