Hlavní navigace

Želví grafika a rekurze

7. 8. 2007
Doba čtení: 11 minut

Sdílet

V dalším článku o jazyce Logo si ukážeme, jak použít rekurzi při vytváření obrázků pomocí želví grafiky. Popíšeme si tvorbu křivky a sněhové vločky Helge von Kocha, vykreslení dvou verzí Sierpinského trojúhelníku a nakonec Pythagorova stromu. S rekurzí se mnoho algoritmů dá zapsat elegantně a přitom srozumitelně.

Obsah

1. Podmíněný příkaz typu ifelse a jeho varianty
2. Křivka Helge von Kocha
3. Sněhová vločka Helge von Kocha
4. Sierpinského trojúhelník
5. Odlišná forma Sierpinského trojúhelníku
6. Pythagorův strom
7. Obsah následující části tohoto seriálu

1. Podmíněný příkaz typu ifelse a jeho varianty

V předchozí části tohoto seriálu jsme si popsali a na demonstračních příkladech předvedli podmíněný příkaz typu if. Pomocí tohoto příkazu je možné zapisovat programy, ve kterých se na základě nějaké logické podmínky buď provede nebo naopak neprovede nějaká větev programu, která je v Logu zapsána jako seznam příkazů. V některých programech je však zapotřebí provést (opět na základě logického výrazu) výběr mezi dvěma větvemi, přičemž je vždy provedena pouze jedna větev (nikdy obě současně). I takovéto rozvětvení programu je sice možné zapsat pomocí dvojice příkazů if (druhý příkaz if používá negovaný logický výraz), v praxi je však běžnější využít jazykovou konstrukci typu if-else. Touto konstrukcí, která se někdy označuje jako úplný příkaz if, disponují prakticky všechny vyšší programovací jazyky, samozřejmě včetně Loga.

Příkaz typu ifelse se v mnohém podobá příkazu typu if, ovšem s tím rozdílem, že místo jednoho seznamu příkazů jsou uvedeny dva seznamy. Obsah prvního seznamu příkazů je spuštěn (resp. je interpretován) v případě, že je logický výraz vyhodnocen jako „pravda“ (true), ovšem pokud je výraz vyhodnocen jako „nepravda“ (false), je naopak spuštěn druhý seznam příkazů. Některé interpretery Loga požadují, aby konec prvního seznamu a začátek druhého seznamu byly umístěny na stejném programovém řádku, což také budeme ve všech dále uváděných demonstračních příkladech dodržovat (poznamenejme, že příkaz else, který v Logu také existuje, se používá v jiném kontextu a není ho možné kombinovat s příkazem if). Zápis celé programové konstrukce s podmíněným příkazem ifelse by měl vypadat následovně:

ifelse logický_výraz [
    seznam příkazů větve "true"
][
    seznam příkazů větve "false
] 

2. Křivka Helge von Kocha

Rekurze se spolu s želví grafikou často používá pro vykreslování jednoduchých fraktálů. Bližší informace o fraktálech jsou uvedeny v seriálu Fraktály v počítačové grafice, který taktéž vycházel na Rootu, proto si zde nebudeme uvádět ani teorii fraktálů, ani způsoby jejich vykreslování v jiných programovacích jazycích. Ukážeme si však využití Loga, rekurze a želví grafiky při práci s fraktály známými pod souhrnným názvem L-systémy.

Jedním z nejznámějších fraktálních útvarů, který je možné velmi jednoduše pomocí Loga a jeho želvy vykreslit, je takzvaná křivka Helge von Kocha a sněhová vločka Helge von Kocha. Popišme si nejdříve křivku Helge von Kocha, sněhová vločka vzniká pouhou změnou počátečních podmínek. Vytváření křivky Helge von Kocha spočívá v provedení následujících kroků (nejedná se o popis programu, ale geometrické konstrukce této křivky):

  1. Nejprve se zkonstruuje vodorovná úsečka o zadané délce.
  2. Ve druhém kroku se tato úsečka rozdělí na (stejně dlouhé) třetiny. Prostřední třetina se vyjme a na jejím místě se sestrojí dvě ramena rovnoramenného trojúhelníku. Vznikne tedy obrazec, který se skládá z lomené úsečky (polyčáry), jejíž délka je rovna 4/3 délky původní úsečky, tj. celková délka takto zkonstruované křivky se o třetinu prodlouží.
  3. Na vzniklý obrazec se opakovaně aplikuje pravidlo uvedené v předchozím bodě, tj. každá úsečka je rozdělena na třetiny, prostřední třetina se vyjme a nahradí se dvojicí ramen rovnoramenného trojúhelníka.

