Bitmap/Flood fill: Difference between revisions

 

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.

[[Image:Unfilledcirc.png|128px|thumb|right]]

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

 

=={{header|Ada}}==

( Picture : in out Image;

From : Point;

Column (From);

end if;

The procedure has the following parameters. ''Picture'' is the image to change. ''From'' is the point to start at. ''Fill'' is the color to fill with. ''Replace'' is the color to replace. ''Distance'' defines the range of color around ''Replace'' to replace as well. The distance is defined as a maximum of the differences of stimuli. The following code snippet reads the test file, fills the area between two circles red, and writes the result:

File : File_Type;

begin

Close (File);

end;

=={{header|AutoHotkey}}==

* <code>x</code>, <code>y</code> are the initial coords (relative to screen unless the <code>relative</code> parameter is true).

=== Recursive ===

This is limited to %StackSize% pixels.

CoordMode, Mouse

CoordMode, Pixel

FloodFill(x-1, y-1, target, replacement, key)

}

 

=== Iterative ===

#SingleInstance, Force

 

DllCall("ReleaseDC", UInt, 0, UInt, hDC)

DllCall("DeleteObject", UInt, hBrush)

=={{header|BBC BASIC}}==

BBC BASIC has a built-in flood fill statement, but to satisfy the terms of the task it is not used in this example.

GCOL 15

CIRCLE FILL 640, 512, 500

PROCflood(X%, Y%-2, C%)

NEXT

=={{header|C}}==

===Simple and complete example in C89===

* RosettaCode: Bitmap/Flood fill, language C, dialects C89, C99, C11.

*

writePortableBitMap(stdout);

return EXIT_SUCCESS;

 

===Second example ===

// http://commons.wikimedia.org/wiki/File:Julia_immediate_basin_1_3.png

 

}

 

===Third example===

