The Flood Fill Algorithm

The Flood Fill Algorithm

🌐 Auf Deutsch lesen
📅 2026-11-19 ✍️ Andreas Wittmann 👁️ ... algorithm graphics computer-graphics

Bresenham's line algorithm and the midpoint circle algorithm draw outlines. Flood fill is what comes next: given a closed outline and one pixel inside it, color every pixel that can be reached from there without crossing the outline — the paint bucket tool in every image editor.

The idea

Start at the seed pixel. If it is empty, fill it, then do the same for its neighbors. The fill spreads outward until it hits the boundary on every side and has nowhere left to go. Written down directly, that is a four-line recursive function:

void flood_fill(int x, int y) {
    if (!inside(x, y) || grid[y][x] != EMPTY) return;
    grid[y][x] = FILLED;
    flood_fill(x + 1, y);
    flood_fill(x - 1, y);
    flood_fill(x, y + 1);
    flood_fill(x, y - 1);
}

It is correct, but it has a serious problem: the recursion depth grows with the size of the area, not with anything like its width or height. In the example below, a region of just 455 cells already reaches a recursion depth of 250. On an empty square, the depth comes out at about half the number of pixels: a 1000×1000 area nests around 500,000 calls deep, far beyond what a default 8 MB thread stack on Linux can hold, and the program crashes with a segmentation fault.

An explicit stack

The fix is to keep the list of cells still to visit in a data structure of your own instead of on the call stack. The logic stays the same — take a cell, fill it, add its neighbors — but the "to do" list now lives in an ordinary array that can be as large as needed. Marking a cell as soon as it is pushed (not only when it is filled) guarantees that every cell goes onto the stack at most once, so an array with one entry per cell is always enough.

Implementation

#include "plot.hpp"

// false: 4-way flood fill, one cell per step
// true:  scanline fill, one whole horizontal span per step
const bool SCANLINE = false;

const int CELL = 16;
const int W = 640 / CELL; // 40 columns
const int H = 480 / CELL; // 30 rows

enum { EMPTY, WALL, QUEUED, FILLED };
int grid[H][W];

// Explicit stack instead of recursion. Every cell is pushed at most once
// (it is marked QUEUED right away), so W * H entries are always enough.
int stackX[W * H];
int stackY[W * H];
int top = -1;

bool done = false;
int tick = 0;

bool inside(int x, int y) {
    return x >= 0 && x < W && y >= 0 && y < H;
}

void wall(int x, int y) {
    if (inside(x, y)) grid[y][x] = WALL;
}

// The boundary: the midpoint circle algorithm, plotting grid cells
// instead of pixels.
void midpoint_circle(int cx, int cy, int r) {
    int x = 0, y = r, d = 1 - r;
    while (x <= y) {
        wall(cx + x, cy + y); wall(cx - x, cy + y);
        wall(cx + x, cy - y); wall(cx - x, cy - y);
        wall(cx + y, cy + x); wall(cx - y, cy + x);
        wall(cx + y, cy - x); wall(cx - y, cy - x);
        x++;
        if (d < 0) {
            d += 2 * x + 1;
        } else {
            y--;
            d += 2 * x - 2 * y + 1;
        }
    }
}

void push(int x, int y) {
    if (inside(x, y) && grid[y][x] == EMPTY) {
        grid[y][x] = QUEUED;
        top++;
        stackX[top] = x;
        stackY[top] = y;
    }
}

// 4-way flood fill: take one cell off the stack, fill it, and push its
// four neighbors.
void step_four_way() {
    int x = stackX[top];
    int y = stackY[top];
    top--;

    grid[y][x] = FILLED;
    push(x + 1, y);
    push(x - 1, y);
    push(x, y + 1);
    push(x, y - 1);
}

bool fillable(int x, int y) {
    return inside(x, y) && (grid[y][x] == EMPTY || grid[y][x] == QUEUED);
}

