Plechovka čili Floodfill

Algoritmy Grafické Plechovka čili Floodfill

Jak to udělat, aby se barva rozlila od zadaného bodu na obrazovce (nebo obecně v nějakém čtverečkovém rastru) do všech stran a souvisle vyplnila celou libovolně složitou oblast stejné barvy jako měl zadaný bod? Ukážeme si ten asi nejjednodušší způsob, který je sice pomalý a náročný na paměť, ale spolehlivě funguje. Ještě jednodušší by sice bylo použití rekurze, ale ta funguje jen na velmi malé plochy kvůli malé kapacitě systémového zásobníku, proto ji tu uvádět nebudu.

Budeme potřebovat nějaký hodně velký zásobník, do kterého budeme ukládat souřadnice pixelů, které chceme vybarvit. Nejvhodnější konstrukce je pro tento případ asi pole:

array[0..co nejvíc] of record x,y:integer; {nebo jiný typ podle potřeby} end;

Pak si deklarujeme ukazatel na něj a vytvoříme ho jako dynamickou proměnnou (New), aby nám nezabírala místo v data segmentu.

 

Když zásobník, tak potřebujeme ještě procedury pro vkládání a vyjímání dat:

procedure Push(x,y:integer);
procedure Pop(var x,y:integer);

První uloží danou dvojici souřadnic na vrchol zásobníku, druhá vyjme souřadnice z vrcholu zásobníku a předá nám je přes parametry.
Do procedury Push je potřeba zabudovat kontrolu přetečení: když je zásobník plný, aby už se do něj nepokoušela nacpat nic dalšího, nebo ještě lépe, aby vytvořila další zásobník a uložila to do něj (jestli chcete tímto způsobem vyplnit celou obrazovku 640x480, nic jiného vám nezbyde).
Procedura Pop pak nesmí způsobit problémy, pokud se snažíme tahat data z prázdného zásobníku. V takovém případě by měla vrátit nějakou bezpečnou hodnotu (třeba původní zadané výchozí souřadnice) nebo ještě lépe zrušit aktuální prázdný zásobník a pokud existuje nějaký před ním, načíst data z něj.
Ale to už nechám na vás.

 

Máme tedy fungující zásobník, jdeme na vlastní vyplňování:

  1. Někam si uložíme barvu výchozího bodu (dejme tomu do proměnné "Výchozí barva").
  2. Pokud je tato barva rovna barvě, jakou chceme oblast vybarvit, končíme, protože už je hotovo (pokud bychom začali vybarvovat, skončilo by to nekonečnou smyčkou).
  3. Uložíme na zásobník (Push) souřadnice výchozího bodu.
  4. Cyklus:
    1. Vyjmeme ze zásobníku jedny souřadnice (Pop).
    2. Vybarvíme bod na těchto souřadnicích zvolenou barvou.
    3. Podíváme se na body vlevo, vpravo, nahoře a dole od tohoto bodu. Pokud se nacházejí uvnitř rastru (tedy např. neleží mimo obrazovku) a mají barvu rovnou Výchozí barvě (jsou ještě uvnitř zadané souvislé jednobarevné oblasti => mají se vybarvit), uložíme jejich souřadnice na zásobník (Push). Nic jiného s nimi neděláme.
    4. To celé opakujeme tak dlouho, dokud není zásobník úplně prázdný.

 

Na začátku jsme tedy uložili jedny souřadnice. Pak jsme je v prvním průchodu cyklem načetli (zásobník byl tedy na chvíli prázdný), ale hned jsme uložili souřadnice čtyř (možná méně, to je jedno) políček okolo něj. V příštím cyklu jsme přečetli souřadnice jednoho z těchto uložených políček a zase jsme uložili políčka okolo. Tady vidíte, jak rychle se zásobník plní. Plnit se přestane, až dosáhneme hranic oblasti. To se moc políček z okolí vybarvených pixelů neuloží, protože z jedné strany je hranice (barva <> Výchozí barva) a z druhé vybarvená oblast (taky barva <> Výchozí barva). Tak zásobník postupně splaskává a na konci, kdy jsme vyjmuli poslední souřadnice a nevložili jsme žádné, je prázdný, cyklus končí a oblast je v tu chvíli kompletně vyplněna.

Určitě vás praštilo do očí, jak je tenhle algoritmus neefektivní: do zásobníku se dostává spousta duplicitních políček, které pak většinu času jenom kontrolujeme a vyhazujeme. Spotřeba paměti je taky větší, než bychom rádi. V dalším článku si plechovku optimalizujeme.


 

  Aktivity (1)

Článek pro vás napsal Mircosoft
Avatar
Autor je amatérský pascalista, assemblerista a bastlíř. Profesionálně psal nebo píše v HLASM, Rexxu, Cobolu, ST, LAD, FBD, PHP, SQL, JS, Basicu a pár dalších jazycích, které kupodivu stále existují a používají se :-).

Jak se ti líbí článek?
Celkem (2 hlasů) :
3.53.53.53.5 3.5


 


Miniatura
Předchozí článek
Rasterizace úsečky
Miniatura
Všechny články v sekci
Grafické algoritmy
Miniatura
Následující článek
Mandelbrotova množina

 

 

Komentáře

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zatím nikdo nevložil komentář - buď první!