Flood Fill Algorithms

Question

Its the weekend again, and that means I get to play with my hobby project.

I've gotten tired of creating test levels by hand, so I thought I'd take a break from engine development and work on a level editor:

Level Editor http://gfilter.net/junk/Editor.JPG

I'd like to implement a flood fill algorithm in the editor, which would work just like in a paint program. Does anyone have any pointers on what technique would work good for me here?

The level is just a 2d array, so it could be considered the same as a bitmap really.

Thanks!

Answer 1

The Wikipedia article is pretty good. As long as your grids are small, just about anything will work.

Earlier this fall I did some flood filling on 10 megapixel scanned images. (The problem was to remove black edges from book pages that had been scanned on a photocopier.) In that case there are only two colors so I essentially treated the problem like a search in an undirected graph, with each pixel connected to its neighbors along the four compass directions. I maintained a separate bitmap to keep track of which pixels had been visited.

The main findings were

• Don't try recursive depth-first search. You really want an explicit data structure.

• An auxiliary queue uses much less space than a stack. About forty times less space. In other words, prefer breadth-first search to depth-first search.

Again, these findings apply only to grids with multiple megapixels. On a nice small grid like the one shown in your question, any simple algorithm should work.

Answer 2

We had to program that for school:

1: stuff the start pixel into a queue, note its color. note it as added.
2: begin picking a pixel off the queue. If it's similar to the start pixel:
   2: put all its neighbours into the queue
      for each added pixel, note it's added. if already noted for a pixel, don't 
      add it anymore.
   3: color it with the destination color.
3: nonempty => jump back to 2
4: empty => we are finished

Depending on whether we do 8-neighbour or 4-neighbour, we check all 8 neighbour pixels, or only pixels left/right or above/below a certain pixel. Here is the code (using ImageJ. I removed some code not relevant). I hope it makes sense, it's Java. Just ask away for questions:

public class Uebung1_2 implements PlugInFilter, MouseListener {
    private ImageProcessor ip;
    boolean[] state;
    int[] pixels;
    Queue<Integer> nextPixels;
    int threshould;

    /**
     * adds one pixel to the next-pixel queue only if it's not
     * already added.
     */
    void addNextPixel(int p) {
        if(!state[p]) {
            nextPixels.add(p);
            state[p] = true;
        }
    }

    boolean pixelsSimilar(int color1, int color2) {
        int dr = Math.abs(((color1 >> 16) & 0xff) -
                          ((color2 >> 16) & 0xff));
        int dg = Math.abs(((color1 >>  8) & 0xff) -
                          ((color2 >>  8) & 0xff));
        int db = Math.abs(((color1 >>  0) & 0xff) -
                          ((color2 >>  0) & 0xff));
        return ((double)(dr + dg + db) / 3.0) <= threshould;
    }

    /**
     * actually does the hard work :)
     * @param x the x position from which to start filling
     * @param y the y position from which to start filling
     */
    private void doFill(int x, int y, boolean connect8) {
        // first, add the start pixel
        int width = ip.getWidth(),
            height = ip.getHeight();
        /* for 8bit, we just gonna take the median of rgb */
        Color colorC = ij.gui.Toolbar.getForegroundColor();
        int color = colorC.getRGB();
        int firstPixel = ip.get(x, y);

        // go on with the mainloop
        addNextPixel(y * width + x);
        while(!nextPixels.isEmpty()) {
            int nextPixel = nextPixels.remove();
            int pixel = pixels[nextPixel];
            if(pixelsSimilar(pixel, firstPixel)) {
                // yay it matches. put the neighbours.
                int xN = nextPixel % width,
                    yN = nextPixel / width;
                /* the three pixels above */
                if(yN - 1 >= 0) {
                    if(connect8) {
                        if(xN + 1 < width) { 
                            addNextPixel(nextPixel - width + 1);
                        }
                        if(xN - 1 >= 0) {
                            addNextPixel(nextPixel - width - 1);
                        }
                    }
                    addNextPixel(nextPixel - width);
                }

                /* pixels left and right from the current one */
                if(xN > 0) {
                    addNextPixel(nextPixel - 1);
                }
                if(xN + 1 < width) {
                    addNextPixel(nextPixel + 1);
                }

                /* three pixels below */
                if(yN + 1 < height) {
                    if(connect8) {
                        if(xN + 1 < width) { 
                            addNextPixel(nextPixel + width + 1);
                        }
                        if(xN - 1 >= 0) {
                            addNextPixel(nextPixel + width - 1);
                        }
                    }
                    addNextPixel(nextPixel + width);
                }

                /* color it finally */
                pixels[nextPixel] = color;
            }
        }
    }

    @Override
    public void run(ImageProcessor ip) {
        ij.WindowManager.getCurrentImage().getCanvas().addMouseListener(this);
        this.ip = ip;
        this.pixels = (int[])ip.getPixels();
        this.state = new boolean[ip.getPixelCount()];
        this.nextPixels = new LinkedList<Integer>();
    }

    @Override
    public int setup(String arg0, ImagePlus arg1) {
        return DOES_RGB;
    }

    @Override
    public void mouseClicked(MouseEvent e) {
        ij.WindowManager.getCurrentWindow().getCanvas().removeMouseListener(this);
        ij.gui.GenericDialog g = new GenericDialog("Please enter parameters");
        g.addChoice("connection", new String[]{"4-connect", "8-connect"}, "8-connect");
        g.addNumericField("Threshould (0..255)", 0.0, 3);
        g.showDialog();

        boolean connect8 = g.getNextChoice().equals("8-connect");
        threshould = (int) g.getNextNumber();
        doFill(e.getX(), e.getY(), connect8);
        ij.WindowManager.getCurrentImage().draw();
    }
}