Strona główna » Algorytmy » Artykuły » Wypełnianie Przez Podtapianie
 

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:

11111011
11000200
10222220
10222220
11022201
11100011

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

11111011
11000200
10232220
10222220
11022201
11100011

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.

11111011
11000200
10332220
10322220
11022201
11100011

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

11111011
11000300
10333330
10333330
11033301
11100011

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

C++C#
Python
  1. def WypelnijMacierz(dane, szer, wys, x, y, stary, nowy):
  2.   if (CzyIstnieje(x, y, szer, wys) and 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.   return dane

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.

C++C#
Python
  1. def WypelnijMacierz(dane, szer, wys, x, y, stary, nowy):
  2.   kolejka = []
  3.   kolejka.append(Punkt(x, y))
  4.   while kolejka:
  5.     pkt = kolejka.pop()
  6.     if (not CzyIstnieje(pkt.x, pkt.y, szer, wys) or dane[pkt.y][pkt.x] != stary):
  7.       continue
  8.     dane[pkt.y][pkt.x] = nowy
  9.     kolejka.append(Punkt(pkt.x + 1, pkt.y))
  10.     kolejka.append(Punkt(pkt.x - 1, pkt.y))
  11.     kolejka.append(Punkt(pkt.x, pkt.y + 1))
  12.     kolejka.append(Punkt(pkt.x, pkt.y - 1))
  13.   return dane

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.

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. stary = int(input("Podaj zamieniany kolor\n s = "))
  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, stary, 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:

  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

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.