int21h

"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.

Algoritmus je jednoduchý a snadno pochopitelný, ale velice náročný na paměť a výpočetní výkon. Dá se ale optimalizovat - viz dále.

2006-11-30 | Mircosoft
Reklamy:
„Přátelství je součást lidského štěstí.“ Jan Werich