Floodfill

Floodfill bzw. Flutfüllung ist ein Begriff aus der Computergrafik. Es ist ein einfacher Algorithmus, um Flächen zusammenhängender Pixel einer Farbe in einem digitalen Bild zu erfassen und mit einer neuen Farbe zu füllen.

Ausgehend von einem Pixel innerhalb der Fläche werden jeweils dessen Nachbarpixel darauf getestet, ob diese Nachbarpixel auch die alte Farbe enthalten. Jedes gefundene Pixel mit der alten Farbe wird dabei sofort durch die neue Farbe ersetzt.

Zwei Varianten des Algorithmus sind gängig:

4-connected oder 4-Neighbour

Es werden jeweils die vier benachbarten Pixel unten, links, oben und rechts vom Ausgangspunkt untersucht (Koordinatenursprung ist links-oben im Eck).

fill4(x, y, alteFarbe, neueFarbe) {

  if (getPixel(x, y) == alteFarbe) {

     setPixel(x, y, neueFarbe);

     fill4(x, y + 1, alteFarbe, neueFarbe); // unten
     fill4(x, y - 1, alteFarbe, neueFarbe); // oben
     fill4(x - 1, y, alteFarbe, neueFarbe); // links
     fill4(x + 1, y, alteFarbe, neueFarbe); // rechts

  }
  return;
}

8-connected oder 8-Neighbour

Es werden jeweils die acht benachbarten Pixel oben, unten, links, rechts, oben-links, oben-rechts, unten-links und unten-rechts vom Ausgangspunkt untersucht (Koordinatenursprung ist links-oben im Eck).

fill8(x, y, alteFarbe, neueFarbe) {

  if (getPixel(x, y) == alteFarbe) {

     setPixel(x, y, neueFarbe);

     fill8(x, y + 1, alteFarbe, neueFarbe);        //unten
     fill8(x, y - 1, alteFarbe, neueFarbe);        //oben
     fill8(x + 1, y, alteFarbe, neueFarbe);        //rechts
     fill8(x - 1, y, alteFarbe, neueFarbe);        //links
     fill8(x + 1, y + 1, alteFarbe, neueFarbe);    //unten-rechts
     fill8(x + 1, y - 1, alteFarbe, neueFarbe);    //oben-rechts
     fill8(x - 1, y + 1, alteFarbe, neueFarbe);    //unten-links
     fill8(x - 1, y - 1, alteFarbe, neueFarbe);    //oben-links

  }
  return;
}

Bei gleichen Ausgangsbedingungen füllt die 8-connected-Variante üblicherweise einen größeren Bereich als die 4-connected-Variante, da sie „durch feine Ritzen kriecht“. Dies ist häufig nicht gewünscht.

Aufgrund der Einfachheit des Algorithmus eignet er sich nur bedingt für nicht-triviale Anwendungen. Der Algorithmus ist hoch-rekursiv. Daher besteht ein hohes Risiko, dass der Algorithmus zu einem Stack-Überlauf führt. Ebenso benötigen die möglichen vielen Stack-Operationen durch die Rekursionen im Vergleich zu den eigentlichen Operationen des Algorithmus relativ viel Zeit.

Nicht zuletzt sind viele Rekursionsaufrufe des Algorithmus unnötig, da dabei unnötigerweise Pixel getestet werden, die kurz zuvor bereits auf die neue Farbe gesetzt wurden. Jede Rekursion trifft mindestens auf ein solches Pixel, jenes Pixel, welches gerade im darüberliegenden Rekursionslevel markiert wurde.

Iterative Flutfüllung

Mit Hilfe eines Stapelspeichers oder einer ähnlichen Datenstruktur ist auch eine iterative Implementierung möglich. Dabei werden die Nachbarpixel-Koordinaten gespeichert und dann nacheinander abgearbeitet. Die Reihenfolge, in der die Koordinaten aus der Datenstruktur ausgelesen werden, spielt dabei keine Rolle. Durch das hohe Risiko eines Stack-Überlaufs bei der rekursiven Flutfüllung ist die iterative Version in der Regel die bessere Wahl zur Implementierung des Verfahrens.

fill4(x, y, alteFarbe, neueFarbe) {

   stack.push(x, y);

   while(stack.isNotEmpty) {
      (x, y) = stack.pop;

      if (getPixel(x, y) == alteFarbe) {
         setPixel(x, y, neueFarbe);

         stack.push(x, y + 1);
         stack.push(x, y - 1);
         stack.push(x + 1, y);
         stack.push(x - 1, y);
      }
   }
   return;
}

Dieses Beispiel entspricht dem rekursiven Algorithmus mit vier Nachbarn. Derjenige mit acht Nachbarn wird entsprechend analog implementiert.

Teiliterative Flutfüllung (Span Flood Fill)

Bei teiliterativer Flutfüllung besteht der Algorithmus aus einem iterativen Teil, der immer weiterläuft und sich immer in eine bestimmte Richtung wendet, zum Beispiel immer linksherum. Wenn der iterative Teil keine Pixel mehr zum Einfärben findet, wird der rekursive Teil gestartet, der nun deutlich weniger tief in die Rekursion geht. Somit ist ein Stack-Überlauf weniger wahrscheinlich.