logo0701
Obrázek 1: První iterace křivky Helge von Kocha

logo0702
Obrázek 2: Druhá iterace křivky Helge von Kocha

logo0703
Obrázek 3: Třetí iterace křivky Helge von Kocha

logo0704
Obrázek 4: Čtvrtá iterace křivky Helge von Kocha

logo0705
Obrázek 5: Pátá iterace křivky Helge von Kocha

Při implementaci programové procedury, která má pomocí želví grafiky vykreslit Kochovu křivku, se sice budeme řídit výše uvedenými pravidly pro geometrickou konstrukci křivky, vlastní implementace však bude dosti odlišná, protože odebírání částí úseček a náhrada odebraných částí úsečkami novými nejsou operace, které by bylo možné jednoduše provádět.

Zvolíme mnohem elegantnější řešení založené na rekurzi. Základem vznikající procedury bude vykreslení tvaru podobného první iteraci Kochovy křivky, tj. čtyř úseček, z nichž dvě krajní úsečky jsou vodorovné a prostřední úsečky tvoří dvojici ramen rovnostranného trojúhelníku (viz obrázek číslo 1). Tento tvar je možné vykreslit například následující sekvencí příkazů, ve kterých parametr :strana představuje celkovou délku původní (nerozdělené) úsečky:

forward :strana/3
right 60
forward :strana/3
left 120
forward :strana/3
right 60
forward :strana/3 

Každá další iterace křivky Helge von Kocha spočívá v nahrazení všech úseček vzniklých v předchozí iteraci čtyřmi novými úsečkami s třetinovou délkou. Tato úvaha nás povede k vytvoření rekurzivně volané procedury nazvané kochova_krivka, která bude volat sebe samu pro každou vykreslovanou (a v dalších iteracích dělenou) úsečku.

To znamená, že se v předchozím fragmentu kódu nahradí příkaz forward rekurzivním voláním procedury kochova_krivka. Rekurzivní volání této procedury se zastaví ve chvíli, kdy je úsečka rozdělena na část kratší než zadaný limit. V tomto případě je úsečka přímo vykreslena a nedochází k jejímu dalšímu dělení. Test na délku úsečky je jednoduchý, protože se jedná o parametr předávaný proceduře. Pro zachování obecnosti pro různá rozlišení výsledných obrazců bude předáván ještě jeden parametr – délkový limit úsečky. Zdrojový kód procedury kochova_krivka má následující tvar:

to kochova_krivka :strana :limit
    ifelse :strana>:limit [
        kochova_krivka :strana/3 :limit
        left 60
        kochova_krivka :strana/3 :limit
        right 120
        kochova_krivka :strana/3 :limit
        left 60
        kochova_krivka :strana/3 :limit
    ][
        forward :strana
    ]
end 

logo0706
Obrázek 6: Křivka Helge von Kocha vykreslená procedurou kochova_krivka

Výše uvedenou proceduru by bylo možné upravit tak, aby se Kochova křivka vykreslovala pro zadaný počet iterací a ne až do chvíle, kdy je překročen limit délky úsečky. Úprava je velmi jednoduchá – místo parametru limit se bude předávat číslo iterace, které bude postupně klesat k nule. Pokud dosáhne této hodnoty, rekurzivní dělení úsečky se ukončí a úsečka je vykreslena, stejně jako v předchozí proceduře. Celkový počet iterací zadá uživatel při volání procedury kochova_krivka2 jako druhý parametr (prvním je horizontální rozměr obrazce):

