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 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:
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 2 | 0 | 0 |
| 1 | 0 | 2 | 2 | 2 | 2 | 2 | 0 |
| 1 | 0 | 2 | 2 | 2 | 2 | 2 | 0 |
| 1 | 1 | 0 | 2 | 2 | 2 | 0 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
Przypuśćmy, że kolorujemy od punktu (3, 2). Zamalowywujemy go i przechodzimy do wywołania tego algorytmu na sąsiadach:
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 2 | 0 | 0 |
| 1 | 0 | 2 | 3 | 2 | 2 | 2 | 0 |
| 1 | 0 | 2 | 2 | 2 | 2 | 2 | 0 |
| 1 | 1 | 0 | 2 | 2 | 2 | 0 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
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.
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 2 | 0 | 0 |
| 1 | 0 | 3 | 3 | 2 | 2 | 2 | 0 |
| 1 | 0 | 3 | 2 | 2 | 2 | 2 | 0 |
| 1 | 1 | 0 | 2 | 2 | 2 | 0 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
Dalej algorytm zacznie przeglądać punkt na prawo i tak rekurencyjnie, aż zostanie uzyskany następujący obrazek:
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 3 | 0 | 0 |
| 1 | 0 | 3 | 3 | 3 | 3 | 3 | 0 |
| 1 | 0 | 3 | 3 | 3 | 3 | 3 | 0 |
| 1 | 1 | 0 | 3 | 3 | 3 | 0 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
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.
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).
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.
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.
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.
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.
Oto przykładowa macierz obrazku:
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.