Problem mit einem rekursivem FloodFill Algorithmus

S

Soltan

Aktives Mitglied
Folgender Code
Code: 
private static void floodFill(int[][] imgArr, int sx, int sy){
    
      
if(sx<0) return;
if(sx>imgArr[sy].length-1) return;
if(sy<0) return;
if(sy>imgArr.length-1) return;
     
        imgArr[sy][sx]=1;

        floodFill(imgArr, sx+1, sy);
        floodFill(imgArr, sx-1, sy);
        floodFill(imgArr, sx, sy+1);
        floodFill(imgArr, sx, sy-1);
    }


Ich verstehe nicht warum bei diesem Code nur eine einzige Zeile mit 1 gefüllt wird. Ich begreife es einfach nicht... kann mir wer helfen ?
 
Hallo.

Du wahrscheinlich läufst in ein Stackoverflow Fehler und nach
Code: 
floodFill(imgArr, sx + 1, sy);
floodFill(imgArr, sx - 1, sy);

Werden die
Java: 
floodFill(imgArr, sx, sy + 1);
floodFill(imgArr, sx, sy - 1);
nie erreicht.

Zudem stimmen deine Abbruchbedingungen nicht.

sx kann auch aus dem Bereich von der länge deines Arrays laufen.

Schau dir nochmal deine Bedingungen an:

Java: 
if(sx<0) return;
if(sx>imgArr[sy].length-1) return;
if(sy<0) return;
if(sy>imgArr.length-1) return;

Grüße
 
Zuletzt bearbeitet:
Dh die 4 rekursiven aufrufe sind falsch angeordnet ? Oder auch inhaltlich nicht so zu verwenden ?
Das mit der Abbruchbedingung stimmt jo, das leuchtet mir ein. Den rekursiven Aufruf mit dem hadere ich noch...
 
Mach' doch mal einen Schreibtischtest. Dann erkennst du das Problem ziemlich schnell. Ich würde dafür aber ein kleines Array nehmen - vielleicht 3x3. Sonst wird's zu aufwändig.
 
Code: 
if(sx<0) return;
        if(sx>imgArr[sy].length-1) return;
        if(sy<0) return;
        if(sy>imgArr.length-1) return;

       
        floodFill(imgArr, sx-1, sy, gVal, gThresh);
        floodFill(imgArr, sx+1, sy, gVal, gThresh);
        floodFill(imgArr, sx, sy-1, gVal, gThresh);
        floodFill(imgArr, sx, sy+1, gVal, gThresh);

Was zum Teufel ist nicht korrekt....
 
Code: 
// Base cases
    if (x < 0 || x >= M || y < 0 || y >= N)
        return;

floodFillUtil(screen, x+1, y, prevC, newC);
    floodFillUtil(screen, x-1, y, prevC, newC);
    floodFillUtil(screen, x, y+1, prevC, newC);
    floodFillUtil(screen, x, y-1, prevC, newC);

code aus nem tutorial....
 
Soltan hat gesagt.:
Java: 
// Base cases
    if (x < 0 || x >= M || y < 0 || y >= N)
        return;

floodFillUtil(screen, x+1, y, prevC, newC);
    floodFillUtil(screen, x-1, y, prevC, newC);
    floodFillUtil(screen, x, y+1, prevC, newC);
    floodFillUtil(screen, x, y-1, prevC, newC);
code aus nem tutorial....
Zum Vergrößern anklicken....
Na ja, wenn das der gesamte Code ist, wird's da wohl auch nicht funktionieren.
Soltan hat gesagt.:
Was zum Teufel ist nicht korrekt....
Zum Vergrößern anklicken....
Warum gehst du der Sache nicht einfach selbst auf den Grund? So lange Tutorials zu durchwühlen, bis du es irgendwann mal richtig abgeschrieben hast, scheint ja keine Zeit zu sparen und vom Lerneffekt bringt's ohnehin nichts.
 
Dude.... ich bin alleine deswegen hier in diesem Forum weil ich mir schon stundenlang den Kopf zerbreche und einfach nicht dahinter komme..... ich habs schon aufgezeichnet alles..... Selbst wenn ich garkeine Abbruchbedinung angebe bekomme ich dasselbe Ergebniss weil es eben nur in dieser einen Zeile hin und her läuft... dachte mir mir kann jemand HELFEN. Wie soll ich ausserdem dahinter kommen ausser zu recherchieren wenn ich selbst nicht draufkomme.....
 
