In de vorige Pythagoras heb je kunnen lezen hoe je met behulp van iteraties klassieke fractals zoals de Sierpiński driehoek kunt creëren: een herhaling van simpele berekeningen leidt tot een collectie van punten die allemaal samen de fractal vormen. In zijn boek Fractals everywhere uit 1988 legt Michael Barnsley uit waarom deze methode werkt, en bootst hij diverse vertakkende structuren in de natuur na met een fractal. De varen uit dat boek draagt inmiddels zijn naam. Als je het artikel in de vorige Pythagoras helemaal hebt doorgewerkt, heb je als uitsmijter een programmaatje geschreven dat deze varen maakte. Zie figuur 1.

Als je goed kijkt zie je dat deze varen, net als de driehoek en het tapijt van Sierpiński, kan worden overdekt met verkleinde versies van zichzelf. In het geval van de varen zijn deze kleinere versies ook iets vervormd. Om dat goed te zien, tekenen we een rechthoek die de varen bevat (blauw in figuur 2), en overdekken we de varen met behulp van vierhoeken op zo'n manier dat binnen iedere vierhoek een verkleinde versie van de varen te zien is.

Je ziet in figuur 2 dat je met drie vierhoeken en het witte lijnstuk de hele varen in de blauwe vierhoek kunt overdekken. Dat correspondeert met vier transformaties die ieder de grote rechthoek afbeelden op een van de kleinere vierhoeken of op het lijnstuk.

Iteraties

Dit is precies wat Barnsley deed. Hij bedacht vier transformaties die hij gebruikte om de varen in stappen te construeren, uitgaande van een beginpunt. Op basis van de vierhoeken is het duidelijk dat de transformatie die overeenkomt met de bruine rechthoek, meer moet worden gebruikt dan de andere (meer punten!), en dat degene die punten in het witte lijnstuk oplevert maar af en toe nodig is.

Het idee voor de iteratie is eenvoudig. Start met een beginpunt $(x_0, y_0)$ in het vlak en bereken de coördinaten van het volgende punt als functie van die van het huidige punt: $(x_1, y_1) = \left( f_x(x_0,y_0), f_y(x_0,y_0)\right)$, vervolgens $(x_2, y_2) = \left(f_x(x_1,y_1), f_y(x_1,y_1)\right)$, enzovoort. Voor algemene $n \in \mathbb{N}$ kun je dit schrijven als $(x_{n+1}, y_{n+1}) = \left(f_x(x_n,y_n), f_y(x_n,y_n)\right)$.

MatriCes en veCtoren

Voor de varen zijn de functies van de vorm $(x_{n+1}, y_{n+1}) = \left(ax_n + by_n + e, cx_n + dy_n + f\right)$. Ofwel

$x_{n+1}$	$=$	$ax_n+by_n+e$,
$y_{n+1}$	$=$	$cx_n+dy_n+f$.

 

Dit wordt gewoonlijk geschreven met een matrix en vectoren. Een vector

$$\begin{pmatrix}x\\ y\end{pmatrix}$$

kun je opvatten als een pijl die van de oorsprong naar het punt $(x,y)$ wijst. En met een vector

$$\begin{pmatrix}x_n\\y_n\end{pmatrix}$$

kun je bovenstaande berekening voor het volgende punt op een overzichtelijke manier opschrijven met behulp van een matrix-vectorvermenigvuldiging en een vectoroptelling: 

$$\begin{pmatrix}x_{n+1}\\y_{n+1}\end{pmatrix}=\begin{pmatrix}a&b\\c&d\end{pmatrix}\begin{pmatrix}x_n\\y_n\end{pmatrix}+\begin{pmatrix}e\\f\end{pmatrix}.$$

Voor lineaire functies van veel variabelen zijn matrices enorm handig. Ze worden dan ook heel vaak en voor heel veel verschillende toepassingen gebruikt.

Om de varen te creëren is nog iets extra's nodig. Er zijn vier definiërende functies en voor iedere volgende iteratie wordt een van de functies met een bepaalde kans gebruikt:

