如何避免java.lang.StackOverflowError

Question

我在我的绘画应用程序中实现了一个泛洪填充算法。我的代码在那个算法上没有问题。

当我测试该程序时，我注意到泛洪填充适用于小的封闭区域，但当泛洪填充应用于大的区域时，我得到java.lang.StackOverflowError，并且在重新绘制后大的区域被填充了一半。我知道Java对递归方法的调用堆栈有限，我不确定如何优化我的代码来处理这个问题，是否需要调整我的缓冲区大小？

代码：

import java.awt.*;
import java.awt.event.*;
import java.awt.image.BufferedImage;
import javax.swing.*;
public class MinimumVerifiableExample extends JFrame {
private static final long serialVersionUID = 1L;
private final int WIDTH = 800;
private final int HEIGHT = 600;
private PaintPanel panel;
private JButton button;
private MinimumVerifiableExample() {
super("Paint App Plus");
panel = new PaintPanel();
button = new JButton("Fill with mouse click");
button.addActionListener(e -> {
panel.setFloodFill(Color.RED);
});
setSize(WIDTH, HEIGHT);
setLocationRelativeTo(null);
setLayout(new BorderLayout());
add(panel, BorderLayout.CENTER);
add(button, BorderLayout.SOUTH);
setResizable(false);
}
public static void main(String[] args) {
EventQueue.invokeLater(() -> {
MinimumVerifiableExample frame = new MinimumVerifiableExample();
frame.setVisible(true);
});
}
private class PaintPanel extends JComponent implements MouseListener, MouseMotionListener {
private static final long serialVersionUID = 1L;
private final int canvasWidth = 784;
private final int canvasHeight = 526;
private BufferedImage canvas;
private boolean floodFill;
private Color fillColour;
private boolean painting;
private int prevX;
private int prevY;
private int curX;
private int curY;
private PaintPanel() {
canvas = new BufferedImage(canvasWidth, canvasHeight, BufferedImage.TYPE_INT_RGB);
floodFill = false;
fillColour = null;
painting = false;
Graphics2D paintBrush = canvas.createGraphics();
paintBrush.setColor(Color.WHITE);
paintBrush.fillRect(0, 0, canvas.getWidth(), canvas.getHeight());
paintBrush.dispose();
addMouseListener(this);
addMouseMotionListener(this);
}
protected void paintComponent(Graphics g) {
super.paintComponent(g);
g.setColor(Color.WHITE);
g.fillRect(0, 0, canvas.getWidth(), canvas.getHeight());
g.drawImage(canvas, getInsets().left, getInsets().top, canvasWidth, canvasHeight, this);
}
public void setFloodFill(Color fillColour) {
floodFill = true;
this.fillColour = fillColour;
}
private void floodFill(int x, int y, Color target, Color previous) {
if (x > canvas.getWidth() || x < 1 || y > canvas.getHeight() || y < 1)
return;
if (canvas.getRGB(x, y) != previous.getRGB())
return;
previous = new Color(canvas.getRGB(x, y));
canvas.setRGB(x, y, target.getRGB());
floodFill(x + 1, y, target, previous);
floodFill(x, y + 1, target, previous);
floodFill(x - 1, y, target, previous);
floodFill(x, y - 1, target, previous);
}
private void updateBoard() {
Graphics2D paintBrush = canvas.createGraphics();
paintBrush.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
paintBrush.setPaint(Color.BLACK);
paintBrush.setStroke(new BasicStroke(10, BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND));
paintBrush.drawLine(prevX, prevY, curX, curY);
paintBrush.dispose();
}
public void mousePressed(MouseEvent e) {
if (floodFill) {
floodFill(e.getX(), e.getY(), fillColour, new Color(canvas.getRGB(e.getX(), e.getY())));
repaint();
floodFill = false;
return;
}
if (painting) return;
prevX = e.getX();
prevY = e.getY();
painting = true;
}
public void mouseReleased(MouseEvent e) {
if (!painting) return;
curX = e.getX();
curY = e.getY();
painting = false;
}
public void mouseDragged(MouseEvent e) {
curX = e.getX();
curY = e.getY();
if (!painting) return;
updateBoard();
repaint();
prevX = curX;
prevY = curY;
}
public void mouseClicked(MouseEvent e) {}
public void mouseEntered(MouseEvent e) {}
public void mouseExited(MouseEvent e) {}
public void mouseMoved(MouseEvent e) {}
}
}

Answer 1

解决方案：

private class StackItem {
private final int x;
private final int y;
private final Color previous;
public StackItem(int x, int y, Color previous) {
this.x = x;
this.y = y;
this.previous = previous;
}
}
private void floodFill(final int initialX, final int initialY, final Color target, final Color previous) {
Stack<StackItem> stack = new Stack<>();
stack.push(new StackItem(initialX, initialY, previous));
while (!stack.isEmpty()) {
StackItem stackItem = stack.pop();
if (stackItem.x > canvas.getWidth() || stackItem.x < 1 || stackItem.y > canvas.getHeight() || stackItem.y < 1)
continue;
if (canvas.getRGB(stackItem.x, stackItem.y) != stackItem.previous.getRGB())
continue;
Color previousColor = new Color(canvas.getRGB(stackItem.x, stackItem.y));
canvas.setRGB(stackItem.x, stackItem.y, target.getRGB());
stack.push(new StackItem(stackItem.x + 1, stackItem.y, previousColor));
stack.push(new StackItem(stackItem.x, stackItem.y + 1, previousColor));
stack.push(new StackItem(stackItem.x - 1, stackItem.y, previousColor));
stack.push(new StackItem(stackItem.x, stackItem.y - 1, previousColor));
}

}

请原谅使用continue。我想保持原始解决方案的结构与此类似。不过我建议克制使用它。

正如您所看到的，这是一种如何将递归转换为循环的直接方法。我们使用的不是JVM堆栈(其大小有限(，而是一个使用JVM堆的集合。

类StackItem只是递归函数的所有参数的表示。参数target不会改变，所以它不是它的一部分。每个递归调用都等于向我们的Stack结构推送新的参数。每次调用"递归"函数都等于从顶部弹出参数并使用该参数执行逻辑。

Answer 2

最简单的解决方案是仔细检查堆栈跟踪并检测行号的重复模式。这些行号表示被递归调用的代码。一旦检测到这些行，就必须仔细检查代码，并理解为什么递归永远不会终止。