Zuletzt bearbeitet:
Hast du den Schreibtischtest schon gemacht? Dann müsste dir bei den rekursiven Aufrufen eigentlich etwas auffallen. Hier mal die ersten Aufrufe für ein 3x3-Array:
Code: 
floodFill(imgArr, 0, sy);
    floodFill(imgArr, 1, sy);
        floodFill(imgArr, 2, sy);
            floodFill(imgArr, 3, sy);
            floodFill(imgArr, 1, sy);
                floodFill(imgArr, 2, sy);
 
Bei 3 bricht es ab und geht quasi auf 1 zurück..... dann sollte des - kommen.... dann bin ich wieder in diesem Szenario wo es einfach in einer Zeile endlos hin und her springt.... ich bin schon derartig frustriert
 
Ich habe nicht die geringste Ahnung. Wenn danach der Aufruf mit x-1 kommt sollte es eigentlich mit 2 aufgerufen werden und danach wieder mit x+1
 
Ja ok das versteh ich . Tja wir sind dann wieder bei diesem ewigem Szenario wo halt auf der x Achse bis in alle Ewigkeiten hin und her gezeichnet wird.... Im Grunde kann dann jegliche Geschichte die x+1 und x-1 aufeinander folgend hat ( wie in 90% aller Erklärungen) eigentlich nie funktionieren...
 
Soltan hat gesagt.:
// Base cases
if (x < 0 || x >= M || y < 0 || y >= N)
return;

floodFillUtil(screen, x+1, y, prevC, newC);
floodFillUtil(screen, x-1, y, prevC, newC);
floodFillUtil(screen, x, y+1, prevC, newC);
floodFillUtil(screen, x, y-1, prevC, newC);
Zum Vergrößern anklicken....

Code kann niemals stimmen Du rufst die Funktion viel zu oft auf. Der Sinn dieser Rekursion kann immer nur darin bestehen, dass man z.B. bei einem 3x3 Array auch genau 9 Aufrufe der Funktion hat. Z.B.
Code: 
public static void floodFill(int[][] imgArr, int sx, int sy) {
        if (sy > imgArr.length - 1)
            return;
        imgArr[sy][sx] = 1;
        if (sx < imgArr[0].length - 1)
            floodFill(imgArr, sx + 1, sy);
        else
            floodFill(imgArr, 0, sy + 1);
    }
Pro imgArr[sy][sx] = 1; folgt ein floodFill
 
k ich geb auf. Muss mir nen Profi checken der mir das mal wirklich erklären kann. Keine Chance das bis morgen früh jemals zu implementieren. Danke für eure Mühe
 
Soltan hat gesagt.:
k ich geb auf.
Zum Vergrößern anklicken....
Welches Problem ist denn noch übrig?

Die ursprüngliche Frage:
Soltan hat gesagt.:
Ich verstehe nicht warum bei diesem Code nur eine einzige Zeile mit 1 gefüllt wird.
Zum Vergrößern anklicken....
ist doch schon geklärt.

Dass diese:
Soltan hat gesagt.:
( wie in 90% aller Erklärungen)
Zum Vergrößern anklicken....
Erklärungen für dich nicht funktionieren, liegt daran, dass sie sich mit einem anderen Problem beschäftigen.

Und dazu:
Soltan hat gesagt.:
Keine Chance das bis morgen früh jemals zu implementieren.
Zum Vergrößern anklicken....
hat @Blender3D doch schon etwas Konkretes geschrieben.
 
Ich schaffe es einfach nicht einen funktionierenden Code zu implementieren... Blenders befüllt nur die obere Seite des Arrays. Spiel mich schon seit ner Stunde einen Weg zu finden auch die untere zu befüllen.... Ich stoße immer wieder auf das Problem dass sobald ich irgendwo ein x+1 UND ein x-1 stehen habe ich mich im Kreis bewege... dito mit y.
 
Blender3D hat gesagt.:
Code kann niemals stimmen Du rufst die Funktion viel zu oft auf. Der Sinn dieser Rekursion kann immer nur darin bestehen, dass man z.B. bei einem 3x3 Array auch genau 9 Aufrufe der Funktion hat. Z.B.
Code: 
public static void floodFill(int[][] imgArr, int sx, int sy) {
        if (sy > imgArr.length - 1)
            return;
        imgArr[sy][sx] = 1;
        if (sx < imgArr[0].length - 1)
            floodFill(imgArr, sx + 1, sy);
        else
            floodFill(imgArr, 0, sy + 1);
    }
Pro imgArr[sy][sx] = 1; folgt ein floodFill
Zum Vergrößern anklicken....
Das ist kein Floodfill, sondern die rekursive Umsetzung von zwei simplen verschachtelten for-Schleifen...


