Plechovka turbo aneb Floodfill po riadkoch

Pred nejakou dobou sa tu objavil článok popisujúci tú najjednoduchšiu variantu vyplňovacieho algoritmu. Teraz sa pozrieme na jeho vylepšenú formu, ktorá potrebuje cca tisíckrát menej pamäte a navyše je rýchlejší.

Rozdiel je v tom, že namiesto aby sme danú oblasť vypĺňali pixel po pixeli a do zásobníka ukladali všetky pixely okolo, kreslíme po riadkoch a ukladáme si len určité "dôležité" pixely, ktorých je mnohonásobne menej.

Budeme potrebovať úplne rovnaký zásobník ako minule: nejaké pole alebo čokoľvek, do ktorého budeme strkať súradnice pixelov na obrazovke (napr. Array [...] of record x, y: integer end) a potom je z neho štýlom LIFO (posledný vložený ide von prvá) zase vyberať. Teoreticky by to vlastne LIFO zásobník byť nemusel, fungovalo by to aj s FIFO frontom, ale LIFO je jednoduchšie na naprogramovanie a lepšie sa s ním pracuje.

Vlastné algoritmus potom vyzerá takto:

1. Niekam si uložíme farbu východzieho bodu, nazvime si ju VB (kde táto farba končí, tam končí vypĺňanie oblasť).
2. Ak je táto farba rovná farbe, akú chceme oblasť vyfarbiť, končíme, pretože už je hotovo.
3. Uložíme na zásobník súradnice východiskového bodu.
4. cyklus: Vyberieme zo zásobníka jeden bod (povedzme P):

   Od tohto bodu postupujeme doľava, kým nenarazíme na okraj oblasti:

   Od bodu P postupujeme doprava, kým nenarazíme na okraj oblasti:

   Celý takto nájdený riadok vyfarbíme:

   Nastavíme sa na bod nad bodom P (nazvime ho treba Q). Ak ešte je vnútri vyfarbovaní oblasti, uložíme tento bod na zásobník:

   Od tohto bodu postupujeme doprava až ku koncu vyfarbeného riadku pod ním. Kedykoľvek narazíme na prechod zvonka dovnútra vyfarbovanie oblasti (jeden pixel má farbu inú ako VB a nasledujúce ju má rovnú VB), uložíme si jeho súradnice na zásobník (ukladáme súradnice toho pixelu s farbou VB):

   Od bodu Q postupujeme obdobným spôsobom doľava až k ľavému koncu vyfarbeného riadka:

   Nastavíme sa na bod pod bodom P (napríklad R). Ak ešte je vo vyfarbovaní oblasti, uložíme tento bod na zásobník:

   Postupujeme doprava a doľava obdobne ako pred chvíľou (u bodu Q):

To celé opakujeme tak dlho, kým nie je zásobník úplne prázdny:
...

5. Vyberieme zo zásobníka jeden bod (povedzme P):

6. Od tohto bodu postupujeme doľava, kým nenarazíme na okraj oblasti:

7. Od bodu P postupujeme doprava, kým nenarazíme na okraj oblasti:

8. Celý takto nájdený riadok vyfarbíme:

9. Nastavíme sa na bod nad bodom P (nazvime ho treba Q). Ak ešte je vnútri vyfarbovaní oblasti, uložíme tento bod na zásobník:

10. Od tohto bodu postupujeme doprava až ku koncu vyfarbeného riadku pod ním. Kedykoľvek narazíme na prechod zvonka dovnútra vyfarbovanie oblasti (jeden pixel má farbu inú ako VB a nasledujúce ju má rovnú VB), uložíme si jeho súradnice na zásobník (ukladáme súradnice toho pixelu s farbou VB):

11. Od bodu Q postupujeme obdobným spôsobom doľava až k ľavému koncu vyfarbeného riadka:

12. Nastavíme sa na bod pod bodom P (napríklad R). Ak ešte je vo vyfarbovaní oblasti, uložíme tento bod na zásobník:

13. Postupujeme doprava a doľava obdobne ako pred chvíľou (u bodu Q):

14. To celé opakujeme tak dlho, kým nie je zásobník úplne prázdny:

...

A to je všetko, priatelia.
PS: je samozrejme úplne jedno, či budete testovať najskôr ľavú stranu a potom pravú alebo naopak. Vyššie uvedené poradie bolo zvolené náhodne.
PPS: je dobré zlúčiť cykly pre nájdenie konca aktuálneho riadku a testovanie riadkov hore a dole do jedného (majú rovnaký index).
Kódex PS: keď sa podmienka "leží pixel vnútri oblasti a má sa vyfarbiť?" zmení z tvaru (farba = původní_barva_o­blasti) na tvar (farba <> barva_hranice) and (farba <> barva_kterou_vy­barvujeme), zmení sa tak Plechovka z PAINTBRUSH na Floodfill z Graph.tpu - farba sa preleje cez akékoľvek pozadie a zastaví sa jedine o zadanú farbu okraje (alebo o farbu, ktorú vyfarbujeme, aby nevznikla nekonečná slučka).

Ako je na tom tento algoritmus s rýchlosťou? O niečo lepšie ako predtým uvedená variant "bod po bode do všetkých strán", pretože kreslí celé riadky naraz. Hlavne ale spotrebúva o niekoľko rádov menej pamäte: ukladá zvyčajne menej ako 10 bodov na jeden riadok, zatiaľ čo predchádzajúca algoritmus by ich potreboval niekoľko stoviek.

Rýchlosť ale stále ešte nie je zrovna špičková. Hlavne preto, že musíme testovať veľa pixelov (na jednom riadku doľava, doprava a potom to isté o riadok hore aj dole). Prvý urýchľovací zlepšovák, ktorý ma napadol, bol použiť namiesto Getpixelu getImage, riadky si načítať do pamäte celé a testovať ich až tam (normálny pamäť sa číta oveľa rýchlejšie než grafická). Lenže zrýchlenie nie je moc výrazné a hlavne sa tým výrazne spomalí vyplňovanie malých oblastí - deväťdesiat Getpixelů je stále ešte rýchlejší ako jeden getImage cez celú šírku obrazovky. Takže odporúčam pre začiatok zostať u Getpixelu (ako niekde vyštrachám nejaký ešte vypiplanější a rýchlejší algoritmus (Čo už ale moc pravdepodobné nie je)).