How to create a bucket fill in Java?

I am trying to create a paint like program and I am currently implementing a bucket fill tool. I am storing all the points that have been drawn and using Graphics2D's drawLine to draw the actual lines, so I do not want to store all the points for the bucket fill (so I do not want to do flood fill).

For the bucket fill, so far I have used a BufferedImage to fill in the points that are not in my list, but are still being drawn.

One thing that I thought to do was to just store the outermost points that and than I could use Graphics2D's fillPolygon using those points. The only problem is that I'm not sure how to find those points.

I'm stuck here, so does anyone have any ideas?

Solution

There's probably a heap of different ways of achieving this, personally, I'd make use of 2D Graphics Shape API...

enter image description here

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.EventQueue;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.RenderingHints;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.awt.geom.Path2D;
import java.util.ArrayList;
import java.util.List;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.UIManager;
import javax.swing.UnsupportedLookAndFeelException;

public class BucketFill {

    public static void main(String[] args) {
        new BucketFill();
    }

    public BucketFill() {
        EventQueue.invokeLater(new Runnable() {
            @Override
            public void run() {
                try {
                    UIManager.setLookAndFeel(UIManager.getSystemLookAndFeelClassName());
                } catch (ClassNotFoundException | InstantiationException | IllegalAccessException | UnsupportedLookAndFeelException ex) {
                }

                JFrame frame = new JFrame("Testing");
                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                frame.setLayout(new BorderLayout());
                frame.add(new TestPane());
                frame.pack();
                frame.setLocationRelativeTo(null);
                frame.setVisible(true);
            }
        });
    }

    public class TestPane extends JPanel {

        private List<Point> points;

        public TestPane() {
            points = new ArrayList<Point>(25);

            addMouseListener(new MouseAdapter() {
                @Override
                public void mouseClicked(MouseEvent e) {
                    points.add(e.getPoint());
                    repaint();
                }
            });
        }

        @Override
        public Dimension getPreferredSize() {
            return new Dimension(200, 200);
        }

        @Override
        protected void paintComponent(Graphics g) {
            super.paintComponent(g);

            if (points.size() > 0) {

                Graphics2D g2d = (Graphics2D) g.create();
                g2d.setRenderingHint(RenderingHints.KEY_ALPHA_INTERPOLATION, RenderingHints.VALUE_ALPHA_INTERPOLATION_QUALITY);
                g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
                g2d.setRenderingHint(RenderingHints.KEY_COLOR_RENDERING, RenderingHints.VALUE_COLOR_RENDER_QUALITY);
                g2d.setRenderingHint(RenderingHints.KEY_DITHERING, RenderingHints.VALUE_DITHER_ENABLE);
                g2d.setRenderingHint(RenderingHints.KEY_FRACTIONALMETRICS, RenderingHints.VALUE_FRACTIONALMETRICS_ON);
                g2d.setRenderingHint(RenderingHints.KEY_INTERPOLATION, RenderingHints.VALUE_INTERPOLATION_BILINEAR);
                g2d.setRenderingHint(RenderingHints.KEY_RENDERING, RenderingHints.VALUE_RENDER_QUALITY);
                g2d.setRenderingHint(RenderingHints.KEY_STROKE_CONTROL, RenderingHints.VALUE_STROKE_PURE);

                List<Point> proxy = new ArrayList<>(points);

                Path2D.Double path = new Path2D.Double();
                Point p = proxy.remove(0);
                path.moveTo(p.getX(), p.getY());
                while (proxy.size() > 0) {
                    p = proxy.remove(0);
                    path.lineTo(p.getX(), p.getY());
                }

                g2d.setColor(Color.RED);
                g2d.fill(path);
                g2d.setColor(Color.BLACK);
                g2d.draw(path);
                g2d.dispose();

            }
        }
    }
}

Update with fillPolygon

You could replace the Shape implementation with a fillPolygon simply by removing the reference to the shape and using something like the following instead.

List<Point> proxy = new ArrayList<>(points);
int[] xPoints = new int[proxy.size()];
int[] yPoints = new int[proxy.size()];
int nPoints = proxy.size();

int index = 0;
while (proxy.size() > 0) {
    Point p = proxy.remove(0);
    xPoints[index] = p.x;
    yPoints[index] = p.y;
    index++;
}

