Wypełnianie Po Brzegi

Wstęp

Wypełnianie po brzegi polega na zamalowaniu wszystkich pikseli ograniczone przez pewne obramowanie (lub ograniczone krawędzią obrazu). Do tego potrzebny jest pewien punkt początkowy. Na stronie zostanie wyjaśnione jak napisać i wykorzystać taki algorytm.

Algorytm

Do rozpoczęcia procesu zamalowywania algorytm potrzebuje punktu początkowego (x, y), kolor obramowania oraz docelowy kolor na który zostaną zamalowane piksele. Następnie zamalowywanie piksela polega na sprawdzeniu czy nie jest koloru obramowania lub docelowego i jeśli warunek jest spełniony to jest zamalowywany, a proces jest powtarzany dla wszystkich jego sąsiadów.

Przykład

Przypuśćmy, że dany jest obrazek opisany macierzą opisaną poniżej. Zadanie polega na zamalowaniu wszystkich pikseli ograniczonych wartością 0 na kolor 3 rozpoczynając od punktu (3, 2).

Pierwszy krok polega na zamalowaniu punktu początkowego, a następnie zamalowywaniu kolejnych sąsiadów, sąsiadów sąsiadów.. itd.

Końcowy efekt działania algorytmu wygląda jak poniżej:

Jak można zauważyć obydwa kolory: 2 i 4, które były ograniczone przez czarny kolor 0 zostały zamalowane na ten sam kolor docelowy 3.

Złożoność

Algorytm wypełniania po brzegi działa na podobnej zasadzie jak algorytm wypełnianie przez podtapianie. Wykorzystują rekurencję otrzymuje się algorytm o bardzo wysokiej złożoności. W obu algorytmach ten sam piksel jest odwiedzany wielkokrotnie (choć zamalowany zostaje tylko raz).

Implementacja

Rekurencja

Poniższa funkcja WypelnijMacierz(), która w macierzy dane zamienia wszystkie piksele ograniczone kolor obramowanie na nowy. Algorytm rozpoczyna zamalowywanie od punktu (x, y).

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

Przed pomalowaniem punktu są sprawdzane trzy warunki: czy punkt wogle istnieje, czy kolor jest różny od koloru obramowania oraz docelowego koloru. Jeśli warunek jest spełniony to punkt zostaje pomalowany, a algorytm rekurencyjnie wykonany dla jego sąsiadów.

Testowanie funkcji

Przetestowanie kodu jest możliwe dzięki poniższemu fragmentowi programu:

1. int main() {
2.   int szer, wys, x, y, obr, 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 kolor obramowania\n obr = ";
8.   cin >> obr;
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, obr, 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 podana na początku artykułu:

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

• Kod źródłowy Rekurencja

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) zgodnie z zasadą zamalowywania po brzegi.

Jak będzie wyglądać obrazek po zamalowaniu jeśli wybierzemy dowolne pole prócz wybranego obramowanie o kolorze 0?

• Kod źródłowy Zadanie 1