// Scanline fill: take one seed off the stack, extend it left and right
// as far as possible, fill that whole span, then push one new seed for
// every separate empty run directly above and below it.
void step_scanline() {
    int x = stackX[top];
    int y = stackY[top];
    top--;

    int left = x, right = x;
    while (fillable(left - 1, y)) left--;
    while (fillable(right + 1, y)) right++;

    for (int i = left; i <= right; i++) grid[y][i] = FILLED;

    for (int dy = -1; dy <= 1; dy += 2) {
        bool inRun = false;
        for (int i = left; i <= right; i++) {
            bool empty = inside(i, y + dy) && grid[y + dy][i] == EMPTY;
            if (empty && !inRun) push(i, y + dy);
            inRun = empty;
        }
    }
}

void setup() {
    PlotCanvas(640, 480);

    midpoint_circle(20, 15, 13);
    for (int x = 10; x <= 30; x++) {
        if (x < 18 || x > 21) wall(x, 11); // a wall with a gap
    }
    for (int y = 17; y <= 21; y++) {
        for (int x = 23; x <= 27; x++) wall(x, y); // a solid block
    }

    push(14, 15); // the seed cell
}

void frame() {
    // 4-way fill: two cells per frame. Scanline: one span every 6 frames,
    // since each step fills a lot more at once.
    if (!done && ++tick >= (SCANLINE ? 6 : 1)) {
        tick = 0;
        for (int n = 0; n < (SCANLINE ? 1 : 2) && top >= 0; n++) {
            if (SCANLINE) step_scanline();
            else step_four_way();
        }
        if (top < 0) done = true;
    }

    PlotBackground(250, 250, 250);

    for (int y = 0; y < H; y++) {
        for (int x = 0; x < W; x++) {
            int c = grid[y][x];
            if (c == EMPTY) continue;
            if (c == WALL)        PlotColor(30, 100, 200);  // boundary
            else if (c == QUEUED) PlotColor(220, 60, 60);   // waiting on the stack
            else                  PlotColor(70, 170, 90);   // filled
            PlotFilledRectangle(x * CELL + 1, y * CELL + 1,
                                x * CELL + CELL - 1, y * CELL + CELL - 1);
        }
    }
}
Open in full editor →

The boundary is a circle drawn with the midpoint circle algorithm, this time on a grid of 16×16 pixel cells instead of single pixels, plus a wall with a gap and a solid block, so the fill has to find its way around obstacles. The colors show the state of each cell: blue is the boundary, red cells are waiting on the stack, and green cells are filled.

With SCANLINE = false, step_four_way takes one cell off the stack per step, fills it, and pushes its four neighbors. Because the stack always continues with the most recently added cell, the fill runs off in long stripes, a depth-first search, and leaves a trail of red cells behind that will only be processed later. For this shape the stack grows to 166 entries.

Scanline fill

Most of those pushes are wasteful: a cell's left and right neighbors are almost always going to be filled next anyway. Scanline fill takes advantage of that. Each step takes one seed off the stack and:

  1. extends left and right from the seed until it hits the boundary,
  2. fills that whole horizontal span in one go,
  3. looks at the rows directly above and below the span and pushes exactly one new seed for every separate run of empty cells there.

Change SCANLINE to true in the code above and press "Compile & Run" to see the difference: the region now fills row by row, and there are never more than a handful of red seeds waiting. For the same shape, scanline fill needs 34 steps instead of 455 and a stack of at most 4 entries instead of 166, while filling exactly the same 455 cells.

4-way or 8-way?

The examples above treat only the four direct neighbors — left, right, up, down — as connected. An 8-way fill also counts the four diagonal neighbors. That sounds like a harmless extension, but it changes which outlines count as closed.

A circle from the midpoint circle algorithm is only connected diagonally wherever it steps by one pixel in both x and y. A 4-way fill cannot squeeze between two pixels that only touch at a corner, so for it the outline is closed. An 8-way fill can, and leaks straight through: for the example shape it escapes the circle and fills 1086 cells instead of 455. So a 4-way fill belongs with 8-connected outlines like the ones Bresenham's and the midpoint circle algorithm produce, and an 8-way fill only works inside outlines that are 4-connected.

Conclusion

Flood fill is a graph search in disguise: the cells are nodes, adjacent empty cells are connected, and filling means visiting everything reachable from the seed. The recursive version is the shortest way to write that down, the explicit stack makes it safe for any size, and scanline fill makes it fast by handling whole runs of pixels at once instead of one pixel at a time.