g2d.setColor(Color.RED);
g2d.fillPolygon(xPoints, yPoints, nPoints);
g2d.setColor(Color.BLACK);
g2d.drawPolygon(xPoints, yPoints, nPoints);

This will generate what's know as a closed polygon (ie, you can see that all the lines join up).

enter image description here

You can achieve using the Shape by calling path.closePath() after the while-loop and before it's painted.

Updated with multiple Polygons

enter image description here

A lot will come down to what you consider a polygon and how you store those values, but you could use an Area and subtract the intersecting polygon's from it...

public class BucketFill {

    public static void main(String[] args) {
        new BucketFill();
    }

    public BucketFill() {
        EventQueue.invokeLater(new Runnable() {
            @Override
            public void run() {
                try {
                    UIManager.setLookAndFeel(UIManager.getSystemLookAndFeelClassName());
                } catch (ClassNotFoundException | InstantiationException | IllegalAccessException | UnsupportedLookAndFeelException ex) {
                }

                JFrame frame = new JFrame("Testing");
                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                frame.setLayout(new BorderLayout());
                frame.add(new TestPane());
                frame.pack();
                frame.setLocationRelativeTo(null);
                frame.setVisible(true);
            }
        });
    }

    public class TestPane extends JPanel {

        private List<List<Point>> points;

        public TestPane() {
            points = new ArrayList<>(25);

            MouseAdapter ma = new MouseAdapter() {
                @Override
                public void mousePressed(MouseEvent e) {
                    List<Point> newShape = new ArrayList<>(25);
                    newShape.add(e.getPoint());
                    points.add(newShape);
                }

                @Override
                public void mouseReleased(MouseEvent e) {
                }

                @Override
                public void mouseDragged(MouseEvent e) {
                    List<Point> newShape = points.get(points.size() - 1);
                    newShape.add(e.getPoint());
                    repaint();
                }
            };

            addMouseListener(ma);
            addMouseMotionListener(ma);
        }

        @Override
        public Dimension getPreferredSize() {
            return new Dimension(200, 200);
        }

        @Override
        protected void paintComponent(Graphics g) {
            super.paintComponent(g);

            if (points.size() > 0) {

                Graphics2D g2d = (Graphics2D) g.create();
                g2d.setRenderingHint(RenderingHints.KEY_ALPHA_INTERPOLATION, RenderingHints.VALUE_ALPHA_INTERPOLATION_QUALITY);
                g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
                g2d.setRenderingHint(RenderingHints.KEY_COLOR_RENDERING, RenderingHints.VALUE_COLOR_RENDER_QUALITY);
                g2d.setRenderingHint(RenderingHints.KEY_DITHERING, RenderingHints.VALUE_DITHER_ENABLE);
                g2d.setRenderingHint(RenderingHints.KEY_FRACTIONALMETRICS, RenderingHints.VALUE_FRACTIONALMETRICS_ON);
                g2d.setRenderingHint(RenderingHints.KEY_INTERPOLATION, RenderingHints.VALUE_INTERPOLATION_BILINEAR);
                g2d.setRenderingHint(RenderingHints.KEY_RENDERING, RenderingHints.VALUE_RENDER_QUALITY);
                g2d.setRenderingHint(RenderingHints.KEY_STROKE_CONTROL, RenderingHints.VALUE_STROKE_PURE);

                g2d.setColor(Color.BLUE);
                List<Shape> shapes = new ArrayList<>(25);
                for (List<Point> subPoints : points) {

                    if (subPoints.size() > 0) {

                        List<Point> proxy = new ArrayList<>(subPoints);

                        Path2D path = new Path2D.Float();
                        Point startPoint = proxy.remove(0);
                        path.moveTo(startPoint.x, startPoint.y);
                        for (Point p : proxy) {
                            path.lineTo(p.x, p.y);
                        }
                        path.closePath();
                        shapes.add(path);
                        path = null;

                    }

                }

                for (Shape master : shapes) {
                    Area area = new Area(master);
                    for (Shape inner : shapes) {
                        if (inner != master) {
                            area.subtract(new Area(inner));
                        }
                    }
                    g2d.setColor(Color.RED);
                    g2d.fill(area);
                    g2d.setColor(Color.BLACK);
                    g2d.draw(area);
                }

                g2d.dispose();

            }
        }
    }
}