Как избежать java.lang.StackOverflowError? - PullRequest
Новая
       40

Как избежать java.lang.StackOverflowError?

0 голосов
/ 17 ноября 2018

Я реализовал алгоритм заливки в моем приложении для рисования. Для моего кода не было проблем с этим алгоритмом.

Когда я тестировал программу, я заметил, что заливка заливки отлично работает для небольших закрытых областей, но когда заливка заливки была применена к большим областям, я получил 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) {}
    }
}

Ответы [ 2 ]

0 голосов
/ 17 ноября 2018

Самое простое решение - тщательно проверить трассировку стека и обнаружить повторяющуюся последовательность номеров строк.Эти номера строк указывают на рекурсивно вызываемый код.Как только вы обнаружите эти строки, вы должны тщательно проверить свой код и понять, почему рекурсия никогда не завершается.

0 голосов
/ 17 ноября 2018

Решение: 

    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. Каждый вызов «рекурсивной» функции равен извлечению аргумента из верха и выполнению логики с использованием этого аргумента.

...