java - 如何避免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));

        }


    }

请原谅使用继续。我想保持原始解决方案的结构与此类似。但我建议不要使用它。

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

Class StackItem 只是递归函数所有参数的表示。参数 target 不会更改，因此它不是其中的一部分。每次递归调用都等于将新参数推送到我们的 Stack 结构中。每次调用“递归”函数都等于从顶部弹出参数并使用该参数执行逻辑。