Wypełnianie Przez Podtapianie

Wstęp

Wypełnianie przez podtapianie pozwala na zmianę koloru grupy takich samych pikseli np. na obrazku. Jest to bardzo prosty algorytm, ale niestety zużywa bardzo dużo mocy obliczeniowej oraz pamięci komputera. W tym artykule zostanie wyjaśniona jego implementacja.

Algorytm

Algorytm rozpoczyna pracę w dowolnym punkcie (x, y) oraz ma zdefiniowany jaki kolor jest zamieniany na jaki. Jeśli dany punkt jest takiego koloru jak ten, który jest zmieniany to zmieniamy jego kolor, a następnie wykonujemy rekurencyjnie tę operację dla punktów sąsiadujących (zwykle przyjmuje się, że tylko te stykające się krawędzią, ale można też we wszystkich 8 kierunkach). Oto przykładowy obrazek:

Przypuśćmy, że kolorujemy od punktu (3, 2). Zamalowywujemy go i przechodzimy do wywołania tego algorytmu na sąsiadach:

Sąsiedzi są rozpatrywani kolejno w lewo, w górę, w prawo i w dół. W tym przypadku algorytm pomaluje punkt obok na lewo, ale dalej zatrzyma się na ścianie i pozostanie do pomalowania punkt na dole.

Dalej algorytm zacznie przeglądać punkt na prawo i tak rekurencyjnie, aż zostanie uzyskany następujący obrazek:

Złożoność

Algorytm Wypełnianie przez podtapianie nie jest algorytmem optymalnym, ponieważ większość punktów jest sprawdzana wielokrotnie. Pierwsze sprawdzenie następuje w momencie malowania punktu, a następnie ten punkt jest odwiedzany za każdym razem, gdy sąsiad zostanie pomalowany. Podstawowa wersja algorytmu jest rekurencyjna. Oznacza to, że im więcej punktów jest do pokolorowania to zapoptrzebowanie na pamięć znacząco rośnie.

Implementacja

Rekurencja

Poniżej została przedstawiona rekurencyjna wersja algorytmu WypelnijMacierz(), która w zmiennej dane zmianie kolor stary na nowy rozpoczynając zamianę w punkcie (x, y).

1. void WypelnijMacierz(int ** dane, int szer, int wys, int x, int y, int stary, int nowy) {
2.   if (CzyIstnieje(x, y, szer, wys) && dane[y][x] == stary) {
3.     dane[y][x] = nowy;
4.     WypelnijMacierz(dane, szer, wys, x + 1, y, stary, nowy);
5.     WypelnijMacierz(dane, szer, wys, x - 1, y, stary, nowy);
6.     WypelnijMacierz(dane, szer, wys, x, y + 1, stary, nowy);
7.     WypelnijMacierz(dane, szer, wys, x, y - 1, stary, nowy);
8.   }
9. }

Dany punkt malujemy tylko jeśli jego kolor jest odpowiedni i jeśli wogle istnieje, ponieważ jak widać w dalszej części kodu może zostać podany punkt do rozpatrzenia, który niekoniecznie istnieje. Przekazane dane są modyfikowane w miejscu.

Kolejka

Głównym problemem wersji rekurencyjnej jest odkładnie na stos bardzo dużej ilości informacji, dlatego lepszym pomysłem jest utworzenie kolejki na którą będą wrzucane kolejne punkty do zamalowania. Algorytm działa, aż do momentu, gdy kolejka nie jest pusta.

1. void WypelnijMacierz(int ** dane, int szer, int wys, int x, int y, int stary, int nowy) {
2.   queue<Punkt> kolejka;
3.   kolejka.push(UtworzPunkt(x, y));
4.   while (!kolejka.empty()) {
5.     Punkt pkt = kolejka.front();
6.     kolejka.pop();
7.     if (!CzyIstnieje(pkt.x, pkt.y, szer, wys) || dane[pkt.y][pkt.x] != stary)
8.       continue;
9.     dane[pkt.y][pkt.x] = nowy;
10.     kolejka.push(UtworzPunkt(pkt.x + 1, pkt.y));
11.     kolejka.push(UtworzPunkt(pkt.x - 1, pkt.y));
12.     kolejka.push(UtworzPunkt(pkt.x, pkt.y + 1));
13.     kolejka.push(UtworzPunkt(pkt.x, pkt.y - 1));
14.   }
15. }

Wykorzystanie pętli zamiast rekurencji pozytywnie wpływa na czas działania algorytmu, ale niestety nie rozwiązuje problemu z wielokrotnym sprawdzaniem koloru tego samego punktu.

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego fragmentu programu, który dla podanej macierzy danych oraz informacji o zamienianym kolorze wypisze wynik.

1. int main() {
2.   int szer, wys, x, y, stary, nowy;
3.   cout << "Podaj wymiar tablicy\n szer, wys = ";
4.   cin >> szer >> wys;
5.   cout << "Podaj miejsce rozpoczecia\n x, y = ";
6.   cin >> x >> y;
7.   cout << "Podaj zamieniany kolor\n s = ";
8.   cin >> stary;
9.   cout << "Podaj docelowy kolor\n n = ";
10.   cin >> nowy;
11.   cout << "Podaj macierz grafu:\n";
12.   int** dane = new int*[wys];
13.   for (int i = 0; i < wys; i++) {
14.     dane[i] = new int[szer];
15.     for (int j = 0; j < szer; j++) {
16.       cin >> dane[i][j];
17.     }
18.   }
19.   WypelnijMacierz(dane, szer, wys, x, y, stary, nowy);
20.   cout << "Po wypelnieniu:" << endl;
21.   for (int i = 0; i < wys; i++) {
22.     for (int j = 0; j < szer; j++) {
23.       cout << dane[i][j] << " ";
24.     }
25.     cout << endl;
26.   }
27.   system("pause");
28.   return 0;
29. }

Oto przykładowa macierz obrazku:

1. 1 1 1 1 1 0 1 1
2. 1 1 0 0 0 2 0 0
3. 1 0 2 2 2 2 2 0
4. 1 0 2 2 2 2 2 0
5. 1 1 0 2 2 2 0 1
6. 1 1 1 0 0 0 1 1

• Kod źródłowy Rekurencja
• Kod źródłowy Kolejka

Zadania

Zadanie 1

Napisz rekurencyjny algorytm, który będzie zamalowywał sąsiednie pola we wszystkich ośmiu kierunkach (czyli prócz punktów stykających się krawędziami to jeszcze te z którymi tylko rogami). Zastanów się czy taki algorytm jest optymalny. Takim algorytmem będzie możliwa zmiana zmiana koloru obramowania obiektu w przedstawionym w artykule obrazku.

• Kod źródłowy Zadanie 1