java - 洪水填充扫描线

Question

我写了一个经典的队列填充:

public static void floodFill(int y, int x, byte originalvalue, byte newvalue, byte[][] arr) {
    Deque queue = new ArrayDeque();
    queue.add(new int[]{y, x});
    while (!queue.isEmpty()) {
        int[] t = (int[]) queue.poll();
        y = t[0];
        x = t[1];
        if (arr[y][x] == originalvalue) {
            arr[y][x] = newvalue;
            for (int i = 0; i < 8; i++) {
                if (x + dx[i] < arr[0].length && y + dy[i] < arr.length && x + dx[i] > -1 && y + dy[i] > -1 && arr[y + dy[i]][x + dx[i]] == originalvalue) {
                    queue.add(new int[]{y + dy[i], x + dx[i]});
                }
            }
        }
    }
}

现在我想写扫描线Flood Fill，这要快得多。我找不到任何伪代码，我也不明白this code .

你能帮我优化我的洪水填充或写扫描线一吗？

对于尺寸为 1000–2000 x 1000–2000(不一定是正方形)的字节数组，我将这种填充称为一次大面积填充，然后针对较小的区域进行大约 1000 到 1,000,000 次。

Answer 1

这是一种改进的洪水填充算法。不是先填充一个像素再填充它的相邻像素，而是先填充整个水平“运行”的像素然后再填充它的相邻像素。

递归如下:

要填充(X0、X1、Y、旧、新):

# Precondition: the segment [X0 X1]/Y has the old color and can't be lengthened

在 Y-1 行中找到所有连接的运行 [X0' X1'] 具有旧颜色和 Fill(X0', X1', Y-1 , 旧的, 新的)

在 Y+1 行中找到所有连接的运行 [X0' X1'] 具有旧颜色和 Fill(X0', X1', Y+1 , 旧的, 新的)

要在新行中查找所有连接的运行，从 X0 开始，只要您在旧像素上就向左移动，或者只要您在非旧像素上就向右移动(在 X1 处停止)；你有 X0'。然后在旧像素上继续向右；你有 X1'。只要 X0' 在 [X0 X1] 中，就重复向右搜索。

一些实现细节取决于您选择的 4/8 连接规则。