to kochova_krivka2 :strana :iterace
    ifelse :iterace>0 [
        kochova_krivka2 :strana/3 :iterace-1
        left 60
        kochova_krivka2 :strana/3 :iterace-1
        right 120
        kochova_krivka2 :strana/3 :iterace-1
        left 60
        kochova_krivka2 :strana/3 :iterace-1
    ][
        forward :strana
    ]
end 

logo0707
Obrázek 7: Pět na sebe navazujících křivek Helge von Kocha vykreslených procedurou kochova_krivka2

Seznam příkazů použitých při vykreslení sedmého obrázku:

; nastavení velikosti kreslicí plochy v Turtle Tracks
(draw 300 300)

; otočení želvy a posun k hornímu okraji kreslicí plochy
right 180
back 300

; smazání kreslicí plochy a skrytí želvy
clean
ht

; pět na sebe navazujících křivek
kochova_krivka2 100 0
kochova_krivka2 100 1
kochova_krivka2 100 2
kochova_krivka2 100 3
kochova_krivka2 100 4 

3. Sněhová vločka Helge von Kocha

Sněhová vločka Helge von Kocha vzniká nepatrnou úpravou počáteční podmínky při generování křivky téhož matematika. Místo jedné úsečky, která se rekurzivně dělí na třetiny, se v případě sněhové vločky začíná s rovnostranným trojúhelníkem, u nějž se v každé iteraci dělí všechny tři strany stejným způsobem. Již po první iteraci je patrný základní tvar vločky, který se v dalších iteracích postupně zjemňuje a zpřesňuje. To je ostatně patrné i z následující pětice ukázkových obrázků:

logo0708
Obrázek 8: První iterace sněhové vločky Helge von Kocha

logo0709
Obrázek 9: Druhá iterace sněhové vločky Helge von Kocha

logo0710
Obrázek 10: Třetí iterace sněhové vločky Helge von Kocha

logo0711
Obrázek 11: Čtvrtá iterace sněhové vločky Helge von Kocha

logo0712
Obrázek 12: Pátá iterace sněhové vločky Helge von Kocha

Implementace konstrukce sněhové vločky Helge von Kocha v Logu je taktéž velmi jednoduchá, protože můžeme použít již naprogramovanou proceduru kochova_krivka či kochova_krivka2. Postačí vytvořit novou proceduru, která třikrát za sebou zavolá proceduru pro vykreslení Kochovy křivky, ovšem pokaždé se želva otočí doprava o 120°, aby vytvořila základní trojúhelník, na kterém je sněhová vločka postavena. Procedura pro vykreslení sněhové vločky může mít například tento tvar:

to kochova_vlocka :strana :iterace
    repeat 3 [
        kochova_krivka2 :strana :iterace
        right 120
    ]
end 

A celý program pro vykreslení sněhové vločky Helge von Kocha v interpreteru Loga Turtle Tracks vypadá následovně:

to kochova_krivka2 :strana :iterace
    ifelse :iterace>0 [
        kochova_krivka2 :strana/3 :iterace-1
        left 60
        kochova_krivka2 :strana/3 :iterace-1
        right 120
        kochova_krivka2 :strana/3 :iterace-1
        left 60
        kochova_krivka2 :strana/3 :iterace-1
    ][
        forward :strana
    ]
end

to kochova_vlocka :strana :iterace
    repeat 3 [
        kochova_krivka2 :strana :iterace
        right 120
    ]
end

; nastavení velikosti kreslicí plochy v Turtle Tracks
(draw 300 300)

; skrytí želvy
ht

; vykreslení pěti iterací sněhové vločky Helge von Kocha
kochova_vlocka 100 5 

logo0713
Obrázek 13: První, druhá a současně čtvrtá iterace sněhové vločky Helge von Kocha (vytvořeno třemi voláními procedury kochova_vlocka bez smazání grafické plochy Loga)

