C# 洪水填充算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/367226/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Flood Fill Algorithms
提问by FlySwat
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
关卡编辑器 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!
谢谢！
回答by Steven A. Lowe
回答by strager
Wikpedia provides some pseudocode examples of different flood fill techniques on their Flood fillarticle. Which technique you choose depends on the application.
维基百科在其泛洪填充文章中提供了一些不同泛洪填充技术的伪代码示例。您选择哪种技术取决于应用程序。
Remember that flood filling can easily be threaded (similar to how quicksort can be).
请记住，洪水填充可以轻松地进行线程化（类似于快速排序的方式）。
回答by AAA
In all fairness it should be quite simple. Since you have the basic tile structure anyway the algorithm would be fairly simple:
平心而论，这应该很简单。由于您拥有基本的 tile 结构，因此算法将相当简单：
Select Tile To Fill:
Fill Till
Check neighbouring Tiles - If Empty Then Fill
Repeat, for all filled tiles.
Disclaimer: The above is a very basic description. There are many references on the web which explain it a lot better than I can.
免责声明：以上是一个非常基本的描述。网上有很多参考资料，比我能解释的要好得多。
回答by Johannes Schaub - litb
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:
根据我们是做 8-邻居还是 4-邻居，我们检查所有 8 个邻居像素，或者只检查某个像素的左/右或上/下像素。这是代码（使用 ImageJ。我删除了一些不相关的代码）。我希望它是有道理的，它是 Java。只需提出问题：
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();
}
}
回答by Norman Ramsey
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.
今年秋天早些时候，我对 10 兆像素的扫描图像进行了一些洪水填充。（问题是从复印机上扫描的书页中去除黑边。）在这种情况下，只有两种颜色，所以我基本上把这个问题当作无向图中的搜索，每个像素都连接到它的邻居四个罗盘方向。我维护了一个单独的位图来跟踪哪些像素被访问过。
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.
同样，这些发现仅适用于具有多个百万像素的网格。在像您的问题中所示的漂亮的小网格上，任何简单的算法都应该有效。
回答by Geograph
Simple function without check the color tolerance
简单的功能，无需检查色差
Using:
使用：
var img = Image.FromFile("test.png");
img = img.FloodFill(new Point(0, 0), Color.Red);
img.Save("testcomplete.png", ImageFormat.Png);
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 (a.X < img.Width && a.X > -1 && a.Y < img.Height && a.Y > -1)
{
if (((Bitmap)img).GetPixel(a.X, a.Y) == targetColor)
{
((Bitmap)img).SetPixel(a.X, a.Y, color);
pixels.Push(new Point(a.X - 1, a.Y));
pixels.Push(new Point(a.X + 1, a.Y));
pixels.Push(new Point(a.X, a.Y - 1));
pixels.Push(new Point(a.X, a.Y + 1));
}
}
}
return img;
}
回答by Ivan P.
Here is example how to use GDI+ routines in C# program.
下面是如何在 C# 程序中使用 GDI+ 例程的示例。
( https://www.pinvoke.net/default.aspx/gdi32.extfloodfill)
( 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 are calling this in OnPaint event handler, you may use e.Graphics. Worked for me quite well.
Graphics vGraphics = Graphics.FromHwnd(Handle);如果您在 OnPaint 事件处理程序中调用它，而不是使用，则可以使用e.Graphics. 为我工作得很好。
Sometimes its better not to reinvent algorithm and use existing routines, although you may get some problems with this when porting to Mono.
有时最好不要重新发明算法并使用现有例程，尽管在移植到 Mono 时可能会遇到一些问题。
