Flood filling algorithms

Question

His weekend is back, and that means that I can play with my hobby project .

I was tired of creating test levels manually, so I thought that I would move on from developing the engine and working on the level editor:

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

I would like to implement a fill filling algorithm in an editor that will work just like in a drawing program. Does anyone have any guidance on which technique will work for me here?

A level is just a 2d array, so it can be considered the same as a bitmap.

Thanks!

Answer 1

The Wikipedia article is pretty good. As long as your grids are small, pretty much everything will work.

Earlier this fall, I filled in 10 megapixel scanned images. (The problem was to remove the black edges from the pages of the book that were scanned on the copier.) In this case, there are only two colors, so I essentially considered the problem as a search on an undirected graph, with each pixel connected to its neighbors along Four compass directions. I maintained a separate bitmap to keep track of which pixels were visited .

The main results were

• Do not attempt to perform a recursive depth search . You really need an explicit data structure.

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

Again, these results apply only to mega-pixel grids . On a nice small grid like the one shown in your question, any simple algorithm should work.

Answer 2

We had to program this for the 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 similar to the start pixel: 2: put all its neighbours into the queue for each added pixel, note it 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 make an 8-neighboring or 4-neighboring, we check all 8 neighboring pixels or only pixels left / right or above / below a certain pixel. Here is the code (using ImageJ. I deleted some code that doesn't matter). Hope this makes sense, this is Java. Just ask 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 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(); } } 

Answer 3

general link

optimized algorithm in C #

Answer 4

Wikpedia provides some examples of pseudo-code of various methods of flooding their Flood fill . Which method you choose depends on the application.

Remember that filling the filler can be easily threaded (similar to how quicksort can be).

Answer 5

In all fairness, this should be pretty simple. Since you have a basic tile structure, the algorithm would be pretty simple:

 Select Tile To Fill: Fill Till Check neighbouring Tiles - If Empty Then Fill Repeat, for all filled tiles. 

Disclaimer: The foregoing is a very simple description. There are many links on the Internet that explain this much better than I can.

Answer 6

Simple function without checking color fastness

Through:

 var img = Image.FromFile("test.png"); img = img.FloodFill(new Point(0, 0), Color.Red); img.Save("testcomplete.png", ImageFormat.Png); 

The main function:

  public static Image FloodFill(this Image img, Point pt, Color color) { Stack<Point> pixels = new Stack<Point>(); var targetColor = ((Bitmap)img).GetPixel(pt.X, pt.Y); pixels.Push(pt); while (pixels.Count > 0) { Point a = pixels.Pop(); if (aX < img.Width && aX > -1 && aY < img.Height && aY > -1) { if (((Bitmap)img).GetPixel(aX, aY) == targetColor) { ((Bitmap)img).SetPixel(aX, aY, color); pixels.Push(new Point(aX - 1, aY)); pixels.Push(new Point(aX + 1, aY)); pixels.Push(new Point(aX, aY - 1)); pixels.Push(new Point(aX, aY + 1)); } } } return img; } 

Answer 7

Here is an example of how to use the GDI + routines in a C # program.

( https://www.pinvoke.net/default.aspx/gdi32.extfloodfill )

 using System.Runtime.InteropServices; //insert by Zswang(wjhu111#21cn.com) at 2007-05-22 [DllImport("gdi32.dll")] public static extern IntPtr SelectObject(IntPtr hdc, IntPtr hgdiobj); [DllImport("gdi32.dll")] public static extern IntPtr CreateSolidBrush(int crColor); [DllImport("gdi32.dll")] public static extern bool ExtFloodFill(IntPtr hdc, int nXStart, int nYStart, int crColor, uint fuFillType); [DllImport("gdi32.dll")] public static extern bool DeleteObject(IntPtr hObject); [DllImport("gdi32.dll")] public static extern int GetPixel(IntPtr hdc, int x, int y); public static uint FLOODFILLBORDER = 0; public static uint FLOODFILLSURFACE = 1; private void button1_Click(object sender, EventArgs e) { Graphics vGraphics = Graphics.FromHwnd(Handle); vGraphics.DrawRectangle(Pens.Blue, new Rectangle(0, 0, 300, 300)); vGraphics.DrawRectangle(Pens.Blue, new Rectangle(50, 70, 300, 300)); IntPtr vDC = vGraphics.GetHdc(); IntPtr vBrush = CreateSolidBrush(ColorTranslator.ToWin32(Color.Red)); IntPtr vPreviouseBrush = SelectObject(vDC, vBrush); ExtFloodFill(vDC, 10, 10, GetPixel(vDC, 10, 10), FLOODFILLSURFACE); SelectObject(vDC, vPreviouseBrush); DeleteObject(vBrush); vGraphics.ReleaseHdc(vDC); } 

Instead of using Graphics vGraphics = Graphics.FromHwnd(Handle); if you call this in the OnPaint event handler, you can use e.Graphics . It worked pretty well for me.

Sometimes it’s better not to invent an algorithm and use existing routines, although there might be some problems with porting to Mono.