Plechovka čiže Floodfill
Ako to urobiť, aby sa farba rozliala od zadaného bodu na obrazovke (alebo všeobecne v nejakom štvorčekové rastri) do všetkých strán a súvisle vyplnila celú ľubovoľne zložitú oblasť rovnakej farby ako mal zadaný bod? Ukážeme si ten asi najjednoduchší spôsob, ktorý je síce pomalý a náročný na pamäť, ale spoľahlivo funguje. Ešte jednoduchšie by síce bolo použitie rekurzia, ale tá funguje len na veľmi malé plochy kvôli malej kapacite systémového zásobníka, preto ju tu uvádzať nebudem.
Budeme potrebovať nejaký veľa veľký zásobník, do ktorého budeme ukladať súradnice pixelov, ktoré chceme vyfarbiť. Najvhodnejšie konštrukcia je pre tento prípad asi pole:
array[0..co nejvíc] of record x,y:integer; {nebo jiný typ podle potřeby} end;
Potom si deklarujeme ukazovateľ na neho a vytvoríme ho ako dynamickú premennú (New), aby nám nezaberala miesto v dáta segmente.
Keď zásobník, tak potrebujeme ešte procedúry pre vkladanie a vyberanie dát:
procedure Push(x,y:integer); procedure Pop(var x,y:integer);
Prvý uloží danú dvojicu súradníc na vrchol zásobníka, druhá vyjme
súradnice z vrcholu zásobníka a odovzdá nám je cez parametre.
Do procedúry Push je potreba zabudovať kontrolu pretečeniu: keď je
zásobník plný, aby už sa do neho nepokúšala napchať nič ďalšie, alebo
ešte lepšie, aby vytvorila ďalší zásobník a uložila to do neho (ak
chcete týmto spôsobom vyplniť celú obrazovku 640x480, nič iné vám
neostane).
Procedúra Pop potom nesmie spôsobiť problémy, ak sa snažíme ťahať dáta
z prázdneho zásobníka. V takom prípade by mala vrátiť nejakú bezpečnú
hodnotu (napríklad pôvodné zadanej predvolené súradnice) alebo ešte
lepšie zrušiť aktuálne prázdny zásobník a ak existuje nejaký pred ním,
načítať dáta z neho.
Ale to už nechám na vás.
Máme teda fungujúce zásobník, ideme na vlastné vyplňovanie:
- Niekam si uložíme farbu východzieho bodu (dajme tomu do premennej "Predvolená farba").
- Ak je táto farba rovná farbe, akú chceme oblasť vyfarbiť, končíme, pretože už je hotovo (ak by sme začali vyfarbovať, skončilo by to nekonečnou slučkou).
- Uložíme na zásobník (Push) súradnice východiskového bodu.
- cyklus: Vyberieme zo zásobníka jedny súradnice (Pop).
Vyfarbíme bod na týchto súradniciach zvolenú farbou.
Pozrieme sa na body vľavo, vpravo, hore a dole od tohto bodu. Ak sa nachádzajú vo vnútri rastra (teda napr. Neleží mimo obrazovku) a majú farbu rovno Predvolené farbe (sú ešte vo vnútri zadanej súvislej jednofarebné oblasti => majú so vyfarbiť), uložíme ich súradnice na zásobník (Push). Nič iné s nimi nerobíme.
To celé opakujeme tak dlho, kým nie je zásobník úplne prázdny.
- Vyberieme zo zásobníka jedny súradnice (Pop).
- Vyfarbíme bod na týchto súradniciach zvolenú farbou.
- Pozrieme sa na body vľavo, vpravo, hore a dole od tohto bodu. Ak sa nachádzajú vo vnútri rastra (teda napr. Neleží mimo obrazovku) a majú farbu rovno Predvolené farbe (sú ešte vo vnútri zadanej súvislej jednofarebné oblasti => majú so vyfarbiť), uložíme ich súradnice na zásobník (Push). Nič iné s nimi nerobíme.
- To celé opakujeme tak dlho, kým nie je zásobník úplne prázdny.
Na začiatku sme teda uložili jedny súradnice. Potom sme ich v prvom prechode cyklom načítali (zásobník bol teda na chvíľu prázdny), ale hneď sme uložili súradnice štyroch (možno menej, to je jedno) políčok okolo neho. V budúcom cykle sme prečítali súradnice jedného z týchto uložených políčok a zase sme uložili políčka okolo. Tu vidíte, ako rýchlo sa zásobník plní. Plniť sa prestane, až dosiahneme hraníc oblasti. To sa moc políčok z okolia vyfarbených pixelov neuloží, pretože z jednej strany je hranica (farba <> Predvolené farba) az druhej vyfarbená oblasť (taky farba <> Predvolené farba). Tak zásobník postupne splaskává a na konci, kedy sme vybrali posledné súradnice a nevložili sme žiadne, je prázdny, cyklus končí a oblasť je v tej chvíli kompletne vyplnené.
Určite vás udrelo do očí, ako je tento algoritmus neefektívna: do zásobníka sa dostáva veľa duplicitných políčok, ktoré potom väčšinu času len kontrolujeme a vyhadzujeme. Spotreba pamäte je taky väčšia, než by sme radi. V ďalšom článku si plechovku optimalizujeme.
