How to do a flood fill operation in Java ?

Java does provide API to fill a simple shape with a specified color. So why do we want to write a flood fill program ?

The answer is :

1. API belongs to public. Knowledge belongs to yourself.
2. Self written method is sometimes more flexible than API.

The algorithm for flood fill is simple :

1. Starts with any pixel inside the shape to be filled.
2. Remember the color of this pixel, name it as initialColor.
3. Add the initial point to the examination list
4. For all point P in the examination list do
• If P.color = initialColor then
• Fill point P with the target color
• Add all neighboring pixels of point P to the examination list

This leads to the following implementation :

  public static void floodFill(BufferedImage image, int x,int y, int fillColor)
  {
    java.util.ArrayList<Point> examList=new java.util.ArrayList<Point>();

    int initialColor=image.getRGB(x,y);
    examList.add(new Point(x,y));

    while (examList.size()>0)
    {
      Point p = examList.remove(0);  // get and remove the first point in the list
      if (image.getRGB(p.x,p.y)==initialColor) 
      {
        x = p.x;  y = p.y;
        image.setRGB(x, y, fillColor);  // fill current pixel

        examList.add(new Point(x-1,y));        // check west neighbor
        examList.add(new Point(x+1,y));        // check east neighbor
        examList.add(new Point(x,y-1));        // check north neighbor
        examList.add(new Point(x,y+1));        // check south neighbor

        repaintAndDelay(image);    // this line can be removed
      }
    }
  }

The method repaintAndDelay() is just for showing how the shape is actually filled. You may remove it if you wish.

Full runnable source code follows :

/******************************************************************************
* File : AnimationFiller.java
* Author : http://java.macteki.com/
* Description :
*   Demonstrate a flood fill algorithm.
* Tested with : JDK 1.6
******************************************************************************/

import java.awt.image.BufferedImage;
import javax.swing.JLabel;
import javax.swing.ImageIcon;
import java.awt.Point;

class AnimationFiller
{
  
  // fill the whole image with a color specified by its RGB component
  static void fillImage(BufferedImage image, int red, int green, int blue)
  {
    int packedRGB = (red*256+green)*256+blue;

    for (int y=0;y<image.getHeight(null);y++)
    {
      for (int x=0;x<image.getWidth(null);x++)
        image.setRGB(x,y,packedRGB);
    }
  }

  // draw a red circle with a pen width of 5 pixels
  static void drawCircle(BufferedImage image)
  {
    java.awt.Graphics2D gr=(java.awt.Graphics2D) image.getGraphics(); 

    gr.setColor(new java.awt.Color(255,0,0));  // red
    gr.setStroke(new java.awt.BasicStroke(5));  // set pen width to 5 pixel
    gr.drawArc(5,5,150,150,0,360);  // (x,y,w,h,startDegree, endDegree);
  }

  // repaint the image and delay for a little while
  private static void repaintAndDelay(BufferedImage image)
  {
    _imageLabel.setIcon(new ImageIcon(image));
    _imageLabel.repaint();
    try { Thread.sleep(1); } catch (Exception ignore) {}
  }

  // implements the flood fill algorithm
  public static void floodFill(BufferedImage image, int x,int y, int fillColor)
  {
    java.util.ArrayList<Point> examList=new java.util.ArrayList<Point>();

    int initialColor=image.getRGB(x,y);
    examList.add(new Point(x,y));

    while (examList.size()>0)
    {
      Point p = examList.remove(0);  // get and remove the first point in the list
      if (image.getRGB(p.x,p.y)==initialColor) 
      {
        x = p.x;  y = p.y;
        image.setRGB(x, y, fillColor);  // fill current pixel

        examList.add(new Point(x-1,y));        // check west neighbor
        examList.add(new Point(x+1,y));        // check east neighbor
        examList.add(new Point(x,y-1));        // check north neighbor
        examList.add(new Point(x,y+1));        // check south neighbor

        repaintAndDelay(image);    // this line can be removed
      }
    }

  }

  public static int packRgb(int r,int g,int b)
  {
    return (r*256+g)*256+b;
  }

  static JLabel _imageLabel;
  public static void main(String[] args) throws Exception
  {
    // create an 200x200 RGB image
    BufferedImage image=new BufferedImage(200,200,BufferedImage.TYPE_INT_RGB);

    // fill the image with green color
    fillImage(image,0,255,0);

    // draw a red circle with 5 pixel pen width
    drawCircle(image);

    JLabel imageLabel=new JLabel();
    _imageLabel = imageLabel;  // make it global
    imageLabel.setIcon(new ImageIcon(image));
    imageLabel.setText("Filling the circle with yellow color ...");

    javax.swing.JFrame window=new javax.swing.JFrame();
    window.setTitle("Macteki flood filler");
    window.setDefaultCloseOperation(javax.swing.JFrame.EXIT_ON_CLOSE);

    window.add(imageLabel);

    window.pack();
    window.setVisible(true);

    // fill the circle with yellow color
    int yellow = packRgb(255,255,0);
    int x=50, y=50;  // make sure (x,y) is within the circle
    floodFill(image,x,y, yellow); 

    imageLabel.setIcon(new ImageIcon(image));
    imageLabel.setText("Completed !");

  }
}

Thanks for reading. Comments are welcome.