Flood fill

Algorytm Flood Fill

Flood fill to algorytm stosowany w programach graficznych do wypełniania zamkniętych obszarów bitmap kolorem. Wykorzystuje on kolejkę lub stos do realizacji swojego działania.

Parametry Algorytmu

Algorytm wymaga trzech podstawowych parametrów:

• początkowa pozycja
• kolor do zamiany
• nowy kolor

Wariant Rekurencyjny

W wersji rekursywnej algorytm działa w następujący sposób:

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

Alternatywnie, istnieje wersja flood fill8, która uwzględnia osiem kierunków:

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

Wersja Iteracyjna

Aby uniknąć przepełnienia stosu oraz przyspieszyć działanie, można zastosować wersję iteracyjną z użyciem kolejki:

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

Ograniczenia Algorytmu

W praktyce pokazywane algorytmy rzadko są używane ze względu na duże zużycie pamięci oraz wielokrotne sprawdzanie tych samych pikseli, co obniża ich efektywność.

Kategoria

Algorytmy graficzne