logo0714
Obrázek 14: Pátá iterace sněhové vločky Helge von Kocha vytvořená v předchozím příkladu, pokud došlo k vykreslování křivky dovnitř trojúhelníku (změna příkazu right za left v proceduře kochova_vlocka)

4. Sierpinského trojúhelník

Také Sierpinského trojúhelník patří mezi jeden z nejčastěji zobrazovaných fraktálních útvarů. Možností jeho počítačem řízené konstrukce existuje celá řada, od využití systémů iterovaných funkcí (Iterated Function Systems – IFS) přes speciálně navržené dynamické systémy vytvářené v komplexní rovině až po L-systémy. Vykreslení Sierpinského trojúhelníku v Logu taktéž vede na tvorbu rekurzivně volané procedury. Samotný Sierpinského trojúhelník je totiž definován jako rekurzivní dělení trojúhelníku na menší trojúhelníkové části, vždy s výjimkou prostřední čtvrtiny, která se dále nedělí. První čtyři iterace tohoto objektu jsou vyobrazeny na patnáctém obrázku:

logo0715
Obrázek 15: První čtyři iterace Sierpinského trojúhelníku

Z předchozího obrázku je patrné, jakým způsobem vykreslování probíhá. V každé iteraci se rekurzivně volá procedura pro vykreslení trojúhelníka, tento trojúhelník má však poloviční délku strany a je jinak natočený (to však není, vzhledem k jeho symetrii, patrné). Celé rekurzivní volání je možné zapsat do třikrát opakované programové smyčky, ve které želva postupně zavolá proceduru pro vytvoření „podtrojúhelníku“, vykreslí všechny tři strany a vrátí se do stejného bodu, v jakém vykreslování začala.

V případě, že je překročen zadaný počet iterací, vykreslí se pouze trojúhelník s určenou délkou strany. Pro jeho vykreslování je vytvořena pomocná procedura nazvaná trojuhelnik. Program, který posloužil pro vytvoření patnáctého obrázku, vypadá následovně:

to trojuhelnik :strana
    repeat 3 [
        forward :strana
        left 120
    ]
end

to sierpinski :strana :iterace
    ifelse :iterace>0 [
        repeat 3 [
            sierpinski :strana/2 :iterace-1
            forward :strana
            left 120
        ]
    ][
        trojuhelnik :strana
    ]
end

; nastavení velikosti kreslicí plochy v Turtle Tracks
(draw 300 300)

; smazání grafické plochy, skrytí želvy a natočení do vodorovné polohy
cs
ht
right 90

; přesun želvy na zadanou absolutní pozici (bez kreslení) a následná tvorba Sierpinského trojúhelníku
pu
setpos [-260 0]
pd
sierpinski 250 0

; přesun želvy na zadanou absolutní pozici (bez kreslení) a následná tvorba Sierpinského trojúhelníku
pu
setpos [10 0]
pd
sierpinski 250 1

; přesun želvy na zadanou absolutní pozici (bez kreslení) a následná tvorba Sierpinského trojúhelníku
pu
setpos [-260 -250]
pd
sierpinski 250 2

; přesun želvy na zadanou absolutní pozici (bez kreslení) a následná tvorba Sierpinského trojúhelníku
pu
setpos [10 -250]
pd
sierpinski 250 3 

5. Odlišná forma Sierpinského trojúhelníku

Existuje i odlišná forma Sierpinského trojúhelníku, která je tvořena jedinou lomenou čarou (polyčarou), přičemž úhel napojení sousedních úseček je roven 120° a délka všech úseček tvořících lomenou čaru je shodná. Způsobů vykreslení této formy existuje více, my si ukážeme způsob založený na nepřímé rekurzi, tj. na algoritmu, ve kterém nějaká procedura A volá proceduru B, ve které se rekurzivně volá opět procedura A (ve skutečnosti je v daném algoritmu přítomna i rekurze přímá, tj. procedura A volá jak sama sebe, tak i proceduru B).

Vytvořené procedury mají pro jednoduchost názvy x a y (tyto názvy jsou odvozeny z názvů nonterminálních symbolů v přepisovací gramatice L-systému, to však již zabíháme do podrobností) a výsledný tvar programu pro vykreslení lomené čáry ve tvaru Sierpinského trojúhelníka pro daný počet iterací a délku úseček vypadá takto:

to x :a :iter
    if :iter>0 [
        y :a :iter-1
        forward :a
        left 60
        x :a :iter-1
        forward :a
        left 60
        y :a :iter-1
    ]
end

to y :a :iter
    if :iter>0 [
        x :a :iter-1
        forward :a
        right 60
        y :a :iter-1
        forward :a
        right 60
        x :a :iter-1
    ]
end

(draw 300 300)
y 10 5
forward 10 

logo0716
Obrázek 16: Sierpinského trojúhelník tvořený jednou lomenou čarou (polyčarou)

6. Pythagorův strom

Dalším zajímavým útvarem, který je možné vytvořit pomocí rekurzivně volané procedury, je takzvaný Pythagorův strom (tento termín jsem objevil ve starším vydání časopisu Elektronika, v angličtině pro něj existují i různá pojmenování, například Pythagoras tree nebo Pythagorean tree). Základem Pythagorova stromu je známý domeček kreslený jedním tahem. Pokud považujeme šířku domku a výšku jeho stěn za základní délku, pak mají úhlopříčné tahy délku rovnou odmocnině dvou (sqrt 2) a délka stran střechy je naopak rovná převrácené hodnotě odmocnině dvou (1/sqrt 2).

V proceduře nazvané domek se šířka domku a jeho výška předává v parametru strana. O výpočet druhé odmocniny se stará matematická funkce sqrt s parametrem 2 (i funkce je v Logu zapisována stejně jako procedura, tj. její parametry nemusí být uzavřeny do závorek ani nemusí být odděleny čárkami či jinými oddělovači kromě mezery).

V případě, že se vykreslení každé strany střechy nahradí rekurzivně volanou procedurou pro kreslení celého domečku, získáme charakteristický tvar vzdáleně podobný stromu či keři. Zajímavé je také sledování postupného vykreslování Pythagorova stromu, zejména na pomalejším počítači (Turtle Tracks je sám o sobě dostatečně pomalý interpreter, takže vykreslování pozdrží i na výkonném stroji :-)

Samozřejmě je nutné opět zavést podmínku pro ukončení rekurze, jinak by program skončil běhovou chybou (překročení volné kapacity paměti). Pokud je délka strany pro vykreslení domku menší než deset kroků želvy, je místo domku vykreslena pouze úsečka o této délce, čímž je zajištěno vykreslení střech domků ležících na konci „stromu“. Pokud však délka strany přesahuje tuto hodnotu (deset kroků želvy), je jedním tahem vykreslen celý domek. Výsledný program pro vykreslení Pythagorova stromu má tvar:

to domek :strana
    ifelse :strana>10 [
        ; základna
        forward :strana
        ; úhlopříčka
        left 90+45
        forward :strana*sqrt 2
        ; stěna
        left 90+45
        forward :strana
        ; úhlopříčka
        left 90+45
        forward :strana*sqrt 2
        ; úsečka pod střechou
        left 90+45
        forward :strana
        ; první část střechy
        right 90+45
        domek :strana/sqrt 2
        ; druhá část střechy
        right 90
        domek :strana/sqrt 2
        ; zbývající stěna
        right 45
        forward :strana
        left 90
    ][
        forward :strana
    ]
end

draw
clean
right 90
domek 70 

logo0717
Obrázek 17: Pythagorův strom vytvořený pomocí rekurzivně volané procedury domek

bitcoin_skoleni

logo0718
Obrázek 18: Snížení minimální délky strany domku má vliv na počet rekurzivního volání (zanoření) a tím i „hustoty“ větví

7. Obsah následující části tohoto seriálu

V další části seriálu o programovacím jazyku Logo si vysvětlíme práci s globálními i lokálními proměnnými a ukážeme si jejich použití při psaní složitějších programů.

Autor článku

Vystudoval VUT FIT a v současné době pracuje na projektech vytvářených v jazycích Python a Go.