Java 使用堆栈进行洪水填充
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2783204/
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 using a stack
提问by dafero
I am using the recursive Flood fill algorithm in Java to fill some areas of a image. With very small images it works fine, but when de image becomes larger the JVM gives me a Stack Over Flow Error.
我在 Java 中使用递归 Flood 填充算法来填充图像的某些区域。对于非常小的图像，它工作正常，但是当图像变大时，JVM 会给我一个堆栈溢出错误。
That's the reason why I have to reimplement the method using a Flood Fill with my own stack. (I read that's the best way to do it in these kind of cases)
这就是为什么我必须使用我自己的堆栈使用 Flood Fill 重新实现该方法的原因。（我读到这是在这种情况下最好的方法）
Can anyone explain me how to code it? (if you don't have the code at hand, with the pseudo-code of the algorithm will be fine)
谁能解释我如何编码？（如果你手头没有代码，用算法的伪代码就可以了）
I've read a lot in the Internet but I haven't understood it very well.
我在互联网上阅读了很多，但我并没有很好地理解它。
EDIT: I added my recursive code
编辑：我添加了我的递归代码
public void floodFill(int x, int y, Color targetColor,Color replacementColor) {
if (img.getRGB(x, y) != targetColor.getRGB()) return;
img.setRGB(x, y, replacementColor.getRGB());
floodFill(x - 1, y, targetColor, replacementColor);
floodFill(x + 1, y, targetColor, replacementColor);
floodFill(x, y - 1, targetColor, replacementColor);
floodFill(x, y + 1, targetColor, replacementColor);
return;
}
Thanks!
谢谢！
采纳答案by Gant
You can use Queue to remove recursion from floodfill algorithm. Here are some basic ideas:
您可以使用 Queue 从洪水填充算法中删除递归。这里有一些基本的想法：
- Have a way to mark visited points
- At the beginning, queue the start point.
- While the queue is not empty, continue dequeuing its element. And with each element
- Fill its color and mark just-dequeued point as visited
- Enqueue unvisited adjacent points that has the same color
- 有办法标记访问点
- 在开始时，将起点排队。
- 当队列不为空时，继续使其元素出列。和每个元素
- 填充其颜色并将刚刚出队的点标记为已访问
- 将具有相同颜色的未访问的相邻点排入队列
The below is my Java code to solve similar but different problem of blob detection. I hope you can get some ideas from this and can adapt it the the problem. The code is not well-factored though.
下面是我的 Java 代码，用于解决类似但不同的blob 检测问题。我希望你能从中得到一些想法，并能适应它的问题。虽然代码没有很好地分解。
package blobdetector;
import java.awt.Point;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import javax.imageio.ImageIO;
import javax.management.Query;
public class Main {
public Main() {
}
public static boolean isBlack(BufferedImage image, int posX, int posY) {
int color = image.getRGB(posX, posY);
int brightness = (color & 0xFF) + ((color >> 2) & 0xFF)
+ ((color >> 4) & 0xFF);
brightness /= 3;
return brightness < 128;
}
public static void main(String[] args) {
if (args.length != 1) {
System.err.println("ERROR: Pass filename as argument.");
return;
}
String filename = args[0];
// String filename =
// "C:\Users\Natthawut\Desktop\blob.jpg";
try {
BufferedImage bimg = ImageIO.read(new File(filename));
boolean[][] painted = new boolean[bimg.getHeight()][bimg.getWidth()];
for (int i = 0; i < bimg.getHeight(); i++) {
for (int j = 0; j < bimg.getWidth(); j++) {
if (isBlack(bimg, j, i) && !painted[i][j]) {
Queue<Point> queue = new LinkedList<Point>();
queue.add(new Point(j, i));
int pixelCount = 0;
while (!queue.isEmpty()) {
Point p = queue.remove();
if ((p.x >= 0)
&& (p.x < bimg.getWidth() && (p.y >= 0) && (p.y < bimg
.getHeight()))) {
if (!painted[p.y][p.x]
&& isBlack(bimg, p.x, p.y)) {
painted[p.y][p.x] = true;
pixelCount++;
queue.add(new Point(p.x + 1, p.y));
queue.add(new Point(p.x - 1, p.y));
queue.add(new Point(p.x, p.y + 1));
queue.add(new Point(p.x, p.y - 1));
}
}
}
System.out.println("Blob detected : " + pixelCount
+ " pixels");
}
}
}
} catch (IOException ex) {
ex.printStackTrace();
}
}
}
Test input:
测试输入：
回答by Puppy
You should return the last floodFill statement, turning it into a tail call. This will save you stack space.
您应该返回最后一个 floodFill 语句，将其转换为尾调用。这将节省您的堆栈空间。
回答by RolfS
An important point in flood fill is if you are processing points depth first or breadth first. Depth first is the original solution you were looking at using a stack, breadth first are algorithms shown below using a queue to store point. The difference is substantial when filling in big convex spaces. A breadth first method stores on a perfectly convex area roughly the circle edge (or fill edge). If you use a depth first method you may in worst case store every pixel in the conxex area, that means that in worst case a 1000x1000 image flood filled may require 1000000 of stack frames.
洪水填充的一个重要点是您是先处理点深度还是先处理点。深度优先是您使用堆栈查看的原始解决方案，广度优先是下面显示的使用队列存储点的算法。填充大凸空间时差异很大。广度优先方法将圆边缘（或填充边缘）大致存储在完美凸出的区域上。如果您使用深度优先方法，在最坏的情况下，您可能会将每个像素存储在凸面区域中，这意味着在最坏的情况下，1000x1000 图像洪水填充可能需要 1000000 个堆栈帧。
回答by fdsfdsfdsfds
here is my implementation base on infos from this page and others gathered on the web (tested and working)
这是我基于此页面和网络上收集的其他信息（经过测试和工作）的信息的实施
have fun ;-)
玩得开心 ;-）
public static void floodFillImage(BufferedImage image,int x, int y, Color color)
{
int srcColor = image.getRGB(x, y);
boolean[][] hits = new boolean[image.getHeight()][image.getWidth()];
Queue<Point> queue = new LinkedList<Point>();
queue.add(new Point(x, y));
while (!queue.isEmpty())
{
Point p = queue.remove();
if(floodFillImageDo(image,hits,p.x,p.y, srcColor, color.getRGB()))
{
queue.add(new Point(p.x,p.y - 1));
queue.add(new Point(p.x,p.y + 1));
queue.add(new Point(p.x - 1,p.y));
queue.add(new Point(p.x + 1,p.y));
}
}
}
private static boolean floodFillImageDo(BufferedImage image, boolean[][] hits,int x, int y, int srcColor, int tgtColor)
{
if (y < 0) return false;
if (x < 0) return false;
if (y > image.getHeight()-1) return false;
if (x > image.getWidth()-1) return false;
if (hits[y][x]) return false;
if (image.getRGB(x, y)!=srcColor)
return false;
// valid, paint it
image.setRGB(x, y, tgtColor);
hits[y][x] = true;
return true;
}
