How to start the bucket-fill algorithm

Question

I have a task, but I don't know how to start. If someone knows, please send me links to some posts. I have a minimal Java class, where I need to update the "fill" method so that it works according to the description below:

Pretend you are working in MS Paint, or a similar graphics application. Your job is to implement the bucket-fill tool. More specifically, given a two-dimensional grid, an (X,Y) position that the user clicked on, and a color, devise an algorithm that can be used to fill appropriate part of the grid.

The bucket-fill algorithm should 'paint' all pixels that are connected to the pixel that the user clicked on, all the way to the borders where the color changes. So for example, if the user clicks on a white pixel, and specifies the color green, the bucket-fill tool will turn all of the touching white pixels into green pixels. It will not, however, affect white pixels that are in a completely separate part of the image.

A minimal Java class:

class BucketFill {

    private char[][] pixels;

    public BucketFill(char[][] pixels) {
        this.pixels = pixels;
    }

    public void fill(int x, int y, char color) {
        // TODO: make this method work
    }

    public void inspect() {
        for (int y = 0; y < pixels.length; y++) {
            for (int x = 0; x < pixels[y].length; x++) {
                System.out.print(pixels[y][x]);
            }
            System.out.print("\n");
        }
    }

    public static void main(String argv[]) {
        char pixels[][] =
        {
            { 'O', 'X', 'X', 'X', 'X' },
            { 'X', 'O', 'O', 'O', 'X' },
            { 'X', 'O', '#', 'O', 'X' },
            { 'X', 'O', 'O', 'O', 'X' },
            { 'X', 'X', 'X', 'X', 'X' },
            { 'X', 'X', 'X', '#', '#' },
            { 'X', 'X', 'X', 'X', 'X' }
        };
        BucketFill bucketFill = new BucketFill(pixels);
        bucketFill.fill(0, 0, '*');
        bucketFill.fill(3, 0, 'O');
        bucketFill.fill(2, 1, '@');
        bucketFill.inspect();
    }
}

Answer 1

Here is my approach in Java - feel free to suggest improvements:

import lombok.Getter;
import lombok.RequiredArgsConstructor;
import lombok.Value;

import java.util.Arrays;
import java.util.Queue;
import java.util.function.Function;
import java.util.stream.Collectors;


public class FloodFill {

    /**
     * @param area The whole area
     * @param x User target position X
     * @param y User target position Y
     * @param color The new color
     */
    public static void paint(int[][] area, int x, int y, int color) {
        Coordinates target = new Coordinates(x, y);
        Queue<Coordinates> queue = Arrays.stream(Direction.values()).map(direction -> direction.getNextPosition().apply(target))
                .collect(Collectors.toCollection(LinkedNoReenterQueue::new));
        paint(area, queue, color, area[x][y]);
        switchColor(area, target, color);
    }

    @RequiredArgsConstructor
    @Getter
    private enum Direction {
        NORTH(coordinates -> {
            return new Coordinates(coordinates.x, coordinates.y + 1);
        }),
        SOUTH(coordinates -> {
            return new Coordinates(coordinates.x, coordinates.y - 1);
        }),
        EAST(coordinates -> {
            return new Coordinates(coordinates.x + 1, coordinates.y);
        }),
        WEST(coordinates -> {
            return new Coordinates(coordinates.x - 1, coordinates.y);
        }),
        NORTHEAST(coordinates -> {
            return new Coordinates(coordinates.x + 1, coordinates.y + 1);
        }),
        NORTHWEST(coordinates -> {
            return new Coordinates(coordinates.x - 1, coordinates.y + 1);
        }),
        SOUTHEAST(coordinates -> {
            return new Coordinates(coordinates.x + 1, coordinates.y - 1);
        }),
        SOUTHWEST(coordinates -> {
            return new Coordinates(coordinates.x - 1, coordinates.y - 1);
        });

        private final Function<Coordinates, Coordinates> nextPosition;

    }

    @Value
    private static class Coordinates {
       int x;
       int y;
    }

    private static void switchColor(int[][] area, Coordinates coordinates, int color) {
        area[coordinates.x][coordinates.y] = color;
    }

    private static boolean shouldSwitch(int[][] area, Coordinates coordinates, int previousColor) {
        return area[coordinates.x][coordinates.y] == previousColor;
    }

    private static boolean isValid(int[][] area, Coordinates coordinates) {
        return coordinates.getX() >= 0 && coordinates.getY() >= 0 && coordinates.getX() < area.length && coordinates.getY() < area[0].length;
    }

    private static void paint(int[][] area, Queue<Coordinates> queue, int newColor, int oldColor) {
        while (!queue.isEmpty()) {
            Coordinates nextPosition = queue.poll();
            if (isValid(area, nextPosition) && shouldSwitch(area, nextPosition, oldColor)) {
                switchColor(area, nextPosition, newColor);
                for (Direction direction : Direction.values()) {
                    queue.add(direction.getNextPosition().apply(nextPosition));
                }
            }
        }
    }

}

To avoid filling the same pixels repeatedly, consider this data-structure:

import java.util.*;

public abstract class NoReenterQueue<E> extends AbstractQueue<E> {

    private Set<E> ledger;

    protected NoReenterQueue() {
        this.ledger = new HashSet<>();
    }

    @Override
    public final boolean offer(E e) {
        if (!ledger.contains(e)) {
            ledger.add(e);
            insert(e);
        }
        return true;
    }

    protected abstract boolean insert(E e);

}

And:

import java.util.Iterator;
import java.util.LinkedList;

public class LinkedNoReenterQueue<E> extends NoReenterQueue<E>{
    private LinkedList<E> linkedList = new LinkedList<>();

    @Override
    protected boolean insert(E e) {
        return linkedList.add(e);
    }

    @Override
    public Iterator<E> iterator() {
        return linkedList.iterator();
    }

    @Override
    public int size() {
        return linkedList.size();
    }

    @Override
    public E poll() {
        return linkedList.poll();
    }

    @Override
    public E peek() {
        return linkedList.peek();
    }
}

For example:

2222222
2111112
2122212
2122212
2122212
2111112
2222222

Given target=(3,3) and newColor=3:

2222222
2111112
2133312
2133312
2133312
2111112
2222222

Answer 2

You can use Flood Fill Algorithm. Flood Fill

You can implement it with stack-based recurse. It just colour the connected nodes recursively.