I implemented a flood fill algorithm to my paint application. There were no problems for my code on that algorithm.
When I test the program, I noticed that the flood fill works fine for small enclosed areas but when the flood fill applied to large areas, I got java.lang.StackOverflowError and the large area was half filled after repainting. I know that Java have limited call stack for recursive methods, I'm not sure how can I optimize my code to cope with this problem, should resizing my bufferedimage necessary?
Code:
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) {}
}
}
Solution:
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));
}
}
Please, pardon the use of continue. I wanted to keep the structure of original solution similar to this one. I recommend though to restrain from using it.
As you can see, this is a direct approach on how to translate recursion into a loop. Instead of using JVM stack, which has limited size, we are using a collection, which uses JVMs heap.
Class StackItem is simply a representation of all arguments of a recursive function. Argument target does not change, so it is not part of it. Every recursive call is a equal to pushing new argument to our Stack structure. Every invocation of a "recursive" function is equal to poping the argument from top and executing logic using this argument.