Soltan hat gesagt.:
Ich schaffe es einfach nicht einen funktionierenden Code zu implementieren... Blenders befüllt nur die obere Seite des Arrays. Spiel mich schon seit ner Stunde einen Weg zu finden auch die untere zu befüllen.... Ich stoße immer wieder auf das Problem dass sobald ich irgendwo ein x+1 UND ein x-1 stehen habe ich mich im Kreis bewege... dito mit y.
Zum Vergrößern anklicken....
Hast du mal versucht, zu verstehen, wie der Algorithmus allgemein fuktioniert, unabhängig von einer genauen Umsetzung in Code?

Im wesentlichen fehlt dir nur ein kleiner Punkt...
 
Das Problem ist dass ich es nicht verstehe. Und jeder fragt mich nur ob ich es verstanden habe. Ich stehe einfach auf der leitung und komme seit mittlerweile ca 7 Stunden keinen einzigen Schritt weiter. Ich hätte das heute um 12 abgeben müssen.
 
Genau und dann erfolgt der rekursive aufruf auf x-1 aber erneut da dies quasi der erste Aufruf ist. Es entsteht ein endloser Aufbau.
 
Zuletzt bearbeitet:
Die Frage war nicht, ob der Aufruf aktuell passiert, sondern ob er, wenn er an dem Feld schon war, erneut erfolgen muss.
 
Nur wenn ich einen x+ aufruf habe niemals einen x-1 aufruf zu haben und umgekehrt. Das ist aber keine Option da ich in beide Richtungen des Arrays gehen muss.
 
Ein rauslaufen ja ! Aber dann terminiert es an den Anfangspunkt zurück und geht nicht in die entgegen gesetzte Richtung auch .....
 
Häh?


Aktuell macht es jeweils dann nicht mit den rekursiven aufrufen weiter, wenn du außerhalb des Bereichs bist.
Du musst es so ergänzen, dass es auch dann nicht die Rekursiven aufrufe ausführt, wenn du an dem Punkt schon mal warst.
 
Code: 
if (sy > imgArr.length - 1) {
        return;
        }
        StdDraw.filledCircle(sx,sy,0.01);
        if (sx < imgArr[0].length - 1)
            floodFill(imgArr, sx + 1, sy);
        else
            floodFill(imgArr, 0, sy - 1);

Das hier ist einfach begrenzt und geht nur in eine Hälfte der ganzen Geschichte. Man kann das eigentlich ganz einfach zusammen fassen. Wir starten sagen wir irgendwo in der Mitte/Mitte des arrays. In dem Moment wo ich auch in die andere Richtung gehen will muss ich auch irgendwo eine Anweisung haben die besagt jetzt bitte in die ANDERE Richtung ( sprich alles was ich irgendwann ins x/y+ gehe muss ich an irgendeiner Stelle auch mal ins - gehen.) Korrekt ?
 
Soltan hat gesagt.:
Code: 
if (sy > imgArr.length - 1) {
        return;
        }
        StdDraw.filledCircle(sx,sy,0.01);
        if (sx < imgArr[0].length - 1)
            floodFill(imgArr, sx + 1, sy);
        else
            floodFill(imgArr, 0, sy - 1);

