洪水填充算法

这是周末，这意味着我可以玩我的爱好项目了 。

我已经厌倦了手工创建测试级别，所以我想我会从引擎开发中rest并在级别编辑器上工作：

关卡编辑http://gfilter.net/junk/Editor.JPG

我想在编辑器中实现泛洪填充算法，就像在绘图程序中一样。 有没有人有任何关于哪种技术对我有用的指针？

级别只是一个2d数组，因此可以认为它与位图相同。

谢谢！

Answer 1

维基百科的文章相当不错。 只要您的网格很小，几乎任何东西都可以工作。

今年秋天早些时候，我在1000万像素扫描图像上做了一些洪水填充。 （问题是要去除在复印机上扫描的书页的黑边。）在这种情况下，只有两种颜色，所以我基本上把问题看作是在无向图中搜索，每个像素连接到它的邻居四个指南针方向。 我维护了一个单独的位图来跟踪访问过的像素 。

主要发现是

• 不要尝试递归深度优先搜索 。 你真的想要一个明确的数据结构。

• 辅助队列使用的空间比堆栈少得多 。 空间减少约四十倍 。 换句话说，更喜欢广度优先搜索到深度优先搜索。

同样， 这些发现仅适用于具有多个百万像素的网格 。 在像你的问题中所示的一个漂亮的小网格上，任何简单的算法都应该有效。

Answer 2

我们必须为学校编程：

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 

根据我们是8邻居还是4邻居，我们检查所有8个邻居像素，或仅检查某个像素左/右或上/下的像素。 这是代码（使用ImageJ。我删除了一些不相关的代码）。 我希望它有意义，它是Java。 只是提出问题：

 public class Uebung1_2 implements PlugInFilter, MouseListener { private ImageProcessor ip; boolean[] state; int[] pixels; Queue 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(); } @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

一般参考

C＃中的优化算法

Answer 4

Wikpedia在其Flood填充文章中提供了一些不同洪水填充技术的伪代码示例。 您选择哪种技术取决于应用程序。

请记住，洪水填充可以很容易地进行线程化（类似于快速排序）。

Answer 5

平心而论，它应该很简单。 既然你有基本的瓦片结构，那么算法会非常简单：

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

免责声明：以上是一个非常基本的描述。 网上有很多参考资料，它比我能解释得更好。

Answer 6

function简单，无需检查颜色容差

使用：

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

主function：

  public static Image FloodFill(this Image img, Point pt, Color color) { Stack pixels = new Stack(); 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; }