iterativer Floodfill?

zeropage

Hallo,
ich habe einen rekursiven Floodfill,

        // simple recursive floodfill
	template <typename T> void fillArea(
		T& consl,
		const int x, const int y,
		const console::Dot& ch,
		const int backgroundMode = console::NONE)
	{
		if (x >= 0 && x < consl.screenWidth() && y >= 0 && y < consl.screenHeight())
		{
			const int currCol = consl.getDot(x, y).fColor;
			if (currCol == consl.backgroundDot().fColor) 
			{
				consl.plotDot(x, y, ch, backgroundMode);

				fillArea(consl, x, y + 1, ch, backgroundMode);
				fillArea(consl, x, y - 1, ch, backgroundMode);
				fillArea(consl, x - 1, y, ch, backgroundMode);
				fillArea(consl, x + 1, y, ch, backgroundMode);
			}
		}
	}

analog zu dem Beispiel in wikipedia

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

Ich bekomme recht schnell einen stack overflow, worauf ich hier aber schon hingewiesen wurde.

Nun versuche ich das iterative Beispiel bei wikipedia umzusetzen, schaffe es aber nicht.

wikipedia:

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)

meins:

	// simple iterative floodfill
	template <typename T> void fillArea(
		T& consl,
		const int x, const int y,
		const console::Dot& ch,
		const int backgroundMode = console::NONE)
	{
		std::stack<console::Point<int>> stack; // stack wird erstellt
		stack.push({ x, y }); // erstes Element in stack geschrieben
		while (!stack.empty()) // solange stack nicht leer ist
		{
			stack.pop(); // letztes Element von stack runter, nun ist stack beim ersten start leer
			const int currCol = consl.getDot(x, y).fColor; // aktuelle Farbe an (x, y) holen

			if (currCol == consl.backgroundDot().fColor) // wenn aktuelle Farbe Hintergrundfarbe ist
			{
				consl.plotDot(x, y, ch, backgroundMode); // setze Punkt

				stack.push({ x, y + 1 });
				stack.push({ x, y - 1 });
				stack.push({ x + 1, y });
				stack.push({ x - 1, y }); // 4x stack pushen?
			}
		} // hier fehlt doch noch irgendwas?
	}

Ich kann nicht mal richtig sagen, an welcher Stelle ich es nicht richtig verstehe. Könnt Ihr mir wohl auf die Sprünge helfen?

Swordfish

@zeropage sagte in iterativer Floodfill?:

(x, y) = stack.pop

Sehe ich bei Dir nirgends.

@zeropage sagte in iterativer Floodfill?:

// 4x stack pushen?

Bei 4 Richtungen klingt das garnicht so abwegig?

zeropage

@Swordfish sagte in iterativer Floodfill?:

@zeropage sagte in iterativer Floodfill?:

// 4x stack pushen?

Bei 4 Richtungen klingt das garnicht so abwegig?

Stimmt.

@zeropage sagte in iterativer Floodfill?:

(x, y) = stack.pop

Sehe ich bei Dir nirgends.

Weiß ich nicht, wie ich das umsetzen soll

Swordfish

@zeropage sagte in iterativer Floodfill?:

Weiß ich nicht, wie ich das umsetzen soll

Das oberste Element des Stacks mit stack::top() in x und y speichern bevor Du es mit stack::pop() wegwirfst.

auto [x,y] = stack.top();
stack.pop();

zeropage

Mille Grazie!

Ich werd noch ein wenig rumspielen, evtl kommt noch ne Nachfrage. Aber schon mal Danke

yahendrik

Also ich habe meine Probleme mit diesem Floodfill:

  
  0 1 2 3
0 x x x x
1 x x x x
2 x p x x // hier soll es losgehen
3 x x x x

p setzen (Farbe y), 4 Richtungen pushen

  0 1 2 3
0 x x x x
1 x p x x // dieses p liegt jetzt oben auf dem stack
2 p y p x
3 x p x x

  0 1 2 3
0 x x x x
1 x y x x  // y hier gesetzt, wieder alle 4 Richtungen pushen?
2 p y p x 
3 x p x x

