CODEWITHSUNDEEP
javaalgorithmflood-fill
JohnDow
JohnDow

Reputation: 1322

Flood Fill scan line

I wrote a classic queue floodfill:

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]});
                }
            }
        }
    }
}

And now I want to write scan line Flood Fill, which is much faster. I can't find any pseudocode, and I don't understand this code.

Can you help me optimize my flood fill or write scan line one?

I call this flood fill for a byte array with dimensions 1000–2000 by 1000–2000 (not necessarily square) for a large area once, and then about 1000 to 1,000,000 times for smaller areas.

Upvotes: 0

Views: 3344

Answers (1)

user1196549
user1196549

Reputation:

This is a modified flood-fill algorithm. Rather than filling a pixel and then its neighbors, you fill a whole horizontal "run" of pixels and then its neighbors.

The recursion goes as follows:

To Fill(X0, X1, Y, Old, New):

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

Find all connected runs [X0' X1'] in row Y-1 having old color and Fill(X0', X1', Y-1, Old, New)

Find all connected runs [X0' X1'] in row Y+1 having old color and Fill(X0', X1', Y+1, Old, New)

To find all connected runs in a new row, start from X0 and move left as long as you are on an old pixel, or move right as long as you are on an non-old pixel (stop at X1); you have X0'. Then continue to the right on old pixels; you have X1'. Repeat the search to the right as long as X0' is in [X0 X1].

A few implementation details depend on the 4/8 connexity rule you choose.

Upvotes: 1

Related Questions