The <code>sys/queue.h</code> is not POSIX. (See [[FIFO#C|FIFO]])

 

typedef struct {

color_component red, green, blue;

void floodfill(image img, int px, int py,

rgb_color_p bankscolor,

 

 

typedef struct _ffill_node {

}

return pixelcount;

 

The '''pixelcount''' could be used to know the area of the filled region. The ''internal'' parameter <code>tolerance</code> can be tuned to cope with antialiasing, bringing "sharper" resuts.

(Comments show changes to fill the white area instead of the black circle)

 

#include <stdlib.h>

#include "imglib.h"

}

return 0;

=={{header|C sharp|C#}}==

{{works with|C#|3.0}}

This implementation matches exact colours only. Since the example image has grey pixels around the edges of the circles, these will remain grey after the interiors are filled.

 

using System;

using System.Collections.Generic;

}

}

=={{header|C++}}==

{{libheader|OpenCV}}

 

'''Interface'''

#define PROCESSING_FLOODFILLALGORITHM_H_

 

 

#endif /* PROCESSING_FLOODFILLALGORITHM_H_ */

'''Implementation'''

 

FloodFillAlgorithm::~FloodFillAlgorithm() {

}

 

=={{header|D}}==

This version uses the bitmap module from the Bitmap Task, matches exact colours only, and is derived from the Go version (to avoid stack overflow because unlike Go the D stack is not segmented).

 

 

void floodFill(Color)(Image!Color img, in uint x, in uint y,

img.floodFill(200, 200, RGB(127, 0, 0));

img.savePPM6("unfilled_circ_flooded.ppm");

=={{header|Delphi}}==

See [[#Pascal]].

Using the image type from [[Basic bitmap storage#E]].

 

def matchColor := image[x, y]

def w := image.width()

 

fillScan(x, y)

 

[[File:Filledcirc-E.png|128px|thumb|right|Filled sample image]]Note that this does not make any attempt to smoothly fill 'banks' or have a tolerance; it matches exact colors only. This will fill the example image with red inside green, and there will be black/white fringes:

 

println("Read")

def i := readPPM(<import:java.io.makeFileInputStream>(<file:Unfilledcirc.ppm>))

i.writePPM(<import:java.io.makeFileOutputStream>(<file:Filledcirc.ppm>))

println("Done")

=={{header|ERRE}}==

In "PC.LIB" library there is a FILL procedure that do the job, but the example program implements the algorithm in ERRE language using an iterative method. This program is taken from the distribution disk and works in 320x200 graphics.

PROGRAM MYFILL_DEMO

 

FLOOD_FILL(100,100,0,1)

END PROGRAM

Note: I haven't an "Upload files" item, so I can't show the resulting image!

=={{header|Euler Math Toolbox}}==

 

Using an emulated stack. EMT's recursive stack space is limited. For the notebook with images see [http://www.euler-math-toolbox.de/renegrothmann/Flood%20Fill.html this page].

 

>file="test.png";

>A=loadrgb(file); ...

>B=floodfill(B,200,200,rgb(0,0,0.5),0.5);

>insrgb(B);

=={{header|FBSL}}==

'''Using pure FBSL's built-in graphics functions:'''

#DEFINE WM_CLOSE 16

 

CIRCLE(FBSL.GETDC, Breadth / 2, Height / 2, 85, &HFFFFFF, 0, 360, 1, TRUE) _ ' White

(FBSL.GETDC, Breadth / 3, Height / 3, 30, 0, 0, 360, 1, TRUE) ' Black

'''Output:''' [[File:FBSLFlood.PNG]]

=={{header|Forth}}==

This simple recursive algorithm uses routines from [[Basic bitmap storage]].

: 3dup third third third ;

: 4dup 2over 2over ;

swap 1- swap

then

=={{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.

 

use RCImageBasic

use RCImagePrimitive

end subroutine floodfill

 

 

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

 

=={{header|FreeBASIC}}==

{{trans|BBC BASIC}}

' compile with: fbc -s console

 

Sleep 2000

If InKey <> "" OrElse InKey = Chr(255) + "k" Then End

=={{header|Go}}==

An addition to code from the bitmap task:

 

func (b *Bitmap) Flood(x, y int, repl Pixel) {

}

ff(x, y)

And a test program. Works with code from read ppm and write ppm to pipe tasks. For input, it uses a version of the test file converted by the Go solution to "Read an image through a pipe". For output it uses the trick from "PPM conversion through a pipe" to write the .png suitable for uploading to RC.

[[File:Go_flood.png|right]]

 

import (

log.Fatal(err)

}

=={{header|Haskell}}==

This code uses the Bitmap and Bitmap.RGB modules defined [[Bitmap#Haskell|here]].

import Data.STRef

import Control.Monad

setSpanRight p False

scanWhileX b st p oldC newC (w, h) (Pixel (x, y + 1))

=={{header|HicEst}}==

HicEst color fill is via the [http://www.HicEst.com/DeCoRation.htm decoration option of WRITE()]

 

WRITE(WIN=wh, DeCoRation="EL=14, BC=14") ! color 14 == bright yellow

WRITE(WIN=wh, DeCoRation="L=1/4, R=1/2, T=1/4, B=1/2, EL=25, BC=25")

 

=={{header|J}}==

'''Solution:'''<br>

Uses <code>getPixels</code> and <code>setPixels</code> from [[Basic bitmap storage#J|Basic bitmap storage]].

NB. ref: http://www.jsoftware.com/pipermail/general/2005-August/023886.html

findcontig=: (|."1@|:@:>. (* * 1&(|.!.0)))^:4^:_@(* >:@i.@$)

NB.*floodFill v Floods area, defined by point and color (x), of image (y)

NB. x is: 2-item list of (y x) ; (color)

 

'''Example Usage:'''<br>

The following draws the same image as for the [[Flood fill#Tcl|Tcl example image]] below.<br>

Uses definitions from [[Basic bitmap storage#J|Basic bitmap storage]], [[Bresenham's line algorithm#J|Bresenham's line algorithm]] and [[Midpoint circle algorithm#J|Midpoint circle algorithm]].

myimg=: white makeRGB 50 70

lines=: _2]\^:2 ] 0 0 25 0 , 25 0 25 35 , 25 35 0 35 , 0 35 0 0

myimg=: (5 34;orange) floodFill myimg

myimg=: (5 36;red) floodFill myimg

 

'''Alternative findcontig:'''<br>

The following alternative version of <code>findcontig</code> is less concise but is leaner, faster, works for n-dimensions and is not restricted to numerical arrays.

eq=:[:}:"1 [:($$[:([:+/\1:,}:~:}.),) ,&_"1 NB. equal numbers for atoms of y connected in first direction

eq_nd=: i.@#@$(<"0@[([:, |:^:_1"0 _)&> [:EQ&.> <@|:"0 _)] NB. n-dimensional eq, gives an #@$,*/@$ shaped matrix

cnnct=: [: |:@({."1<.//.]) [: ; <@(,.<./)/.~

 

=={{header|Java}}==

Input is the image, the starting node (x, y), the target color we want to fill, and the replacement color that will replace the target color. It implements a 4-way flood fill algorithm. For large images, the performance can be improved by drawing the scanlines instead of setting each pixel to the replacement color, or by working directly on the databuffer.

import java.awt.Point;

import java.awt.image.BufferedImage;

}

}

And here is an example of how to replace the white color with red from the sample image (with starting node (50, 50)):

import java.awt.Color;

import java.awt.Point;

new Test();

}

=={{header|Julia}}==

{{works with|Julia|0.6}}

Inspired to [[#Python | Python]] version.

 

 

function floodfill!(img::Matrix{<:Color}, initnode::CartesianIndex{2}, target::Color, replace::Color)

img = Gray{Bool}.(load("data/unfilledcircle.png"))

floodfill!(img, CartesianIndex(100, 100), Gray(false), Gray(true))

=={{header|Kotlin}}==

{{trans|Java}}

 

import java.awt.Color

ImageIO.write(image, "png", File(title))

JOptionPane.showMessageDialog(null, JLabel(ImageIcon(image)), title, JOptionPane.PLAIN_MESSAGE)

=={{header|Liberty BASIC}}==

NoMainWin

WindowWidth = 267.5

result = FloodFill(mouseXX, (mouseYY - 1), targetColor)

End If

=={{header|Lingo}}==

Lingo has built-in flood fill for image objects, so a custom implementation would be pointless:

=={{header|Lua}}==

Uses Bitmap class [[Bitmap#Lua|here]], with an RGB tuple pixel representation, then extending..

 

Preprocess with ImageMagick to simplify loading:

Some rudimentary PPM support:

local fp = io.open( filename, "rb" )

if fp == nil then return false end

end

fp:close()

The task itself:

local b = self:get(x, y)

if not b then return end

end

ff(x, y)

Demo:

bitmap:loadPPM("unfilledcirc.ppm")

bitmap:floodfill( 1, 1, { 255,0,0 }) -- fill exterior (except bottom right) with red

bitmap:floodfill( 50, 50, { 0,255,0 })-- fill larger circle with green

bitmap:floodfill( 100, 100, { 0,0,255 })-- fill smaller circle with blue

=={{header|Mathematica}} / {{header|Wolfram Language}}==

RegionBinarize[img, Image[SparseArray[pos -> 1, ImageDimensions[img]]], tol];

floodFill[img_Image, pos_List, tol_Real, color_List] :=

Dilation[createMask[img, pos, tol],1]

]

 

{{out}}

<pre>floodFill[Import["http://rosettacode.org/mw/images/0/0f/Unfilledcirc.png"], {100, 100}, 0.01, {1, 0, 0}]</pre>

 

=={{header|Pascal}}==

{{trans|C#}}

 

program FloodFillTest;

 

end.

=={{header|Perl}}==

 

The <tt>fill</tt> of the Perl package Image::Imlib2 is a flood fill (so the documentatin of Image::Imlib2 says). The target colour is the one of the starting point pixel; the color set with <tt>set_color</tt> is the fill colour.

 

 

use strict;

$img->fill(100,100);

$img->save("filledcirc.jpg");

 

A homemade implementation can be:

 

use Image::Imlib2;

 

floodfill($img, 100,100, 0, 0, 0);

$img->save("filledcirc1.jpg");

 

This fills better than the Image::Imlib2 <tt>fill</tt> function the inner circle, since because of JPG compression and thanks to the <tt>$distparameter</tt>, it "sees" as black also pixel that are no more exactly black.

=={{header|Phix}}==

{{Trans|Go}}

and y>=1 and y<=length(img[x])

and img[x][y]=target then

end function

 

return ff(img,x,y,colour,target)

end function

 

sequence img = read_ppm("Circle.ppm")

=={{header|PicoLisp}}==

Using the format of [[Bitmap#PicoLisp|Bitmap]], a minimal recursive solution:

(let Target (get Ppm Y X)

(recur (X Y)

(recurse X (dec Y))

(recurse X (inc Y)) ) ) )

Test using 'ppmRead' from [[Bitmap/Read a PPM file#PicoLisp]] and 'ppmWrite' from [[Bitmap/Write a PPM file#PicoLisp]], filling the white area with red:

<pre>(ppmWrite

(ppmFloodFill (ppmRead "Unfilledcirc.ppm") 192 128 (255 0 0))

"Filledcirc.ppm" )</pre>

=={{header|PL/I}}==

declare (x, y) fixed binary;

declare fill_color bit (24) aligned;

if pixel_color = area_color then call fill (x, y+1, fill_color);

 

The following PL/I statements change the color of the white area

of the sample image to red, and the central orb to green.

/* Fill the white area of the suggested image with red color. */

area_color = (24)'1'b;

area_color = '0'b;

call fill (125, 125, '000000001111111100000000'b );

=={{header|Processing}}==

import java.util.Queue;

import java.util.LinkedList;

img.pixels[pixel_position(x, y)] = fill_color;

return true;

 

==={{header|Processing Python mode}}===

 

fill_color = color(250, 0, 0)

tolerance = 15

global img

size(600, 400)

fill(0, 0, 100)

textSize(18)

text("Tolerance = {} (Use mouse wheel to change)".format(tolerance),

100, height - 30)

text("Right click to reset", 100, height - 10)

def draw():

global allowed

if allowed:

allowed = False

 

global allowed, img

if mouseButton == RIGHT:

else:

img.loadPixels()

return False

img.pixels[pixel_position(x, y)] = fill_color

=={{header|PureBasic}}==

=== built-in ===

 

=== Iterative ===

old_color = Point(x,y)

NewList stack.POINT()

Event = WaitWindowEvent()

Until Event = #PB_Event_CloseWindow

=={{header|Python}}==

import Image

def FloodFill( fileName, initNode, targetColor, replaceColor ):

break

return img

 

===Usage example===

# "FloodFillClean.png" is name of input file

# [55,55] the x,y coordinate where fill starts

#The resulting image is saved as Filled.png

img.save( "Filled.png" )

=={{header|R}}==

'''Stack-based recursive version'''

library(png)

img <- readPNG("Unfilledcirc.png")

 

image(M, col = c(1, 0, 2))

'''Queue-based version (Forest Fire algorithm)'''

library(png)

img <- readPNG("Unfilledcirc.png")

 

image(M, col = c(1, 0, 2, 3))

=={{header|Racket}}==

#lang racket

 

;; ... and after:

bm

=={{header|Raku}}==

(formerly Perl 6)

Using bits and pieces from various other bitmap tasks.

 

class Bitmap {

has Int ($.width, $.height);

 

$outfile.write: $b.P6;

 

See output image [https://github.com/thundergnat/rc/blob/master/img/Bitmap-flood-perl6.png Bitmap-flood-perl6 ] (offsite image file, converted to PNG for ease of viewing)

=={{header|REXX}}==

{{trans|PL/I}}

black= '000000000000000000000000'b /*define the black color (using bits).*/

red = '000000000000000011111111'b /* " " red " " " */

return

/*──────────────────────────────────────────────────────────────────────────────────────*/

<br><br>

=={{header|Ruby}}==

 

Uses [[Raster graphics operations/Ruby]]

 

 

require_relative 'raster_graphics'

 

class RGBColour

end

end

current_colour = self[pixel.x, pixel.y]

queue = Queue.new

until queue.empty?

next unless self[p.x, p.y] == current_colour

 

%i[north south].each do |direction|

n = neighbour(q, direction)

end

q = neighbour(q, :east)

bitmap.draw_circle(Pixel[200, 100], 40, RGBColour::BLACK)

bitmap.flood_fill(Pixel[140, 160], RGBColour::BLUE)

 

{{libheader|RubyGems}}

JRubyArt is a port of Processing to the ruby language

 

Pixel = Struct.new(:x, :y)

 

size(256, 256)

end

=={{header|Rust}}==

 

/* Naive Rust implementation of RosettaCode's Bitmap/Flood fill excercise.

*

write_image(data);

 

=={{header|Scala}}==

 

See [[Basic_bitmap_storage#Scala|Basic Bitmap Storage]] for RgbBitmap class.

 

import scala.collection.mutable

 

}

}

=={{header|Standard ML}}==

This implementation is imperative, updating the pixels of the image as it goes.

data structures instead.

 

* fundamental would change if we used more colors. *)

datatype color = Black | White

 

(* Fill the image with black starting at the center. *)

=={{header|Tcl}}==

{{libheader|Tk}}

{{tcllib|struct::queue}}

Using code from [[Basic bitmap storage#Tcl|Basic bitmap storage]], [[Bresenham's line algorithm#Tcl|Bresenham's line algorithm]] and [[Midpoint circle algorithm#Tcl|Midpoint circle algorithm]]

package require Tk

package require struct::queue

toplevel .flood

label .flood.l -image $img

Results in:

 

[[Image:Tcl_flood_fill.png]]

 

=={{header|XPL0}}==

[[File:FloodXPL0.gif|right|Output]]

 

proc Flood(X, Y, C, C0); \Fill an area of color C0 with color C

if ChIn(1) then []; \wait for keystroke

SetVid(3); \restore normal text mode

=={{header|zkl}}==

[[file:Flood_before.zkl.jpg|right]][[file:Flood.zkl.jpg|right]]

Uses the PPM class from http://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm#zkl

 

targ,h,w:=pixmap[x,y], pixmap.h,pixmap.w;

stack:=List(T(x,y));

}

}

pixmap.circle(101,200,100,0); pixmap.circle(75,100,25,0);

 

flood(pixmap, 75,100, 0x00|00|F0);

 

{{omit from|AWK}}

{{omit from|Lotus 123 Macro Scripting}}

{{omit from|PARI/GP}}