Seed fill (vyplňovací algoritmus) – Java – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Gamecam
~ Anonymní uživatel
14 příspěvků
12. 11. 2015   #1
-
0
-

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

Nahlásit jako SPAM
IP: 78.128.144.–
Reklama
Reklama
lukas.balaz0
Super člen
12. 11. 2015   #2
-
0
-

#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))
            }
        }
    }
}
Nahlásit jako SPAM
IP: 80.242.41.–
Gamecam
~ Anonymní uživatel
14 příspěvků
12. 11. 2015   #3
-
0
-

#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;
            }
        }
Nahlásit jako SPAM
IP: 78.128.144.–
lukas.balaz0
Super člen
12. 11. 2015   #4
-
0
-

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

Nahlásit jako SPAM
IP: 80.242.41.–
Gamecam
~ Anonymní uživatel
14 příspěvků
12. 11. 2015   #5
-
0
-

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

Nahlásit jako SPAM
IP: 78.128.144.–
Gamecam
~ Anonymní uživatel
14 příspěvků
12. 11. 2015   #6
-
0
-

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

Nahlásit jako SPAM
IP: 78.128.144.–
Kit+11
Guru
12. 11. 2015   #7
-
0
-

#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;
}
Nahlásit jako SPAM
IP: 2a00:1028:83a0:37a6:207:e...–
Komentáře označují místa, kde programátor udělal chybu nebo něco nedodělal.
Gamecam
~ Anonymní uživatel
14 příspěvků
12. 11. 2015   #8
-
0
-

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

Nahlásit jako SPAM
IP: 78.128.144.–
Gamecam
~ Anonymní uživatel
14 příspěvků
12. 11. 2015   #9
-
0
-

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;
            }
        }
Nahlásit jako SPAM
IP: 78.128.144.–
Kit+11
Guru
12. 11. 2015   #10
-
0
-
Nahlásit jako SPAM
IP: 2a00:1028:83a0:37a6:207:e...–
Komentáře označují místa, kde programátor udělal chybu nebo něco nedodělal.
Gamecam
~ Anonymní uživatel
14 příspěvků
12. 11. 2015   #11
-
0
-

#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

Nahlásit jako SPAM
IP: 78.128.144.–
Kit+11
Guru
13. 11. 2015   #12
-
0
-

#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ď.

Nahlásit jako SPAM
IP: 2a00:1028:83a0:37a6:207:e...–
Komentáře označují místa, kde programátor udělal chybu nebo něco nedodělal.
Gamecam
~ Anonymní uživatel
14 příspěvků
13. 11. 2015   #13
-
0
-

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

Nahlásit jako SPAM
IP: 78.128.144.–
Kit+11
Guru
13. 11. 2015   #14
-
0
-

#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ů.

Nahlásit jako SPAM
IP: 2a00:1028:83a0:37a6:207:e...–
Komentáře označují místa, kde programátor udělal chybu nebo něco nedodělal.
Gamecam
~ Anonymní uživatel
14 příspěvků
13. 11. 2015   #15
-
+1
-
Zajímavé
Kit +

#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 ;)

Nahlásit jako SPAM
IP: 78.128.144.–
Thom
~ Anonymní uživatel
3 příspěvky
29. 12. 2015   #16
-
0
-

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

Nahlásit jako SPAM
IP: 91.221.212.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 23 hostů

Podobná vlákna

Seed fill — založil DT

FILL — založil SmokinMon

Algoritmus — založil LuckaH

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý