Der Diffusionsfüllalgorithmus ist ein klassischer Algorithmus in der Computergrafik, der die Farbe eines verwandten Satzes von Pixeln derselben Farbe ändert, die durch Umrisse begrenzt sind. Es wird häufig von Rasterbild- Manipulationsprogrammen wie Paint verwendet. Es findet auch seine Anwendung in bestimmten Spielen wie Minesweeper , Puyo Puyo und Lumines, um zu bestimmen, welche Elemente des Spielbretts enthüllt werden sollen.
Der Diffusions Füllalgorithmus nimmt drei Parameter für ein gegebenes Bild: die Position des Ausgangspixels (auch als Saatgut), die Zielfarbe ( colcible ) und die Ersatzfarbe ( colrep ). Der Algorithmus identifiziert alle Pixel des Bildes, die durch einen Pfad der Zielfarbe mit dem Startwert verbunden sind, und ersetzt diesen durch die Ersatzfarbe. Es gibt verschiedene Möglichkeiten, diesen Algorithmus zu strukturieren, aber alle verwenden implizit oder explizit einen Stapel , um die Berechnung durchzuführen.
Die rekursive Formulierung verwendet implizit einen Stapel.
Wenn das Bild herkömmlicherweise aus quadratischen oder rechteckigen Pixeln besteht , berücksichtigt die 4-bezogene Variante die 4 Nachbarn eines Pixels, die eine Kante mit letzteren gemeinsam haben. Die Formulierung des Algorithmus ist wie folgt:
remplissage4(pixel, colcible, colrep) début si couleur(pixel) = colcible alors couleur(pixel) ← colrep remplissage4(pixel au nord, colcible, colrep) remplissage4(pixel au sud, colcible, colrep) remplissage4(pixel à l'est, colcible, colrep) remplissage4(pixel à l'ouest, colcible, colrep) finsi finDie vorhergehende rekursive Formulierung wird in der Praxis häufig nicht verwendet, wenn sie den Vorteil hat, durch ihre Formulierung intuitiv zu sein, insbesondere in Ausführungsumgebungen, in denen der Aufrufstapel von Funktionen stark eingeschränkt oder reduziert ist. Sie sollten dann Ihren eigenen Stapel erstellen, in dem die zu scannenden Pixel gespeichert werden. Der Algorithmus für die 4-verbundene Variante lautet dann wie folgt:
remplissage4(pixel, colcible, colrep) début Soit P une pile vide si couleur(pixel) ≠ colcible alors sortir finsi Empiler pixel sur P Tant que P non vide faire Dépiler n de P couleur(n) ← colrep si couleur(n nord) = colcible alors Empiler n nord sur P finsi si couleur(n sud) = colcible alors Empiler n sud sur P finsi si couleur(n est) = colcible alors Empiler n est sur P finsi si couleur(n ouest)= colcible alors Empiler n ouest sur P finsi fintantque finDie meisten Implementierungen verwenden eine Schleife, die sowohl "Ost" als auch "West" verbreitet, um die Stapelverwaltung zu vereinfachen. Der verwendete Algorithmus ist dann:
remplissage4(pixel, colcible, colrep) début Soit P une pile vide si couleur(pixel) ≠ colcible alors sortir de la fonction Empiler pixel sur P Tant que P non vide faire Dépiler n de P si couleur(n) = colcible alors w ← n e ← n Déplacer w vers l'ouest jusqu'à ce que couleur(w) ≠ colcible Déplacer e vers l'est jusqu'à ce que couleur(e) ≠ colcible Pour tout pixel p entre w et e Faire couleur(p) ← colrep si couleur(p nord) = colcible alors Empiler p nord sur P finsi si couleur(p sud ) = colcible alors Empiler p sud sur P finsi finpour finsi fintantque fin Die Linien fegenDer Algorithmus kann durch direktes Ausfüllen von Zeilen beschleunigt werden. Anstatt jedes neue potenzielle Pixel zu stapeln, überprüfen Sie einfach die nächsten und vorherigen Zeilen, die in einem zukünftigen Durchgang farbig werden. Die Koordinaten der Enden des zu färbenden Segments werden dann gestapelt. In den meisten Fällen ist diese Variante des Algorithmus schneller als die pixelbasierte Version.