Floodfill
# 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.

## Rekursive Implementierung

Es gibt zwei Varianten der rekursiven Implementierung.

### 4-connected oder 4-Neighbour

Es werden jeweils die 4 benachbarten Pixel unten, links, oben und rechts vom Ausgangspunkt untersucht. Der Koordinatenursprung ist die Ecke links oben.

### 8-connected oder 8-Neighbour

Es werden jeweils die 8 benachbarten Pixel oben, unten, links, rechts, oben-links, oben-rechts, unten-links und unten-rechts vom Ausgangspunkt untersucht. Der Koordinatenursprung ist die Ecke links oben.

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“. Je nach Anwendungsfall kann dies gewünscht sein oder auch nicht.

Der Algorithmus in der rekursiven Form ist zwar einfach zu formulieren und zu verstehen, eignet sich jedoch nur bedingt für nicht-triviale Anwendungen. Der Algorithmus ist überaus rekursiv. Daher besteht ein hohes Risiko, dass der Algorithmus zu einem Stack Overflow 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 Implementierung

### Programmierung

Mit Hilfe einer Warteschlange, 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 Overflow bei der rekursiven Implementierung ist die iterative Version in der Regel die bessere Wahl zur Implementierung des Verfahrens.

**C#**

Das folgende Programm in der Programmiersprache C# verwendet zwei verschachtelte while-Schleifen für eine Breitensuche der Pixel mit derselben Farbe.

**Python**

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

Anstatt auf dem Stack die als nächstes zu testenden Positionen zu speichern, ist es möglich, die vorherigen Positionen und Richtungen zu speichern. Der Stack enthält dadurch nur den Pfad zur derzeitigen Position, was den Algorithmus speichereffizienter macht.

## Teiliterative Implementierung

Bei teiliterativer Implementierung 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 Overflow weniger wahrscheinlich.

