Strona główna » Algorytmy » Artykuły » Wypełnianie Po Brzegi
 

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).

11111011
11000400
10222440
10222440
11022401
11100011

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

11111011
11000400
10232440
10222440
11022401
11100011

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

11111011
11000300
10333330
10333330
11033301
11100011

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).

C++C#
Python
  1. def WypelnijMacierz(dane, szer, wys, x, y, obramowanie, nowy):
  2.   if (CzyIstnieje(x, y, szer, wys)
  3.     and dane[y][x] != obramowanie
  4.     and dane[y][x] != nowy):
  5.     dane[y][x] = nowy
  6.     WypelnijMacierz(dane, szer, wys, x + 1, y, obramowanie, nowy)
  7.     WypelnijMacierz(dane, szer, wys, x - 1, y, obramowanie, nowy)
  8.     WypelnijMacierz(dane, szer, wys, x, y + 1, obramowanie, nowy)
  9.     WypelnijMacierz(dane, szer, wys, x, y - 1, obramowanie, nowy)
  10.   return dane

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:

C++C#
Python
  1. szer, wys = [int(x) for x in input("Podaj wymiar tablicy\n szer, wys = ").split()]
  2. x, y = [int(x) for x in input("Podaj miejsce rozpoczęcia\n x, y = ").split()]
  3. obramowanie = int(input("Podaj kolor obramowanie\n obr = "))
  4. nowy = int(input("Podaj docelowy kolor\n n = "))
  5. print("Podaj macierz grafu:\n")
  6. dane = [[] for x in range(wys)]
  7. for i in range(wys):
  8.   dane[i] = [int(x) for x in input().split()]
  9. dane = WypelnijMacierz(dane, szer, wys, x, y, obramowanie, nowy)
  10. print("Po wypełnieniu:");
  11. for i in range(wys):
  12.   for j in range(szer):
  13.     print(dane[i][j], end = " ")
  14.   print()

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

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?

11111011
11000400
10222440
10222440
11022401
11100011

Macierz będzie wyglądać następująco:

33333033
33000300
30333330
30333330
33033303
33300033

Brzegi zamalowywanego obszaru mają dużo "dziur". Nie sprawiają one problemu, gdy algorytm przechodzi jedynie po sąsiednich polach, które stykają się z aktualnym polem krawędzią. W tym przypadku problem należałoby rozwiązać robiąc grubsze obramowanie.