Algoritmus vypĺňania vnútorne definovanej oblasti - Záplavový algoritmus (Flood fill Algorithm)
Princíp algoritmu
Na vstupe nech je 4-súvislá oblasť daná všetkými svojimi bodmi s farbou $stara\_farba.$
Na výstupe má byť tá istá oblasť zafarbená farbou nova_farba. Procedúra ešte pozná súradnice jedného vnútorného bodu $(x, y)$ oblasti. Je zrejmé, že ide o tzv. semienkové vypĺňanie. V algoritme sa predpokladá, že hodnoty priradené jednotlivým pixlom sa dajú priamo prečítať z obrazovej pamäte.
Tento algoritmus pracuje na princípe rekurzie. Rekurzia predstavuje využitie časti vlastnej vnútornej štruktúry, najmä definovanie funkcie pomocou seba samej resp. samotná táto funkcia.
Pseudokód
Implementácia rekurzívneho Flood-fill algoritmu pre 4-súvislú oblasť je zhrnutá v nasledovnom zápise.
Na vstupe nech je 4-súvislá oblasť daná všetkými svojimi bodmi s farbou stara_farba.
Na výstupe má byť tá istá oblasť zafarbená farbou nova_farba. Procedúra, ktorá oblasť vyfarbí má okrem farieb ešte súradnice jedného vnútorného bodu oblasti $(x, y)$.
Funkcia zapis_pixel(x, y, color) má tri parametre: súradnice vykresleného bodu rastra a jeho príslušnú farbu. Funkcia nacitaj_pixel(x,y) vráti farbu zadaného pixlu $(x,y)$.
Flood_fill_4(int $x$, int $y$, color stara_farba, color nova_farba) $\lbrace$
If (nacitaj_pixel(x,y) = stara_farba) $\lbrace$
zapis_pixel(x,y,nova_farba);
Flood_fill_4(x,y-1,stara_farba, nova_farba);
Flood_fill_4(x,y+1,stara_farba, nova_farba);
Flood_fill_4(x-1,y,stara_farba, nova_farba);
Flood_fill_4(x+1,y,stara_farba, nova_farba);
$\rbrace$
Tento algoritmus sa obmedzuje síce na 4-súvislú oblasti, ale je jednoducho modifikovateľný pre 8-súvislú oblasť.
Literatúra
Záplavový algoritmus vieme nájsť podrobne spracovaný v literatúre [3] na strane 130. Jeho princíp je aj v [1] na 65. strane.