Das hier ist einfach begrenzt und geht nur in eine Hälfte der ganzen Geschichte. Man kann das eigentlich ganz einfach zusammen fassen. Wir starten sagen wir irgendwo in der Mitte/Mitte des arrays. In dem Moment wo ich auch in die andere Richtung gehen will muss ich auch irgendwo eine Anweisung haben die besagt jetzt bitte in die ANDERE Richtung ( sprich alles was ich irgendwann ins x/y+ gehe muss ich an irgendeiner Stelle auch mal ins - gehen . Korrekt ?
Zum Vergrößern anklicken....
Die Variante hat auch wie gesagt nichts mit Floodfill zu tun.

Und ja, du brauchst die Aufrufe in beide Richtungen. Die hast du richtig und die müssen so bleiben.
Dein Problem ist die Abbruchbedingung.

(So als Tipp: einfach mal bei Wikipedia gucken)
 
Code: 
private static void floodFill(int[][] imgArr, int sx, int sy){
 
   
if(sx<0) return;
if(sx>imgArr[sy].length-1) return;
if(sy<0) return;
if(sy>imgArr.length-1) return;
   
        imgArr[sy][sx]=1;

        floodFill(imgArr, sx+1, sy);
        floodFill(imgArr, sx-1, sy);
        floodFill(imgArr, sx, sy+1);
        floodFill(imgArr, sx, sy-1);
    }

Ich weiß nichteinmal mehr über was für einen Code wir jetzt genau sprechen.
So das war meine ursprünglichste Variante. Es ist alles begrenzt. Es geht in jede Richtung. Da stoßen wir eben ganz genau auf das Problem.
 
Ich könnte sagen wenn das array and der Stelle x y schon 1 ist dann returne auch. Im Falle dieses einfach arrays bsp mit 1 würde das sogar funktionieren, möchtest du auf das hinaus ?
 
K meine aufgabe ist einfach ich klicke auf ein bild und soll alles einfärben was nicht den wert des klicks hat.
Code: 
 if(sx<0) return;
            if(sx>imgArr[sy].length-1) return;
            if(sy<0) return;
            if(sy>imgArr.length-1) return;

            if (imgArr[sy][sx]!=klickWert);
        {
            Draw(sx,sy,0.01);  //Das ist die Einfärbung des Pixels
            floodFill(imgArr, sx + 1, sy,klickWert);
            floodFill(imgArr, sx - 1, sy,klickWert);
            floodFill(imgArr, sx, sy + 1,klickWert);
            floodFill(imgArr, sx, sy - 1,klickWert);
        }
        }

Ich habe es genau so gemacht wie auf Wikipedia.(Bis auf den Rand des Bildes, das haben sie ausgelassen. Aber sollte egal sein) Ist ja eh shcon eine exakte Kopie des Codes. Was passiert ? Dasselbe wie immer.... eine Zeile wird eingefärbt. Ich war noch nie so frustriert in meinem Leben.
 
mrBrown hat gesagt.:
Das ist kein Floodfill, sondern die rekursive Umsetzung von zwei simplen verschachtelten for-Schleifen...
Zum Vergrößern anklicken....
Stimmt ...
Code: 
public static void floodFill(int[][] a, int x, int y, int oldValue, int newValue) {
        int dimX = a.length -1;
        int dimY = a[0].length -1;
        if( x < 0 || y < 0 || x > dimX || y > dimY  )
            return;
        if (a[x][y] == oldValue) {
            a[x][y] = newValue;
            floodFill(a, x, y + 1, oldValue, newValue); // up
            floodFill(a, x, y - 1, oldValue, newValue); // down
            floodFill(a, x - 1, y, oldValue, newValue); // left
            floodFill(a, x + 1, y, oldValue, newValue); // right
        }
        return;
    }
Code: 
public static  void print( int [][] a ) {
      
        for( int i = 0; i < a.length; i++ ) {
            for( int ii = 0; ii < a[0].length; ii++ )
                System.out.print( a[i][ii] +"\t" );
            System.out.println();
        }
    }
Code: 
int[][] a = { { 10, 10, 10, 5 }, { 10, 10, 10, 5 }, { 10, 10, 5, 5 }, { 10, 10, 10, 5 }, { 10, 10, 10, 10 }};
      
        print(a);
        floodFill(a, 2, 1, 10, 3);
        System.out.println("********************");
        print(a);
Hier die Floodfillvariante:
🙄
 
Hoppla.
Code: 
if(sx<0) return;
            if(sx>imgArr[sy].length-1) return;
            if(sy<0) return;
            if(sy>imgArr.length-1) return;

            if (imgArr[sy][sx]==klickWert)
        {
            Draw(sx,sy,0.01);  //Das ist die Einfärbung des Pixels
            floodFill(imgArr, sx + 1, sy,klickWert);
            floodFill(imgArr, sx - 1, sy,klickWert);
            floodFill(imgArr, sx, sy + 1,klickWert);
            floodFill(imgArr, sx, sy - 1,klickWert);
        }
return;
        }

Obs gleich oder nicht gleich ist ändert ja aber nur ob es eben gezeichnet wird wenn es die Farbe ist oder nicht. Aber dass der Durchlauf ganz grundsätzlich nicht funktioniert.... daran ändert es auch nichts 🙁. Funktioniert aber sowieso auf egal welche Variante auch immer nicht auf die Art.
 
Zuletzt bearbeitet:

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Labyrinth mittel FloodFill
Antworten: 1
Opencv Imgproc.floodfill exception
Antworten: 1
Deklaration einer Variablen in einem rekursivem Aufruf
Antworten: 5
toString() methode überschreiben mit rekursivem aufruf.
Antworten: 8
Multiplikation mit rekursivem Aufruf
Antworten: 17

Zurück
Oben