FloodFill Rekursiv

[dizzy]

Nochmal zum Overflow:

Wie groß ist dein Bild, bzw. der zu füllende Bereich ca.? Diese Methode zum Füllen tendiert nämlich dazu, seeeehr tief in die Rekursion zu gehen. Die Erste "Füll-Ameise" läuft ja durch, bis sie in einer Sackgasse landet. Das kann im Optimalfall schon der gesamte Füllbereich sein! Je nach Größe, Form und Startpunkt wandern dann mehrere tausend Aufrufe aufm Stack.

Wenn das der Fall ist, und andere Quellen für den Overflow auszuschließen sind, gäbe es zwei Auswege:

1. Umsetzung in iteratives Vorgehen. Es wird angenommen, dass jede Rekursion in eine Iteration überführbar ist. Für den Umgekehrten Fall ist es bereits allgemein bewiesen, ob so rum mittlerweile auch weiss ich grad nicht.
   Da jeder Rekursionsschritt gleich 4 neue auslöst wird das allerdings vermute ich etwas aufwändiger was das Rahmenwerk an Zählern und Bedingungen angeht.
   
2. Festlegen einer maximalen Rekursionstiefe. DoPixel() würde einen Parameter mehr bekommen, einen Zähler der für jeden neuen Aufruf um je eins erhöht wird. In der Prozedur dann ab einer gewissen Tiefe nicht mehr weiter machen.
   Im Ergebnis können zwei Dinge passieren:
   1) Die Tiefe reicht aus, deine Form und Startpunkt waren glücklich gewählt, so dass die Fläche trotdem ganz erfasst wird.
   2) Die Füllung erhält Lücken.
   Im Fall 2 könntest du dann her gehen, und in der Map verbleibende Flecken suchen, und dort einen neuen Floodfill ansetzen, und das ganze so lange wiederholen, bis sich keine Flecken mehr finden. Dieses Verfahren wird jedoch auch etwas Aufwendiger, und sicherlich nicht weniger anspruchsvoll wie die Umsetzung in eine Iteration.

Es gibt noch einen 3. Ausweg, der aber extrem unschön ist, und nur Symptome bekämpft: In den Projektoptionen den Stack vergrößern. Auf den ersten Blick eine tolle Idee, weil einfach und super schnell gemacht, aber sehr unfeiner Stil und wenn jemand ein noch etwas größeres Bild nimmt, schon wieder im Eimer.


Zunächst gilt es aber alle anderen Fehlerquellen als "zu groß" auszuschließen. (Zumal das dann wirklich schon nen ganz schön großer Bereich sein müsste. So Fullscreen-Fill oder sowas )


Anmerkung: Witziger weise ist es was die Rekursionstiefe angeht besser für den Algo, wenn die zu füllende Form möglichst komplex ist, mit schön zerklüfteten Rändern. Ein ausgefranstes Tribal-Tatoo z.B. wäre prima . Während ein einfaches Viereck z.B. schlimmstenfalls in einer einzigen Spirale gefüllt würde, was einer Rekursionstiefe von Breite*Höhe des Vierecks in Pixeln entspräche. (Je nach Wahl der Reihenfolge der zu untersuchenden Nachbarpixel, und dem Startpixel. Es kann auch etwas günstiger ausfallen.)

Alles in allem ist Floodfill recht interessant, und weit weniger trivial, als man zunächst annehmen möchte finde ich =). Man kann viel optimieren, verallgemeinern, rumdoktorn - herrlich!