[all] Rastrove vyplnovani
Potreboval bych nejak polopaticky vysvelit, jak to vlastne funguje. Chapu zcasti princip, ale nejak me to podle skript moc smysl nedava. Davam sem i cast skript, kde se to pise, uci nas to slovak, ale to doufam problem nebude.
Diky za pripadne vysvetleni...
Predpokladajme, že existuje vnútorný bod, z ktorého začíname proces vyplňovania – inicializačný pixel. Problém je vo svojej podstate rekurzívny a dá sa jednoducho sformulovať napr. takto:
Def Vypln(x, y, cin, cout) Ak P(x,y) ≠ cin, a zároveň P(x,y) ≠ cout potom vykonaj kroky 1.—5.
1. P(x,y) = cin
2. Vypln(x-1,y, cin, cout)
3. Vypln(x+1,y, cin, cout)
4. Vypln(x,y-1, cin, cout)
5. Vypln(x,y+1, cin, cout)
Už pri pomerne malých oblastiach je však hĺbka rekurzie tak vysoká, že procedúra je prakticky nepoužiteľná. Preto je nutné zredukovať počet rekurzívnych vnorení napr. tak, že v jednom kroku rekurzie
1. pre stanovený pixel nájdeme na tom istom riadku vnútorný pixel, ktorý je najviac vľavo – prvý vnútorný pixel,
2. od prvého vnútorného pixelu vyplňujeme všetky pixely smerom do prava, až kým nenarazíme na hranicu,
3. pri vyplňovaní každého pixelu zisťujeme, či pixel „pod“ a „nad“ nie sú kritické,
4. kritické pixely uchováme.
Pritom kritický pixel je taký, ktorý súčasne spĺňa nasledujúce tri podmienky:
a) je vnútorný bod oblasti
b) je nevyplnený
c) je „nad“ alebo „pod“ prvým vnútorným pixelom na riadku, alebo vľavo od neho je hraničný pixel, alebo je to inicializačný pixel.
Kroky 1.—4. vykonávame dovtedy, kým existujú kritické pixely. Miera rekurzie v tomto prípade závisí od toho, koľko nových kritických pixelov vzniká pri vyplňovaní jedného riadku.
Skonštruujte situáciu, keď pri vyplňovaní riadku vznikajú 4 kritické pixely.