$f_1(x,y)$	$=$	$\begin{pmatrix}0&0\\0&0{,}16)\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}$	met kans $0{,}01$,
$f_2(x,y)$	$=$	$\begin{pmatrix}0{,}85&0{,}04\\-0{,}04&0{,}85)\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}+\begin{pmatrix}0\\0{,}16\end{pmatrix}$	met kans $0{,}85$,
$f_3(x,y)$	$=$	$\begin{pmatrix}0{,}2&-0{,}26\\0{,}23&0{,}22)\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}+\begin{pmatrix}0\\0{,}16\end{pmatrix}$	met kans $0{,}07$,
$f_4(x,y)$	$=$	$\begin{pmatrix}-0{,}15&0{,}28\\0{,}26&0{,}24)\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}+\begin{pmatrix}0\\1{,}44\end{pmatrix}$	met kans $0{,}07$.

De precieze opbouw van de varen ligt dus niet vast. Maar hoe meer iteraties je gebruikt, hoe meer twee apart gegenereerde varens op elkaar lijken, en in de limiet zijn ze hetzelfde.

Draaien, verkleinen en transleren

Om te begrijpen hoe Barnsley tot zijn transformaties is gekomen, en hoe de varen daarmee wordt opgebouwd, gaan we eerst naar $f_2$ kijken. Begin met een vierkant met hoekpunten $A(0,1)$, $B(1,1)$, $C(1,0)$ en $D(0,0)$. Gebruik $f_2$ om het beeld van dit vierkant te berekenen. Voor punt $A$ geeft dit

$f_2(0,1)$	$=$	$\begin{pmatrix}0{,}85&0{,}04\\-0{,}04&0{,}85\end{pmatrix}\begin{pmatrix}0\\1\end{pmatrix}+\begin{pmatrix}0\\1{,}6\end{pmatrix}$
	$=$	$\begin{pmatrix}0{,}85\cdot0+0{,}04\cdot1\\-0{,}04\cdot0+0{,}85\cdot1\end{pmatrix}+\begin{pmatrix}0\\1{,}6\end{pmatrix}=\begin{pmatrix}0{,}04\\2{,}45\end{pmatrix}$

zodat het beeld van $A$ wordt gegeven door $A'(0{,}04;2{,}45)$. Als eerste valt de translatie op: het punt is duidelijk naar boven geschoven, wat komt doordat bij de $y$-coördinaat uiteindelijk $1{,}6$ opgeteld wordt.

$f_2$ toegepast op het eenheidsvierkant $ABCD$	40 iteraties $f_2$ vanuit het beginpunt $(x_0,y_0)=(0,0)$

Ga na dat de overige hoekpunten worden afgebeeld op $B'(0{,}89;2{,}41)$, $C'(0{,}85;1{,}56)$ en $D'(0;1{,}6)$. Zie figuur 3a. Je kunt nagaan dat de vier punten weer een vierkant vormen, door te controleren dat de zijden even lang zijn en loodrecht op elkaar staan:

$A'D'$	$=$	$\sqrt{(0{,}04-0)^2+(2{,}45-1{,}6)^2}$
	$=$	$\sqrt{0{,}04^2+0{,}85^2}=A'B'=B'C'=C'D'$

De richtingscoëfficiënt van $A'B'$ is $m_1 = -0{,}04/0{,}85$ terwijl die van $B'C'$ gelijk is aan $m_2 = 0{,}85/0{,}04$, zodat $m_1m_2 = -1$ en de zijden loodrecht op elkaar staan. En een vierhoek met vier even lange zijden en een rechte hoek is een vierkant. Dit resulterende vierkant is een factor $s = \sqrt{0{,}04^2 + 0{,}85^2} \approx 0{,}85094$ kleiner dan het oorspronkelijke en is behalve getransleerd ook iets gedraaid ten opzichte van het vierkant $ABCD$. Met de klok mee, en dus over een negatieve hoek. De verschillende transformaties kun je goed zien als je de matrix ontbindt in twee matrices: $S$ voor het schalen met een factor $s$ en $R$ voor de draaiing rond de oorsprong:

$S=\begin{pmatrix}s&0\\0&s\end{pmatrix}$ en $R=\begin{pmatrix}\cos(\theta)&-\sin(\theta)\\\sin(\theta)&\cos(\theta)\end{pmatrix}$.

Deze kunnen worden vermenigvuldigd zoals wordt uitgelegd in het kader. De draaiingshoek $\theta$ kun je uitrekenen in het rechthoekige driehoekje dat $A'$ en $D'$ met de $y$-as vormen: $\theta = -\tan^{-1}(0{,}04/0{,}85) \approx -2{,}69^{\rm o}$. En afgerond kunnen we dus schrijven:

$$f_2(x,y)=\begin{pmatrix}0{,}85094&0\\0&0{,}85094\end{pmatrix}\begin{pmatrix}\cos(-2{,}69^{\rm o})&-\sin(-2{,}69^{\rm o})\\-\sin(-2{,}69^{\rm o})&\cos(-2{,}69^{\rm o})\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}+\begin{pmatrix}0\\0{,}16\end{pmatrix}$$

Hiermee is dus duidelijk dat $f_2$ een object $2{,}69^{\rm o}$ met de klok mee draait rond de oorsprong, verkleint met een factor $0{,}8509$ en in verticale richting transleert over een fstand van $1{,}6$ eenheden.

Opbouw van de nerf

Herhaaldelijk $f_2$ toepassen op het punt $(x_0,y_0) = (0,0)$ levert een ander inzicht op, zie figuur 3b waarin 40 iteraties zijn toegepast. Je ziet de centrale nerf van het varenblad verschijnen. De eerste punten zijn

$(x_1,y_1)$	$=$	$(0; 1{,}6)$
$(x_2,y_2)$	$=$	$(0{,}064; 2{,}96)$
$(x_3,y_3)$	$\approx$	$(0{,}1728; 4{,}1134)$
$(x_4,y_4)$	$\approx$	$(0{,}3114; 5{,}0895)$

Het lijkt een convergent proces en dat is het ook. Het rechterbovenhoekje van de bruine rechthoek in figuur 2 is gelijk aan dat van de blauwe rechthoek. Je kunt uitrekenen dat het ongeveer ligt in het punt $(2{,}258; 9{,}965)$. Dit is het toppuntje van het gecreëerde varenblad. Toepassen van $f_2$ op dit punt geeft precies hetzelfde punt:

$$\begin{pmatrix}0{,}85&0{,}04\\-0{,}04&0{,}85\end{pmatrix}\begin{pmatrix}2{,}265\ldots\\9{,}958\ldots\end{pmatrix}+\begin{pmatrix}0\\1{,}6\end{pmatrix}=\begin{pmatrix}2{,}265\ldots\\9{,}958\ldots\end{pmatrix}.$$

 

		Matrixvermenigvuldiging Een $m\times n$ matrix bestaat uit getallen die georganiseerd zijn in $m$ rijen en $n$ kolommen. Een $2\times 2$ matrix heeft dus $2$ rijen en $2$ kolommen. Twee zulke matrices kun je als volgt vermenigvuldigen: $$\begin{pmatrix}a&b\\c&d\end{pmatrix}\begin{pmatrix}e&f\\g&h\end{pmatrix}=\begin{pmatrix}ae+bg&af+bh\\ce+dg&cf+dh\end{pmatrix}$$ Het resultaat is dus weer een $2\times 2$ matrix. Als beide oorspronkelijke matrices een transformatie voorstellen, is de rechter de eerst toegepaste transformatie en de linker de tweede.

Vullen van de nerf

Zoals te zien is in de lijst van vier functies die tezamen het varenblad genereren, wordt de functie $f_2$ uiteindelijk $85\%$ van de tijd toegepast, dus het vaakst. Uit figuur 2 concludeerden we al dat de functie die het witte lijnstuk geeft het minst vaak nodig is. Deze functie $f_1$ wordt in $1\%$ van de gevallen gebruikt. We bekijken nu wat deze functie doet:

$$f_1(x,y)=\begin{pmatrix}0&0\\0&0{,}16\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}0\\0{,}16y\end{pmatrix}.$$

Dus een punt met coördinaten $(x, y)$ wordt afgebeeld op $(0; 0{,}16y)$. Op basis van een willekeurig punt uit de hierboven gegenereerde rij, bijvoorbeeld $(x_4, y_4) \approx (0{,}3114; 5{,}0895)$ krijgen we met $f_1$ als volgende punt $(x_5, y_5) \approx (0; 0{,}8143)$, een van de punten op het witte lijnstukje uit figuur 2. Als we beginnend met $(0,0)$ een varenblad construeren, zien we dat $f_2$ punten met $y$-coördinaten oplevert die reiken tot ongeveer $y = 10$. Omdat $0{,}16 \cdot 10 = 1{,}6$, geeft $f_1$ punten $(0, y)$ met $0 \lt y \lt 1{,}6$ die de verticale ruimte tussen de punten $(0,0)$ en $(0; 1{,}6)$ vullen: precies het witte lijnstukje uit figuur 2. Met $f_2$ vallen beelden daarvan telkens tussen de punten uit figuur 3b.

