imported>Invisigoth67: typo

2024-03-02T09:08:27Z

typo

Neue Seite

'''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 [[Rekursive Programmierung|rekursiven]] Implementierung.

=== 4-connected oder 4-Neighbour ===
[[Datei:Recursive Flood Fill 4 (aka).gif|rechts|Schema]]
Es werden jeweils die 4 benachbarten [[Pixel]] unten, links, oben und rechts vom Ausgangspunkt untersucht. Der Koordinatenursprung ist die Ecke links oben.
<syntaxhighlight lang="python">
def 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) # rechts
fill4(x - 1, y, alteFarbe, neueFarbe) # links
</syntaxhighlight>
=== 8-connected oder 8-Neighbour ===
[[Datei:Recursive Flood Fill 8 (aka).gif|rechts|Schema]]
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.

<syntaxhighlight lang="python">
def 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) # rechts unten
fill8(x + 1, y - 1, alteFarbe, neueFarbe) # rechts oben
fill8(x - 1, y + 1, alteFarbe, neueFarbe) # links unten
fill8(x - 1, y - 1, alteFarbe, neueFarbe) # links oben
</syntaxhighlight>
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 [[Rekursive Programmierung|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 (Datenstruktur)|Warteschlange]], eines [[Stapelspeicher]]s oder einer ähnlichen [[Datenstruktur]] ist auch eine [[Iteration|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 [[Computerprogramm|Programm]] in der [[Programmiersprache]] [[C-Sharp|C#]] verwendet zwei verschachtelte [[While-Schleife|while-Schleifen]] für eine [[Breitensuche]] der [[Pixel]] mit derselben Farbe.<ref>Rosetta Code: [https://rosettacode.org/wiki/Bitmap/Flood_fill Bitmap/Flood fill]</ref><ref>GeeksforGeeks: [https://www.geeksforgeeks.org/flood-fill-algorithm-implement-fill-paint/ Flood fill Algorithm]</ref><syntaxhighlight lang="c#">
using System;
using System.Collections.Generic;
using System.Drawing;

namespace FloodFill
{
class Program
{
// Diese Methode gibt true zurück, wenn die beiden Farben gleich sind, sonst false
private static bool ColorMatch(Color replacementColor, Color targetColor)
{
return replacementColor.ToArgb() == targetColor.ToArgb();
}

// Diese Methode füllt alle zusammenhängenden Pixel, die dieselbe Farbe wie das Startpixel haben, mit der neuen Farbe
private static void FloodFill(Bitmap bitmap, Point point, Color replacementColor)
{
Color targetColor = bitmap.GetPixel(point.X, point.Y); // Speichert die Farbe des Startpixels
Queue<Point> queue = new Queue<Point>(); // Warteschlange der Pixel für die Breitensuche
queue.Enqueue(point); // Fügt das Startpixel der Warteschlange hinzu
while (queue.Count != 0) // So lange die Warteschlange nicht leer ist
{
Point point1 = queue.Dequeue(); // Entfernt das erste Pixel aus der Warteschlange
if (!ColorMatch(bitmap.GetPixel(point1.X, point1.Y), targetColor)) // Wenn die Farbe des aktuellen Pixels gleich dem Startpixel ist, wird die nächste Iteration der äußeren while-Schleife ausgeführt
{
continue;
}
Point point2 = new Point(point1.X + 1, point1.Y); // Speichert das Pixel rechts vom aktuellen Pixel
while (point1.X >= 0 && ColorMatch(bitmap.GetPixel(point1.X, point1.Y), targetColor)) // So lange das aktuelle Pixel nicht links vom Rand ist und die Farbe des Startpixels hat
{
bitmap.SetPixel(point1.X, point1.Y, replacementColor); // Setzt das aktuelle Pixel auf die neue Farbe
if (point1.Y > 0 && ColorMatch(bitmap.GetPixel(point1.X, point1.Y - 1), targetColor)) // Wenn das aktuelle Pixel nicht am linken Rand ist und die Farbe des Startpixels hat
{
queue.Enqueue(new Point(point1.X, point1.Y - 1)); // Fügt das Pixel über dem aktuellen Pixel der Warteschlange hinzu
}
if (point1.Y < bitmap.Height - 1 && ColorMatch(bitmap.GetPixel(point1.X, point1.Y + 1), targetColor)) // Wenn das aktuelle Pixel nicht am rechten Rand ist und die Farbe des Startpixels hat
{
queue.Enqueue(new Point(point1.X, point1.Y + 1)); // Fügt das Pixel unter dem aktuellen Pixel der Warteschlange hinzu
}
point1.X--; // Verschiebt das aktuelle Pixel um 1 nach links
}
// Die folgende while-Schleife wiederholt den Ablauf mit dem Pixel rechts vom aktuellen Pixel
while (point2.X <= bitmap.Width - 1 && ColorMatch(bitmap.GetPixel(point2.X, point2.Y), targetColor))
{
bitmap.SetPixel(point2.X, point2.Y, replacementColor);
if (point2.Y > 0 && ColorMatch(bitmap.GetPixel(point2.X, point2.Y - 1), targetColor))
{
queue.Enqueue(new Point(point2.X, point2.Y - 1));
}
if (point2.Y < bitmap.Height - 1 && ColorMatch(bitmap.GetPixel(point2.X, point2.Y + 1), targetColor))
{
queue.Enqueue(new Point(point2.X, point2.Y + 1));
}
point2.X++; // Verschiebt das aktuelle Pixel um 1 nach rechts
}
}
}

// Hauptmethode, die das Programm ausführt
public static void Main(string[] args)
{
Bitmap bitmap = new Bitmap("UnfilledCircle.png"); // Weist den Inhalt der Bilddatei mit dem angegebenen Dateinamen der Variablen der Klasse Bitmap hinzu
FloodFill(bitmap, new Point(200, 200), Color.Red); // Aufruf der Methode mit den Parametern für Startpixel und Farbe
bitmap.Save("FilledCircle.png"); // Speichert das geänderte Bitmap als Bilddatei mit dem angegebenen Dateinamen
}
}
}
</syntaxhighlight>

==== Python ====
<syntaxhighlight lang="python">
def 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)
</syntaxhighlight>
Dieses [[Iterative Programmierung|iterative]] Beispiel entspricht dem rekursiven Algorithmus mit vier Nachbarn. Derjenige mit acht Nachbarn wird entsprechend analog implementiert.

Anstatt auf dem [[Stapelspeicher|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.<ref>[https://github.com/minetest/minetest/blob/f7c7353a9a9446a2fb6b3b0cb24deec0851d7291/builtin/game/falling.lua#L401 Tiefensuche von zusammenhängenden Nodes in] [[Minetest]]</ref>

== Teiliterative Implementierung ==
Bei teiliterativer Implementierung besteht der Algorithmus aus einem [[Iterative Programmierung|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 Programmierung|rekursive]] Teil gestartet, der nun deutlich weniger tief in die [[Rekursion]] geht. Somit ist ein [[Stack Overflow]] weniger wahrscheinlich.

== Einzelnachweise ==
<references />

[[Kategorie:Computergrafik]]
[[Kategorie:Algorithmus (Computergrafik)]]

Floodfill - Versionsgeschichte

imported>Invisigoth67: typo