iterativer Floodfill?



  • 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?



  • @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?



  • @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 😉



  • @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();
    


  • Mille Grazie!

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



  • 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.



  • @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.



  • @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.



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

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



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



  • 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?



  • @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
        }
    }

Log in to reply