Der Flood-Fill-Algorithmus

Der Flood-Fill-Algorithmus

🌐 Read in English
📅 19.11.2026 ✍ Andreas Wittmann đŸ‘ïž ... algorithm graphics computer-graphics

Bresenhams Linienalgorithmus und der Midpoint-Circle-Algorithmus zeichnen Umrisse. Flood Fill ist der nĂ€chste Schritt: Gegeben ein geschlossener Umriss und ein Pixel darin, fĂ€rbe jedes Pixel ein, das von dort aus erreichbar ist, ohne den Umriss zu ĂŒberqueren — das Farbeimer-Werkzeug aus jedem Bildbearbeitungsprogramm.

Die Idee

Man beginnt beim Startpixel. Ist es leer, wird es gefĂŒllt, und dasselbe passiert mit seinen Nachbarn. Die FĂŒllung breitet sich nach außen aus, bis sie auf allen Seiten an die Begrenzung stĂ¶ĂŸt und nicht mehr weiterkommt. Direkt hingeschrieben ist das eine rekursive Funktion mit vier Zeilen:

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

Das ist korrekt, hat aber ein ernstes Problem: Die Rekursionstiefe wĂ€chst mit der GrĂ¶ĂŸe der FlĂ€che, nicht etwa mit ihrer Breite oder Höhe. Im Beispiel unten erreicht eine FlĂ€che von gerade einmal 455 Zellen schon eine Rekursionstiefe von 250. Auf einem leeren Quadrat liegt die Tiefe bei etwa der HĂ€lfte der Pixelzahl: Eine FlĂ€che von 1000×1000 Pixeln verschachtelt rund 500.000 Aufrufe — weit mehr, als ein unter Linux ĂŒblicher 8-MB-Thread-Stack fasst, und das Programm stĂŒrzt mit einem Segmentation Fault ab.

Ein expliziter Stack

Die Lösung: Die Liste der noch zu besuchenden Zellen kommt in eine eigene Datenstruktur statt auf den Aufruf-Stack. Die Logik bleibt dieselbe — Zelle nehmen, fĂŒllen, Nachbarn vormerken —, aber die „To-do“-Liste liegt jetzt in einem gewöhnlichen Array, das so groß sein kann wie nötig. Wird eine Zelle schon beim Ablegen markiert (und nicht erst beim FĂŒllen), landet jede Zelle höchstens einmal auf dem Stack; ein Array mit einem Eintrag pro Zelle reicht also immer aus.

Implementierung

#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 →

Die Begrenzung ist ein Kreis, gezeichnet mit dem Midpoint-Circle- Algorithmus — diesmal auf einem Raster aus 16×16 Pixel großen Zellen statt auf einzelnen Pixeln —, dazu eine Wand mit LĂŒcke und ein massiver Block, damit die FĂŒllung ihren Weg um Hindernisse herum finden muss. Die Farben zeigen den Zustand jeder Zelle: Blau ist die Begrenzung, rote Zellen warten auf dem Stack, grĂŒne Zellen sind gefĂŒllt.

Mit SCANLINE = false nimmt step_four_way pro Schritt eine Zelle vom Stack, fĂŒllt sie und legt ihre vier Nachbarn ab. Weil der Stack immer mit der zuletzt abgelegten Zelle weitermacht, lĂ€uft die FĂŒllung in langen Streifen davon — eine Tiefensuche — und hinterlĂ€sst eine Spur roter Zellen, die erst spĂ€ter abgearbeitet werden. FĂŒr diese Form wĂ€chst der Stack auf 166 EintrĂ€ge.

Scanline-Fill

Die meisten dieser Push-Operationen sind verschwendet: Der linke und rechte Nachbar einer Zelle werden ohnehin fast immer als NĂ€chstes gefĂŒllt. Scanline-Fill nutzt das aus. Jeder Schritt nimmt einen Startpunkt vom Stack und

  1. lÀuft von dort nach links und rechts, bis er auf die Begrenzung trifft,
  2. fĂŒllt diesen ganzen waagrechten Abschnitt auf einmal,
  3. schaut sich die Zeilen direkt darĂŒber und darunter an und legt fĂŒr jeden zusammenhĂ€ngenden Bereich leerer Zellen dort genau einen neuen Startpunkt ab.

Ändere im Code oben SCANLINE auf true und klicke auf „Compile & Run“, um den Unterschied zu sehen: Die FlĂ€che fĂŒllt sich jetzt Zeile fĂŒr Zeile, und es warten nie mehr als eine Handvoll roter Startpunkte. FĂŒr dieselbe Form braucht Scanline-Fill 34 statt 455 Schritte und einen Stack von höchstens 4 statt 166 EintrĂ€gen — und fĂŒllt dabei exakt dieselben 455 Zellen.

4er- oder 8er-Nachbarschaft?

Die Beispiele oben betrachten nur die vier direkten Nachbarn — links, rechts, oben, unten — als verbunden. Ein 8-Wege-Fill zĂ€hlt auch die vier diagonalen Nachbarn dazu. Das klingt nach einer harmlosen Erweiterung, Ă€ndert aber, welche Umrisse als geschlossen gelten.

Ein Kreis aus dem Midpoint-Circle-Algorithmus hĂ€ngt ĂŒberall dort nur diagonal zusammen, wo er gleichzeitig in x und y um ein Pixel springt. Ein 4-Wege-Fill kann sich nicht zwischen zwei Pixeln hindurchzwĂ€ngen, die sich nur an einer Ecke berĂŒhren — fĂŒr ihn ist der Umriss geschlossen. Ein 8-Wege-Fill kann das und lĂ€uft direkt hindurch: Bei der Beispielform entkommt er aus dem Kreis und fĂŒllt 1086 statt 455 Zellen. Ein 4-Wege-Fill gehört also zu 8-fach verbundenen Umrissen, wie sie Bresenham und der Midpoint-Circle-Algorithmus erzeugen, und ein 8-Wege-Fill funktioniert nur innerhalb von Umrissen, die 4-fach verbunden sind.

Fazit

Flood Fill ist eine verkleidete Graphensuche: Die Zellen sind Knoten, benachbarte leere Zellen sind verbunden, und FĂŒllen heißt, alles zu besuchen, was vom Startpunkt aus erreichbar ist. Die rekursive Variante ist die kĂŒrzeste Art, das hinzuschreiben, der explizite Stack macht sie fĂŒr jede GrĂ¶ĂŸe sicher, und Scanline-Fill macht sie schnell, indem ganze Pixelreihen auf einmal statt Pixel fĂŒr Pixel abgearbeitet werden.