Tento text volně navazuje na minulý článek popisující tu nejjednodušší variantu vyplňovacího algoritmu. Nyní se podíváme na jeho vylepšenou formu, která potřebuje cca tisíckrát méně paměti a navíc je rychlejší.
Vtip je v tom, že místo abychom danou oblast vyplňovali pixel po pixelu a do zásobníku ukládali všechny pixely okolo, kreslíme po řádcích a ukládáme si jen určité "důležité" pixely, kterých je mnohonásobně méně.
Budeme potřebovat úplně stejný zásobník jako minule: nějaké pole nebo cokoli, do kterého budeme strkat souřadnice pixelů na obrazovce (např. array[...] of record x,y:integer end) a pak je z něj stylem LIFO (poslední vložený jde ven první) zase vyndavat. Teoreticky by to vlastně LIFO zásobník být nemusel, fungovalo by to i s FIFO frontou, ale LIFO je jednodušší na naprogramování a líp se s ním pracuje.
Vlastní algoritmus pak vypadá takhle:
A to je vše, přátelé.
P.S.: je samozřejmě úplně jedno, jestli budete testovat nejdříve levou stranu a pak pravou nebo naopak. Výše uvedené pořadí bylo zvoleno náhodně.
P.P.S.: je dobré sloučit cykly pro nalezení konce aktuálního řádku a testování řádků nahoře a dole do jednoho (mají stejný index).
P.P.P.S.: když se podmínka "leží pixel uvnitř oblasti a má se vybarvit?" změní z tvaru (barva=původní_barva_oblasti) na tvar (barva<>barva_hranice)and(barva<>barva_kterou_vybarvujeme), změní se tak Plechovka z Paintbrushe na Floodfill z Graph.tpu - barva se přelije přes jakékoli pozadí a zastaví se jedině o zadanou barvu okraje (nebo o barvu, kterou vybarvujeme, aby nevznikla nekonečná smyčka).
Jak je na tom tento algoritmus s rychlostí? O něco lépe než dříve uvedená varianta "bod po bodu do všech stran", protože kreslí celé řádky najednou. Hlavně ale spotřebovává o několik řádů méně paměti: ukládá obvykle méně než 10 bodů na jeden řádek, zatímco předchozí algoritmus by jich potřeboval několik stovek.
Rychlost ale pořád ještě není zrovna špičková. Hlavně proto, že musíme testovat spoustu pixelů (na jednom řádku doleva, doprava a pak to samé o řádek nahoře i dole). První urychlovací zlepšovák, který mě napadl, byl použít místo Getpixelu Getimage, řádky si načíst do paměti celé a testovat je až tam (normální paměť se čte mnohem rychleji než grafická). Jenže zrychlení není moc výrazné a hlavně se tím výrazně zpomalí vyplňování malých oblastí - devadesát Getpixelů je pořád ještě rychlejší než jeden Getimage přes celou šířku obrazovky.