Ich weiß nicht, ob das klar ist (oder ob ich gerade einen groben Denkfehler habe - es ist schon spät...). Wenn der Floodfill auch noch diagonal arbeiten soll, verschärft sich das Problem.

Bei einem „normalen“ Floodfill, bei dem eine Toleranz und ein Alphawert angegeben ist, kann das mMn gar nicht erst funktionieren.

Swordfish

@yahendrik sagte in iterativer Floodfill?:

einen groben Denkfehler

@yahendrik sagte in iterativer Floodfill?:

Farbe y

FARBE y ????

@yahendrik sagte in iterativer Floodfill?:

wieder alle 4 Richtungen pushen?

Ja, weil der Pixel von dem wir zum aktuellen Punkt gekommen sind hat sowieso nicht alteFarbe und wird beim weiteren Abarbeiten ignoriert.

yahendrik

@Swordfish Aber genau das ist doch mein Problem (mal zur Verdeutlichung ebenfalls diagonal):

https://i.ibb.co/fDcBb3V/raster.webp

Wenn die Zielfarbe jetzt nicht opak wäre und die Kombination innerhalb der Toleranz läge, würde alles zigfach beschrieben werden.

Edit: Bei ausreichend großen Zielen wird auch der Speicherverbrauch irgendwann zum Problem.

Edit2: Von der Performance will ich jetzt gar nicht erst reden.

yahendrik

Und hier eine Version, die vorher checkt, ob der Bildpunkt hinzugefügt werden soll:

https://i.ibb.co/sQpgM0K/rasterN.webp

Swordfish

@yahendrik Wo Du Recht hast hast Du Recht. Darf ich mich auch auf "es war schon spät" rausreden?

zeropage

Könnt Ihr mir das Problem näher erläutern? Ich habe ähnlich wie bei dem raster.webp einen "Führungspunkt" und eine Verzögerung hinzugefügt, die bisherigen Tests zeigen nicht, das dieser Punkt trotz gefüllter Fläche noch hin und her springt. Überhaupt springt der gar nicht, sondern zieht ordentlich seinen Bahnen.

Und würde es grundsätzlich an diesem Beispiel eines Floodfill oder an meiner Umsetzung liegen?

yahendrik

@zeropage Das waren alle Punkte, die hinzugefügt wurden. In dem Code sieht das in etwa so aus:

while(!stack.empty()) // solange stack nicht leer ist
{
	// Koordinaten holen
	// pop // letztes Element von stack runter, nun ist stack beim ersten start leer
		
	DWORD currCol=raster.Get(x, y);
	raster.Set(x, y, 0xFFFF00FF);
	anim.Add(d, 50);
	raster.Set(x, y, currCol);

        // Überprüfung

Also alle Punkte, die irgendwann auf den Stack gepusht wurden, werden dargestellt.

Mit den angesprochenen transparenten Farben und einer Toleranz ist es deutlich:

Richtig (etwas umgestellt, damit es nicht so wild aussieht):
https://i.ibb.co/VL5WzgL/raster-alpha-richtig.webp

Falsch (Pixel werden mehrfach beschrieben):
https://i.ibb.co/NpTR4Rq/raster-alpha-falsch.webp

Ersteres kann man zum Beispiel mit einem 2D-Array erreichen:

// Arr2D-Spezialisierung, hat intern einen vector<bool>
Arr2D<bool> bits(width, height);
...
// Nur in Pseudo-Code
while(!stack.empty())
{
  ...
    if(/*Farbe gleich bzw. innerhalb einer Toleranz*/)
    {
    	// oben: nicht bereits in der oberen Zeile
        // und die Koordinaten wurden noch nicht hinzugefügt?
    	if(y>0 && !bits.Get(x, y-1))
    	{
            // den Punkt auf den Stack schieben
    	    stack.push(x, y-1);
            // Punkt im 2D-Array setzen
    	    bits.Set(x, y-1, true);
    	}
        // die anderen Punkte entsprechend
    }
}