|
|
void zam_pr(int x,int y,int dl,int sz,char kol)
{int st=320*y+x;
for(int i=1;i<=sz;i++)
memset(0xa000+st+i*320,kol,dl);
}
|
W każdym języku programowania mamy do dyspozycji procedurę wypełniającą zamknięty obszar.
Najprościej oczywiście wypełnić prostokąt. Np w trybie 13h (320x200 256) wpisujemy do pamięci ekranu całe linie.
Wypełnimy obszar nie będący prostokątem, ani wielokątem. Zadanie wypełniania takiego obszaru ma sens wyłącznie kiedy jest ograniczony i spójny. Zakładamy, że brzeg i wnętrze obszaru mają różne kolory. Dopuszczamy wewnątrz figury istnienie "niedostępnych" rejonów.
Rekurencyjny algorytm - to najprostsza metoda wypełniania konturu przez spójność.
void fill_obszar(int x,int y,int kol_w,int kol_b);
{
int c=getColor (x, y);
if ((c!=kol_w) && (c!=kol_b))
{
piksel (x, y, kol_wyp);
fill_obszar(x, y-1, kol_w, kol_b);
fill_obszar(x, y+1, kol_w, kol_b);
fill_obszar(x-1, y, kol_w, kol_b);
fill_obszar(x+1, y, kol_w, kol_b);
}
}
|
Ma on różne nazwy np:"pożar prerii" czy "wypełnianie przez sianie".
Polega ona na rekurencyjnym przeglądaniu otoczenia punktu startowego - ziarna, w czterech
(lub ośmiu) kierunkach. Punkt startowy musi należeć do wnętrza wypełnianego obszaru.
void piksel(Punkt p,int kolor)
{
mapa.setRGB(p.x,p.y,kolor);
}
//--------------------------------------------
void mazek(Punkt p)
{int pom=mapa.getRGB(p.x,p.y);
if(pom!=kolor&&pom!=brzeg)
{
piksel(p,kolor);
stos.na_poczatek(p);
}
}
//--------------------------------------------
void zamaluj(Graphics g,Punkt p)
{Punkt gdzie=new Punkt(0,0);
stos=new Stos( );
mazek(g,p);
while(stos.liczba( )>0)
{
gdzie=stos.zdejmij( );
mazek(g,new Punkt(gdzie.x,gdzie.y+1));
mazek(g,new Punkt(gdzie.x,gdzie.y-1));
mazek(g,new Punkt(gdzie.x+1,gdzie.y));
mazek(g,new Punkt(gdzie.x-1,gdzie.y));
}
}
|
Potrzebne nam będą tylko dwie funkcje: potrafiąca zapalić punkt na ekranie i odczytać kolor punkt z ekranu.
Rekurencyjna implementacje algorytmu, mimo całej elegancji, jest jego główną wadą (łatwo można doprowadzić do przepełnienia stosu). Drugą wadą jest rozrzutność algorytmu objawiająca się wielokrotnym badaniem koloru tego samego piksela. W niektórych przypadkach kolor pojedynczego piksela badany jest nawet pięciokrotnie
Zaimplementuję ten algorytm bez wykorzystania rekurencji, przy
wykorzystaniu struktury listowej (stosu) .
Obserwuj "licznik" : Na stosie.
Daje on świadectwo kosztów pamięciowych tego algorytmu. Algorytm pokazuję jako dobry przykład zastosowania struktur listowych w sytuacji, kiedy muszę zrezygnować z rozwiązania rekurencyjnego i zastąpić je rozwiązaniem iteracyjnym.
Obok w miarę kompletna lista procedur (oczywiście w Javie).
Aplet zrealizowałem wykorzystując struktury opisane w rozdziale "Trochę teorii". Grafika realizowana na mapie bitowej
BufferedImage mapa; ponieważ chodziło o w miarę "proste" odczytanie koloru piksla na ekranie: pom=mapa.getRGB(p.x,p.y);. W praktyce jest pewien drobny problem...
|