Flood fill

Flood fill to algorytm używany np. w programach graficznych do wypełniania zamkniętych obszarów bitmapy kolorem. Korzysta z kolejki lub stosu.

Algorytm potrzebuje trzech parametrów: początkową pozycję, zamieniany kolor i nowy kolor.

Algorytm rekursywny (oparty na stosie):

funkcja flood_fill (pozycja, zamieniany_kolor, nowy_kolor)
{
	jeżeli (kolor_na_pozycji(pozycja) = zamieniany_kolor)
	{
		ustaw_kolor(pozycja, nowy_kolor);
		flood_fill(lewo(pozycja), zamieniany_kolor, nowy_kolor);
		flood_fill(prawo(pozycja), zamieniany_kolor, nowy_kolor);
		flood_fill(góra(pozycja), zamieniany_kolor, nowy_kolor);
		flood_fill(dół(pozycja), zamieniany_kolor, nowy_kolor);
	}
}

Widoczny po prawej stronie obraz ukazuje rzadziej używany algorytm, który „przeskakuje” przez nachylone linie o szerokości jednego piksela.

funkcja flood_fill8 (pozycja,zamieniany_kolor,nowy_kolor)
{
	jeżeli (kolor_na_pozycji(pozycja) = zamieniany_kolor)
	{
		ustaw_kolor(pozycja, nowy_kolor);
		flood_fill(góra(pozycja),zamieniany_kolor,nowy_kolor);
		flood_fill(dół(pozycja),zamieniany_kolor,nowy_kolor);
		flood_fill(lewo(pozycja),zamieniany_kolor,nowy_kolor);
		flood_fill(prawo(pozycja),zamieniany_kolor,nowy_kolor);
		flood_fill(lewo_góra(pozycja),zamieniany_kolor,nowy_kolor);
		flood_fill(lewo_dół(pozycja),zamieniany_kolor,nowy_kolor);
		flood_fill(prawo_góra(pozycja),zamieniany_kolor,nowy_kolor);
		flood_fill(prawo_dół(pozycja),zamieniany_kolor,nowy_kolor);
	}
}

Powyższe algorytmy bardzo szybko mogą spowodować przepełnienie stosu, aby tego uniknąć oraz przyspieszyć działanie algorytmu, zamiast rekurencji wykorzystuje się kolejkę.

funkcja flood_fill (pozycja,zamieniany_kolor,nowy_kolor)
{
       utwórz kolejka;
       kolejka.wstaw(pozycja);
       dopóki(ilość_elementów(kolejka)>0)
       {
               nowa_pozycja = kolejka.ściągnij_element();
               jeżeli (kolor_na_pozycji(nowa_pozycja) = zamieniany_kolor)
               {
                       ustaw_kolor(nowa_pozycja, nowy_kolor);
                       kolejka.wstaw(lewo(nowa_pozycja));
                       kolejka.wstaw(prawo(nowa_pozycja));
                       kolejka.wstaw(góra(nowa_pozycja));
                       kolejka.wstaw(dół(nowa_pozycja));
               }
       }
}

Pokazane algorytmy w praktyce nie są używane, gdyż zajmują wiele pamięci oraz wielokrotnie sprawdzają te same piksele.