Заливка с использованием стека

Вы можете использовать Queue для удаления рекурсии из алгоритма заполнения. Вот несколько основных идей:

1. Иметь способ отмечать посещенные точки
2. В начале поставьте в очередь начальную точку.
3. While the queue is not empty, continue dequeuing its element. And with each element
   1. Fill its color and mark just-dequeued point as visited
   2. Ставить в очередь непосещенные соседние точки того же цвета

Ниже приведен мой Java-код для решения похожей, но другой проблемы обнаружения больших двоичных объектов. Я надеюсь, что вы можете извлечь из этого некоторые идеи и адаптировать их к проблеме. Однако код не очень хорошо продуман.

package blobdetector;

import java.awt.Point;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import javax.imageio.ImageIO;
import javax.management.Query;

public class Main {

    public Main() {
    }

    public static boolean isBlack(BufferedImage image, int posX, int posY) {

        int color = image.getRGB(posX, posY);

        int brightness = (color & 0xFF) + ((color >> 2) & 0xFF)
        + ((color >> 4) & 0xFF);
        brightness /= 3;

        return brightness < 128;
    }

    public static void main(String[] args) {
        if (args.length != 1) {
            System.err.println("ERROR: Pass filename as argument.");
            return;
        }

        String filename = args[0];
        // String filename =
        // "C:\\Users\\Natthawut\\Desktop\\blob.jpg";
        try {
            BufferedImage bimg = ImageIO.read(new File(filename));

            boolean[][] painted = new boolean[bimg.getHeight()][bimg.getWidth()];

            for (int i = 0; i < bimg.getHeight(); i++) {
                for (int j = 0; j < bimg.getWidth(); j++) {

                    if (isBlack(bimg, j, i) && !painted[i][j]) {

                        Queue<Point> queue = new LinkedList<Point>();
                        queue.add(new Point(j, i));

                        int pixelCount = 0;
                        while (!queue.isEmpty()) {
                            Point p = queue.remove();

                            if ((p.x >= 0)
                                    && (p.x < bimg.getWidth() && (p.y >= 0) && (p.y < bimg
                                            .getHeight()))) {
                                if (!painted[p.y][p.x]
                                                  && isBlack(bimg, p.x, p.y)) {
                                    painted[p.y][p.x] = true;
                                    pixelCount++;

                                    queue.add(new Point(p.x + 1, p.y));
                                    queue.add(new Point(p.x - 1, p.y));
                                    queue.add(new Point(p.x, p.y + 1));
                                    queue.add(new Point(p.x, p.y - 1));
                                }
                            }
                        }
                        System.out.println("Blob detected : " + pixelCount
                                + " pixels");
                    }

                }
            }

        } catch (IOException ex) {
            ex.printStackTrace();
        }

    }

}

Тестовый ввод:

вот моя база реализации на основе информации с этой страницы и других, собранных в Интернете (проверено и работает)

развлекайся ;-)

public static void floodFillImage(BufferedImage image,int x, int y, Color color) 
{
    int srcColor = image.getRGB(x, y);
    boolean[][] hits = new boolean[image.getHeight()][image.getWidth()];

    Queue<Point> queue = new LinkedList<Point>();
    queue.add(new Point(x, y));

    while (!queue.isEmpty()) 
    {
        Point p = queue.remove();

        if(floodFillImageDo(image,hits,p.x,p.y, srcColor, color.getRGB()))
        {     
            queue.add(new Point(p.x,p.y - 1)); 
            queue.add(new Point(p.x,p.y + 1)); 
            queue.add(new Point(p.x - 1,p.y)); 
            queue.add(new Point(p.x + 1,p.y)); 
        }
    }
}

private static boolean floodFillImageDo(BufferedImage image, boolean[][] hits,int x, int y, int srcColor, int tgtColor) 
{
    if (y < 0) return false;
    if (x < 0) return false;
    if (y > image.getHeight()-1) return false;
    if (x > image.getWidth()-1) return false;

    if (hits[y][x]) return false;

    if (image.getRGB(x, y)!=srcColor)
        return false;

    // valid, paint it

    image.setRGB(x, y, tgtColor);
    hits[y][x] = true;
    return true;
}

Вы должны вернуть последний операторfloodFill, превратив его в хвостовой вызов. Это сэкономит вам место в стеке.

Важным моментом в заливке заливки является то, обрабатываете ли вы точки сначала в глубину или в ширину. Сначала в глубину — это исходное решение, которое вы рассматривали с использованием стека, а в ширину — алгоритмы, показанные ниже, использующие очередь для хранения точки. Разница существенна при заполнении больших выпуклых пространств. Метод «сначала в ширину» сохраняет идеально выпуклую область примерно на краю круга (или краю заливки). Если вы используете метод «сначала в глубину», вы можете в худшем случае сохранить каждый пиксель в конксекс-области, это означает, что в худшем случае для заливки изображения размером 1000x1000 может потребоваться 1000000 кадров стека.