Click here to Skip to main content
Click here to Skip to main content
Alternative Article

Queue-Linear Flood Fill: A Fast Flood Fill Algorithm

, 7 May 2012
Rate this:
Please Sign up or sign in to vote.
This is an alternative for "Queue-Linear Flood Fill: A Fast Flood Fill Algorithm"

Introduction

The original code and Java port were really great. I just made some changes to get this to work with Android.

Using the code

Given that even this algorithm can take some time, it's best to put this inside of a thread. I created a little class for that which looks like this:

public class FloodFillThread extends Thread 
{
    ProgressDialog mProgressDialog;
    Bitmap            mBitmap;
    int               mTargetColor;
    int            mNewColor;
    Point           mPoint;
    Runnable       mCallback;
    
    public FloodFillThread(ProgressDialog pd, Runnable callback, 
           Bitmap bitmap, Point pt, int targetColor, int newColor) 
    {
        mBitmap          = bitmap;
        mPoint           = pt;
        mTargetColor     = targetColor;
        mNewColor          = newColor;
        mProgressDialog = pd;
        mCallback       = callback;
    }

    @Override
    public void run() 
    {         
        QueueLinearFloodFiller filler = 
           new QueueLinearFloodFiller(mBitmap, mTargetColor, mNewColor);
        
        filler.setTolerance(10);
        
        filler.floodFill(mPoint.x, mPoint.y);
        
        handler.sendEmptyMessage(0);
    }

    private Handler handler = new Handler() 
    {
        @Override
        public void handleMessage(Message msg) 
        {
            mProgressDialog.dismiss();
            mCallback.run();
        }
    };
}

Here is the code for the port:

//package com.standardandroid.drawer;

//Original algorithm by J. Dunlap queuelinearfloodfill.aspx
//Java port by Owen Kaluza
//Android port by Darrin Smith (Standard Android)

//import java.util.Queue;
//import java.util.LinkedList;

//import android.graphics.Bitmap;
//import android.graphics.Color;