Als we dus in $1\%$ van de gevallen $f_1$ toepassen en in $99\%$ van de gevallen $f_2$ krijgen we na heel veel iteraties het plaatje uit figuur 3b, maar dan met de hele centrale nerf getekend.

Het vormen van de zijblaadjes

De functies $f_3$ en $f_4$ worden beide $7\%$ van de keren toegepast. We passen ze allebei toe op het vierkant $ABCD$ uit figuur 3a en zien dat de resulterende vierhoeken geen vierkanten meer zijn, maar parallellogrammen; zie figuur 4. Dat komt overeen met figuur 2, waarin we zagen dat de blauwe rechthoek werd afgebeeld op een niet-rechthoekige gele of paarse vierhoek.

$f_3(ABCD)=A''B''C''D''$ en $f_4(ABCD)=A'''B'''C'''D'''$.

Vergelijkend met figuur 2 zien we dat $f_3$ inderdaad het blad linksonder oplevert: een gedraaide, iets vervormde en verkleinde versie van de gehele varen. Op eenzelfde manier geeft $f_4$ het blad rechtsonder. Hier is ook nog een spiegeling toegepast. Door in Python alle punten die door $f_3$ gegenereerd worden paars te kleuren, alle punten die uit $f_4$ komen rood en alle punten van de stam, verkregen door $f_1$, groen, zie je heel goed dat $f_2$ vervolgens vanuit deze punten de rest als grijze krommen zoals die in figuur 3b construeert. Alle zijbladen boven degene links- en rechtsonder zijn iets verdraaide, verkleinde en verschoven kopieën van de onderste twee.

De varen met $1\%$ groene punten, $85\%$ grijze punten, $7\%$ paarse punten en $7\%$ rode punten, respectievelijk afkomstig van $f_1$, $f_2$, $f_3$ en $f_4$.

In figuur 6 is $f_4$ in zes stappen verdeeld, die ieder horen bij een standaard transformatiematrix. We zien dat er een horizontale afschuiving $h$ (met invariante lijn $y = 0$), een verticale uitrekking $v$ (weer met invariante lijn $y = 0$), een spiegeling in de $y$-as, een verkleining met een factor $\lambda$, een draaiing over een hoek $\alpha$ en een verticale verschuiving over $t = 0{,}44$ plaatsvinden. Hiermee kan $f_4$ worden geschreven als:

$$f_4(x,y)=\begin{pmatrix}\cos(\alpha)&\sin(\alpha)\\-\sin(\alpha)&\cos(\alpha)\end{pmatrix}\begin{pmatrix}\lambda&0\\0&\lambda\end{pmatrix}\begin{pmatrix}-1&0\\0&1\end{pmatrix}\begin{pmatrix}1&0\\0&v\end{pmatrix}\begin{pmatrix}1&h\\0&1\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}+\begin{pmatrix}0\\t\end{pmatrix}.$$

De afbeelding $f_4(ABCD)$ onderverdeeld in stappen. Het rode punt $A$ geeft het traject aan.

Door gebruik te maken van hoeken en afstanden kun je de parameters allemaal uitrekenen. In het bijzonder zijn $\lambda \approx 0{,}300167$ en $\alpha \approx -60{,}02^{\rm o}$, en de vervormingsparameters zijn $h \approx 0{,}226415$ en $v \approx 1{,}20754$.

Op eenzelfde manier kun je $f_3$ ontleden en schrijven als een serie opeenvolgende transformaties.

Als je dit eenmaal weet, kun je ook je eigen varianten creëren. We geven in figuur 7 twee voorbeelden waarin we kleine veranderingen hebben aangebracht. Links is de hoofdnerf veranderd door in $f_2$ een hoek $\theta = -4^{\rm o}$, factor $s = 0{,}85$, en verticale verschuiving over $1{,}8$ toe te passen, zodat het limietpunt valt in $(3{,}89; 9{,}99)$. Rechts is $f_2$ vrijwel hetzelfde, maar met $\theta = -1{,}5^{\rm o}$. Daar is ook $f_4$ veranderd: $h = 0{,}25$, $v = 1{,}25$, $\lambda = 0{,}25$, geen spiegeling, en een draai over $\alpha = -45^{\rm o}$. Het is een leuke uitdaging om op deze manier net als Michael Barnsley te proberen een echt varenblad na te maken.

Twee varianten van Barnsleys varen.