iterativer Floodfill?

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