//public class QueueLinearFloodFiller
{
	protected Bitmap             	image      = null;
	protected int[]              	tolerance  = new int[] {0,0,0};
	protected int                	width      = 0;
	protected int                	height     = 0;
	protected int[]              	pixels     = null;
	protected int                 	fillColor  = 0;
	protected int[]             	startColor = new int[] {0,0,0};
	protected boolean[]         	pixelsChecked;
	protected Queue<FloodFillRange> ranges;

    //Construct using an image and a copy will be made to fill into,
    //Construct with BufferedImage and flood fill will write directly to provided BufferedImage
	public QueueLinearFloodFiller(Bitmap img)
    {
    	copyImage(img);
    }

	public QueueLinearFloodFiller(Bitmap img, int targetColor, int newColor)
    {
    	useImage(img);
        
    	setFillColor(newColor);
    	setTargetColor(targetColor);
    }

	public void setTargetColor(int targetColor)
    {
    	startColor[0] = Color.red(targetColor);
    	startColor[1] = Color.green(targetColor);
    	startColor[2] = Color.blue(targetColor);
    }

	public int getFillColor()
    {
    	return fillColor;
    }
    
	public void setFillColor(int value)
    {
    	fillColor = value;
    }
    
	public int[] getTolerance()
    {
    	return tolerance;
    }
    
	public void setTolerance(int[] value)
    {
    	tolerance = value;
    }
    
	public void setTolerance(int value)
    {
    	tolerance = new int[] {value, value, value};
    }
    
	public Bitmap getImage()
    {
    	return image;
    }

	public void copyImage(Bitmap img)
    {
        //Copy data from provided Image to a BufferedImage to write flood fill to, use getImage to retrieve
        //cache data in member variables to decrease overhead of property calls
    	width  = img.getWidth();
    	height = img.getHeight();
        
    	image  = Bitmap.createBitmap(width, height, Bitmap.Config.ARGB_8888);
    	image  = Utilities.copyBitmap(img);
        
    	pixels = new int[width * height];
        
    	image.getPixels(pixels, 0, width, 1, 1, width - 1, height - 1);
    }

	public void useImage(Bitmap img)
    {
        //Use a pre-existing provided BufferedImage and write directly to it
        //cache data in member variables to decrease overhead of property calls
    	width  = img.getWidth();
    	height = img.getHeight();
    	image  = img;

    	pixels = new int[width * height];

    	image.getPixels(pixels, 0, width, 1, 1, width - 1, height - 1);
    }
    
	protected void prepare()
    {
        //Called before starting flood-fill
    	pixelsChecked = new boolean[pixels.length];
    	ranges        = new LinkedList<FloodFillRange>();
    }

     Fills the specified point on the bitmap with the currently selected fill color.
     int x, int y: The starting coords for the fill
	public void floodFill(int x, int y)
    {
        //Setup 
    	prepare();

    	if(startColor[0] == 0)
        {
            ***Get starting color.
        	int startPixel = pixels[(width * y) + x];
        	startColor[0]  = (startPixel >> 16) & 0xff;
        	startColor[1]  = (startPixel >> 8) & 0xff;
        	startColor[2]  = startPixel & 0xff;
        }
        
        ***Do first call to floodfill.
    	LinearFill(x,  y);

        ***Call floodfill routine while floodfill ranges still exist on the queue
    	FloodFillRange range;
        
    	while (ranges.size() > 0)
        {
            **Get Next Range Off the Queue
        	range = ranges.remove();

            **Check Above and Below Each Pixel in the Floodfill Range
        	int downPxIdx = (width * (range.Y + 1)) + range.startX;
        	int upPxIdx   = (width * (range.Y - 1)) + range.startX;
        	int upY       = range.Y - 1;//so we can pass the y coord by ref
        	int downY     = range.Y + 1;
            
        	for (int i = range.startX; i <= range.endX; i++)
            {
                *Start Fill Upwards
                //if we're not above the top of the bitmap and the pixel above this one is within the color tolerance
            	if (range.Y > 0 && (!pixelsChecked[upPxIdx]) && CheckPixel(upPxIdx))
                {
                	LinearFill( i,  upY);
                }
                
                *Start Fill Downwards
                //if we're not below the bottom of the bitmap and the pixel below this one is within the color tolerance
            	if (range.Y < (height - 1) && (!pixelsChecked[downPxIdx]) && CheckPixel(downPxIdx))
                {
                	LinearFill( i,  downY);
                }
                
            	downPxIdx++;
            	upPxIdx++;
            }
        }
        
    	image.setPixels(pixels, 0, width, 1, 1, width - 1, height - 1);
    }

     Finds the furthermost left and right boundaries of the fill area
     on a given y coordinate, starting from a given x coordinate, filling as it goes.
     Adds the resulting horizontal range to the queue of floodfill ranges,
     to be processed in the main loop.
    
     int x, int y: The starting coords
	protected void LinearFill(int x, int y)
    {
        ***Find Left Edge of Color Area
    	int lFillLoc = x; //the location to check/fill on the left
    	int pxIdx    = (width * y) + x;
        
    	while (true)
        {
            **fill with the color
        	pixels[pxIdx] = fillColor;
            
            **indicate that this pixel has already been checked and filled
        	pixelsChecked[pxIdx] = true;
            
            **de-increment
        	lFillLoc--;     //de-increment counter
        	pxIdx--;        //de-increment pixel index
            
            **exit loop if we're at edge of bitmap or color area
        	if (lFillLoc < 0 || (pixelsChecked[pxIdx]) || !CheckPixel(pxIdx))
            {
            	break;
            }
        }
        
    	lFillLoc++;

        ***Find Right Edge of Color Area
    	int rFillLoc = x; //the location to check/fill on the left
        
    	pxIdx = (width * y) + x;
        
    	while (true)
        {
            **fill with the color
        	pixels[pxIdx] = fillColor;
            
            **indicate that this pixel has already been checked and filled
        	pixelsChecked[pxIdx] = true;
            
            **increment
        	rFillLoc++;     //increment counter
        	pxIdx++;        //increment pixel index
            
            **exit loop if we're at edge of bitmap or color area
        	if (rFillLoc >= width || pixelsChecked[pxIdx] || !CheckPixel(pxIdx))
            {
            	break;
            }
        }
        
    	rFillLoc--;

        //add range to queue
    	FloodFillRange r = new FloodFillRange(lFillLoc, rFillLoc, y);
        
    	ranges.offer(r);
    }

    //Sees if a pixel is within the color tolerance range.
	protected boolean CheckPixel(int px)
    {
    	int red   = (pixels[px] >>> 16) & 0xff;
    	int green = (pixels[px] >>> 8) & 0xff;
    	int blue  = pixels[px] & 0xff;
        
    	return (red   >= (startColor[0] - tolerance[0]) && red   <= (startColor[0] + tolerance[0]) &&
                green >= (startColor[1] - tolerance[1]) && green <= (startColor[1] + tolerance[1]) &&
                blue  >= (startColor[2] - tolerance[2]) && blue  <= (startColor[2] + tolerance[2]));
    }
  
     Represents a linear range to be filled and branched from.
	protected class FloodFillRange
    {
    	public int startX;
    	public int endX;
    	public int Y;

    	public FloodFillRange(int startX, int endX, int y)
        {
            this.startX = startX;
            this.endX   = endX;
            this.Y      = y;
        }
    }    
}

History 

Added 04/11/2012

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Member 8808706

Unknown
No Biography provided

Comments and Discussions

 
QuestionSource Code Pinmemberarashmobileboy26-Jan-14 4:40 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web01 | 2.8.140721.1 | Last Updated 7 May 2012
Article Copyright 2012 by Member 8808706
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid