Seed fill (vyplňovací algoritmus) – Java – Fórum – Programujte.com

Čaute, znova a opäť ja. Narazil som dneska na problém ohľadne vyplňovanie farbou. Potrebujem vyplniť strany 3D kocky lenže pri pokuse o vyplnenie mi program vždy spadne. Na internete som študoval veľa kódov podľa ktorých som to písal.

Môj kód

public void flood(int x, int y) {
        
        //Overovanie či X,Y neni za hranicou    
        if (x < 0) return;
        if (y < 0) return;
        if (x >= canvas.getWidth()-1) return;
        if (y >= canvas.getHeight()-1) return;
        
       
        if ((graphic.getPixel(x, y).r==cervena.r) && (graphic.getPixel(x, y).g==cervena.g) && (graphic.getPixel(x, y).b==cervena.b)) return;
        
        graphic.putPixel(x, y, cervena);
        
        flood(x - 1, y);
        flood(x + 1, y);
        flood(x, y - 1);
        flood(x, y + 1);
        return;
        }

Bohužiaľ keď to spustím vypíše mi chybu: Exception in thread "AWT-EventQueue-0" java.lang.StackOverflowError

Myslím že sa jedná o tú rekurziu. Každopádne potrebujem poradiť nejaký algoritmus ktorý by mi to 3D teleso dokázal v rôznych uhloch pohľadu vyfarbiť. Mne osobne už dochádzajú nápady.

Ak máte nejaké nápady budem rád.

#1 Gamecam
Neviem, či to vyrieši tvoj problém, ale z každého bodu nemusíš spúšťať flood() na každom susedovi, ale len na tých, ktorý nie sú červení a nie sú za hranicou. Takže celé toto overovanie posunieš nižšie tak, aby vždy, keď sa tá funkcia spustí, bol si si istý, že môžeš pixel poď tebou vyfarbiť na červeno. 

flood(x,y) {
    vyfarbi(x,y,cervena)
    pre kazdeho suseda {
        ak nie je za hranicou a nie je cerveny {
            flood(susedX, susedY)
        }
    }
}

Teraz sa funckia spustí raz pre každý pixel a nebudeš mať zbytočnú rekurziu.

Ale vzhľadom k tomu, že pixelov je asi veľa, odporúčal by som to robiť bez rekurzie (presne kôli stack overflow). Takže body budeš mať uložené v nejakom stacku a namiesto volania tej funkcie flood() pridáš nový bod do toho stacku. Takto budeš spracovávať body až dokým nebude stack prázdny

flood(x,y) {
stack S
S.pridaj(Bod(x,y))
while (S.velkost > 0) {
	bod = S.navrchu
        vyfarbi(bod, cervena)
	pre kazdeho suseda {
            ak nie je cerveny a nie je za hranicou {
                S.pridaj(Bod(susedX, susedY))
            }
        }
    }
}

#2 lukas.balaz
Skúsil som dať na teba a naprogramoval som to zo zásobníkom. Aktuálne to nehádže error ale vyfarbí iba pár pixelov v okolí (cca 8-9). Myslím že som s toho sedenia pri tom asi niečo prehliadol.

Aktuálne to vyzerá nejak takto

public void flood(int x, int y) 
        {
        Zasobnik zacatek, konec;
        zacatek = null;
        konec = null;
        
        Zasobnik p= new Zasobnik (x,y);
        zacatek = p;
        konec = p;
        
        while (zacatek!=null)
            {
            graphic.putPixel(zacatek.x, zacatek.y, cervena);
            
            if (!graphic.compare(graphic.getPixel(x+1, y), cervena) && !(graphic.compare(graphic.getPixel(x+1, y), farba)))
                {
                p = new Zasobnik (x+1,y);
                konec.dalsi=p;
                konec=p;
                }
            
            if (!graphic.compare(graphic.getPixel(x-1, y), cervena) && !(graphic.compare(graphic.getPixel(x-1, y), farba)))
                {
                p = new Zasobnik (x-1,y);
                konec.dalsi=p;
                konec=p;
                }
            
            if (!graphic.compare(graphic.getPixel(x, y+1), cervena) && !(graphic.compare(graphic.getPixel(x, y+1), farba)))
                {
                p = new Zasobnik (x,y+1);
                konec.dalsi=p;
                konec=p;
                }
            
            if (!graphic.compare(graphic.getPixel(x, y-1), cervena) && !(graphic.compare(graphic.getPixel(x, y-1), farba)))
                {
                p = new Zasobnik (x,y-1);
                konec.dalsi=p;
                konec=p;
                }
            zacatek=zacatek.dalsi;
            }
        }

#3 Gamecam
Nwm teraz presne, skús debugovať a zistiť v každom opakovaní cyklu aký máš stav.
Btw. v jave som nikdy nerobil, takže neviem, ale určite to má obyčajný stack, zbytočne tam používať nejaký linked list či čo to je čo tam používaš.
Okrem toho, kde kontroluješ, či nejdeš za hranicu ?

Jednu chybu už som našiel a to sú špatné súradnice tých pridavaných a porovnávaných bodov, ale po opravení na zaciatok.x a zaciatok.y sa program zacyklí. 

#4 lukas.balaz
Celé plátno mám ohraničené čiarnou farbou takže kontrolujem len či nenačítava černu farbu (farba). 

#6 Gamecam
V podstatě ten první algoritmus je správně, jen ta kostka je asi moc velká a proto to padne na hubu. Někdy pomůže pouhá změna pořadí volání flood tak, aby ty první tři pokusy pokud možno narazily na již obsazené pole. Zkus jen změnit pořadí: 

flood(x - 1, y);
flood(x, y - 1);
flood(x + 1, y);
flood(x, y + 1);

Dále bych tam šetřil volání "cizinců". Místo opakovaného volání 

canvas.getWidth()

by bylo dobré mít tu hodnotu uloženou v lokální proměnné, např. canvasWidth. Totéž s voláním funkce 

graphic.getPixel(x, y)

Je to drahé volání a proto by ses neměl ptát 3×, ale jen jednou. Ideální by bylo injektovat predikát přímo do toho objektu graphic

if (graphic.isPixelColor(x, y, cervena)) {
    return;
}

#7 Kit
No okresal som to ako sa dalo a aj tak to nejde. Došiel som k názoru že algoritmus je správny, pretože na malý objekt cca 100x100 funguje ale pri 200x200 už nie. Otázka je čo teraz. Potrebujem vyfarbiť steny 3D krychle no nenapadá ma nijaká možnosť ako by som to spravil. 

Takže po pár hodinách sedenia pri tom som sa dostal k finálnej verzii algoritmu cez nerekurzivnu možnosť za pomoci zásobníka. Posledná vec čo mi zostáva je zistiť ako vypočítam body použitia algoritmu pre každú s plôch krychle. 

Mám krychlu (napriklad):

Připojen obrázek.

Nejaký nápad ako by som dostal 7 rôznych bodov odkial použijem vyplňovací algoritmus? 

Nerekurzívna verzia vyplnenia:

 public void flood(int x, int y) 
        {
        
        Zasobnik zacatek, konec;
        zacatek = null;
        konec = null;
        
        Zasobnik p= new Zasobnik (x,y);
        zacatek = p;
        konec = p;
        
        while (zacatek!=null)
            {
          if (!graphic.compare(graphic.getPixel(zacatek.x+1, zacatek.y), cervena) && !(graphic.compare(graphic.getPixel(zacatek.x+1, zacatek.y), farba)))
                {
                p = new Zasobnik (zacatek.x+1,zacatek.y);
                konec.dalsi=p;
                konec=p;
                graphic.putPixel(zacatek.x+1, zacatek.y, cervena);
                }
            
            if (!graphic.compare(graphic.getPixel(zacatek.x-1, zacatek.y), cervena) && !(graphic.compare(graphic.getPixel(zacatek.x-1, zacatek.y), farba)))
                {
                p = new Zasobnik (zacatek.x-1,zacatek.y);
                konec.dalsi=p;
                konec=p;
                graphic.putPixel(zacatek.x-1, zacatek.y, cervena);
                }
            
            if (!graphic.compare(graphic.getPixel(zacatek.x, zacatek.y+1), cervena) && !(graphic.compare(graphic.getPixel(zacatek.x, zacatek.y+1), farba)))
                {
                p = new Zasobnik (zacatek.x,zacatek.y+1);
                konec.dalsi=p;
                konec=p;
                graphic.putPixel(zacatek.x, zacatek.y+1, cervena);
                }
            
            if (!graphic.compare(graphic.getPixel(zacatek.x, zacatek.y-1), cervena) && !(graphic.compare(graphic.getPixel(zacatek.x, zacatek.y-1), farba)))
                {
                p = new Zasobnik (zacatek.x,zacatek.y-1);
                konec.dalsi=p;
                konec=p;
                graphic.putPixel(zacatek.x, zacatek.y-1, cervena);
                }
            zacatek=zacatek.dalsi;
            }
        }

#9 Gamecam
Pořád mi není jasné, proč nepoužiješ něco hotového, např:

http://www.java2s.com/Code/Java/2D-Graphics-GUI/Fillapolygon.htm

#10 Kit
V jave profík nie som ale ak sa nepletiem tak tam používa už vstavané funkcie ktoré ten polygon vyfarbia, lenže zadanie našeho semestrálneho projektu je že môžeme použiť kresliace funkcie ktoré sami spravíme. Respektíve ak chcem vykresliť úsečku musím si ju naprogramovať (bresenhamov algoritmus), ak chcem nakresliť krychlu musím si ju naprogramovať ak s ňou chcem točiť tak to isté. Bohužiaľ dokážem robiť len s tým k čomu mám nejaké materiály a aspoň trošku ovládam princíp. Ciže sčítané podtrhnuté musím vymyslieť spôsob ako tú krychlu vyfarbiť a tieńovanie a viditeľnosť hrán ešte bude iný level.... (to ma ešte čaká).

Takže asi tak

#11 Gamecam
Už chápu. Cílem není aplikace, ale výuka.

Ta hromada ifů ve while je zbytečná. Zkus se vrátit k původnímu algoritmu a pouze rekurzi nahradit zásobníkem. Doufám, že smíš použít kolekci. Stačí jeden zásobník - nemusíš jich dělat celou hromadu jak teď.

#12 Kit
Práve že keď som tam tie ifi nemal tak sa program zasekol. S kolekciou som ešte nerobil takže som sa do toho ani nejak nepúšťal. Teraz skôr potrebujem vyriešiť akým spôsobom tú kocku vyfarbím. Najhoršie na tom je že kocka môže rotovať takže nech som bádal ako som bádal nevymyslel som nič čím by som tú kocku na 100% vyfarbil. 

1) Skúšal som rozdeliť kocku na 4 časti a podľa x,y bodov v ktorej časti sa nachádzali som použil vyplňovací algoritmus. Bohužiaľ to sa moc neosvedčilo a dosť často vznikali miesta ktoré sa nevyfarbili, poprípade sa zafarbilo aj plátno.

2) Skúsil som kružnicu vpísať do kocky a následne po celom obvode kružnice vyvolať vyplňovací algoritmus. Bohužiaľ aj tu som sa stretol s pár miestami kam proste kružnica nedočiahne a proste sa nevyplnia.

Aktuálne mi dneska už došli nápady čo by som ešte mohol vyskúšať a už ani google nevyhľadáva žiadne zaujímavé odkazy ktoré by pomohli. Uvidíme, možno sa mi to v noci rozleží v hlave a čosi vymyslím ale ak má niekto nejaký nápad ako by to šlo, bol by som moc rád. 

#13 Gamecam
Zkus jako výchozí bod zadat vždy jeden krok směrem do protějšího rohu každé strany kostky. Budeš mít tedy 4×6 výchozích bodů.

#14 Kit
Ďakujem 1000x, vnukol si mi nápad ktorý fungoval. Spravil som to tak že som upravil čiaru a urobil som myslenú čiaru v každej stene ktorá bola naplnená vyplnovacím algoritmom. za následok to má to že nech je kocka v akomkolvek uhle tak vždy každú plochu nejaká myslená uhlopriečka pretína. Stačilo to dať do kódu. Ďakujem ;)

Zdravím potřeboval bych pomoct s tím to floodfillem neustále se mi zacykluje a dělá jenom 4 sekvence pořád dokola.

public boolean compare(G_Color prvni , G_Color druhy){
        return prvni != druhy;
}
public void floodfill(float [][] bod , G_Color barva ) 
        {
          int x,y;  
          x = (int)bod[0][0];
          y = (int)bod[1][0]; 
        
        G_Color hranice = new G_Color(0, 0, 0);    
            
            
        Zasobnik zacatek, konec;
        zacatek = null;
        konec = null;
        
        Zasobnik p= new Zasobnik (x,y);
        zacatek = p;
        konec = p;
        
        while (zacatek!=null)
            {
               
                if (compare(getPixel(zacatek.x-1, zacatek.y), barva) && (compare(getPixel(zacatek.x-1, zacatek.y), hranice)))
                {
                p = new Zasobnik (zacatek.x-1,zacatek.y);
                konec.dalsi=p;
                konec=p;
                putPixel(zacatek.x-1, zacatek.y, barva);
                                
                }
            
            if (compare(getPixel(zacatek.x+1, zacatek.y), barva) && (compare(getPixel(zacatek.x+1, zacatek.y), hranice)))
                {
                p = new Zasobnik (zacatek.x+1,zacatek.y);
                konec.dalsi=p;
                konec=p;
                putPixel(zacatek.x+1, zacatek.y, barva);
                
                }
            
            if (compare(getPixel(zacatek.x, zacatek.y-1), barva) && (compare(getPixel(zacatek.x, zacatek.y-1), hranice)))
                {
                p = new Zasobnik (zacatek.x,zacatek.y-1);
                konec.dalsi=p;
                konec=p;
                putPixel(zacatek.x, zacatek.y-1, barva);
                
                }
            
            if (compare(getPixel(zacatek.x, zacatek.y+1), barva) && (compare(getPixel(zacatek.x, zacatek.y+1), hranice)))
                {
                p = new Zasobnik (zacatek.x,zacatek.y+1);
                konec.dalsi=p;
                konec=p;
                putPixel(zacatek.x, zacatek.y+1, barva);
               
                }
                 zacatek=zacatek.dalsi;
                }
        }