kurse:efcomputergrafik:kw38 [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====KW38: Fraktale mit dem Chaosspiel und über IFS====
Wir brauchen zwei neue Konzepte.
  - Arbeiten mit Zufallszahlen. Arbeitet dazu das Kapitel 3.10 [[http://www.tigerjython.ch/index.php?inhalt_links=navigation.inc.php&inhalt_mitte=grafik/zufall.inc.php|Zufall]] durch, inkl. der Aufgaben. Kapitel 3 arbeitet mit dem GPanel.
  - Rekursion. D.h. Funktionen rufen sich selber auf!? Arbeite dazu das Kapitel 2.9 [[http://www.tigerjython.ch/index.php?inhalt_links=navigation.inc.php&inhalt_mitte=turtle/rekursionen.inc.php|Rekursionen]] durch, inkl. der Aufgaben. Kapitel 2 arbeitet mit der Turtle.

Bevor wir zu den Fraktalen kommen zwei klassische Aufgaben.

**Aufgabe 1**
  - Erstelle eine Funktion $f$, welche die Fakultät $n!$ berechnet. Dabei sei $n\in\mathbb{N}_0$. Zur Erinnerung $$n!=n\cdot (n-1) \cdot \dots \cdot 1, \qquad \text{zudem gilt:} \qquad 0!=1 $$
  - Erstelle eine Funktion $f$, welche die Fibonacci Folge berechnet. Dabei gilt: $$a_1=1, \quad a_2=1, \quad a_3=2, \quad a_4=3, \quad a_5=5, \quad \dots \quad, a_n=a_{n-1}+a_{n-2} $$
  - Erweitere dein Fibonacci Programm, so dass der Quotient $\frac{a_{n}}{a_{n-1}}$ berechnet wird und gibt alle Quotienten von 2 bis n aus. Welcher Zahl wird angestrebt?
<hidden>
$\frac{\sqrt{5}-1}{2}$, d.h. der goldene Schnitt. Schau zu den obigen Aufgaben das folgende YouTube Video an und ergänze...[[https://www.youtube.com/watch?v=Qk0zUZW-U_M&t=352s|Fibonacci und Memoization]]
</hidden>

Erstelle jeweils eine rekursive und eine nicht rekursive Version.

====Sierpinski Dreieck====
Als erstes Fraktal wollen wir das [[https://de.wikipedia.org/wiki/Sierpinski-Dreieck|Sierpinski Dreieck]] //berechnen//.
<hidden>
{{:kurse:efcomputergrafik:sierpinski-dreieck.png?200|}}
</hidden>
===IFS===
IFS steht für Iteriertes Funktionen System, d.h. eine endliche Menge von Funktionen werden immer wieder aufgerufen und ausgeführt. Lest dazu den Artikel von Wikipedia über [[https://de.wikipedia.org/wiki/Iteriertes_Funktionensystem|IFS]], vor allem den Abschnitt Approximation der Grenzmenge.

**Aufgabe 2**

Gegeben sind die drei Eckpunkte $A,B$ und $C$ eines gleichseitigen Dreiecks mit Seitenlänge 100. Wähle als Startpunkt den Flächenschwerpunkt des Dreiecks. $$S(x|y)=\left(\frac{x_1+x_2+x_3}{3}|\frac{y_1+y_2+y_3}{3}\right)$$ Erstelle drei Funktionen $f_A(P_n)$, $f_B(P_n)$ und $f_C(P_n)$. $f_A(P_n)$ erhält als Parameter den letzten Punkt $P_n$. Der nächste Punkt ist dann die Mitte von $P_n$ und der Ecke $A$. Entsprechendes gilt für die Funktionen $f_B$ und $f_C$.

**(a) Chaos Spiel**

Der Befehl **randint(0:2)** liefert zufällig eine der drei Zahlen $\{0,1,2\}$, mit je einer Wahrscheinlichkeit von $\frac{1}{3}$. Wähle damit eine der drei obigen Funktionen aus und setze den berechneten Punkt. Wiederhole diesen Vorgang 10'000 bis 100'000 mal. 

Eine schlanke Version wird ohne die drei Funktionen realisiert. Wie?
<hidden>
<code python sierpinski>
from gturtle import *
from random import randint

makeTurtle()
hideTurtle()

setPos(-200,-200)
right(30)
punkte=[]
# Umrandung und die drei Eckpunkte
for i in range(3):
    punkte.append(getPos())
    forward(400)
    dot(2)
    right(120)
# Startpunkt ist der Schwerpunkt
px=(punkte[0][0]+punkte[1][0]+punkte[2][0])/3
py=(punkte[0][1]+punkte[1][1]+punkte[2][1])/3
#----------------------------------------------
# 100'000 Punkte zeichnen
#----------------------------------------------
for i in range(100000):
    j=randint(0,2)
    px=(px+punkte[j][0])/2
    py=(py+punkte[j][1])/2
    setPos(px,py)
    dot(1)
#----------------------------------------------
# Ende
#----------------------------------------------
print("fertig")
</code>
</hidden>


**(b) Rekursive Version**

Rufe im Hauptprogramm die Funktionen $f_A$, $f_B$ und $f_C$ nacheinander auf, starte dabei mit dem Schwerpunkt. Ergänze die Funktionen so, dass in allen Funktionen alle Funktionen wieder aufgerufen werden, bis zu einer vorgegebenen Rekursionstiefe. Ist diese Rekursionstiefe erreicht, dann soll der entsprechende Punkt gesetzt werden und die Funktion endet. Als Parameter wird immer der neu berechnete Punkt $P_{n+1}$ übergeben.

**Einige Bemerkungen zur Aufgabe**
  - Der Schwerpunkt gehört nicht zur Grenzmenge! Wird trotzdem mit diesem Punkt gestartet, so erhalten alle Dreiecke in ihrem Schwerpunkt einen Fehlpunkt.
  - Wählen wir hingegen einen der drei Fixpunkte als Startpunkt, dann approximieren wir die korrekte Grenzmenge, ohne störende Fehlpixel.
  - Ein Fixpunkt ist ein Punkt, der auf sich selber abgebildet wird, d.h. $$P_{n+1}=f(P_n)=P_n$$ Bestimme die drei Fixpunkte für das Sierpinski Dreieck, wenn die Punkte $A=(x_A|y_A)$, $B=(x_B|y_B)$ und $C=(x_C|y_C)$ sind.

<hidden>
Die drei Fixpunkte sind die drei Eckpunkte A, B und C.
</hidden>  
====Barnsley Farn====
Das IFS für das Barnsley Farn besteht aus vier affinen Abbildungen in der Form:
$$ \vec{x}_{n+1}=A\cdot \vec{x_n}+\vec{b} \quad \Leftrightarrow \quad \left( \begin{array}{c} x_{n+1} \\ y_{n+1} \end{array} \right) = \left( \begin{array}{c c} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right) \cdot \left( \begin{array}{c} x_{n} \\ y_{n} \end{array}\right) + \left( \begin{array}{c} b_x \\ b_y \end{array}\right) 
$$
1. Abbildung: Stiel mit $p=0.02$
$$A_1=\left( \begin{array}{cc} 0 & 0 \\ 0 & 0.16 \end{array} \right) \qquad b_1=\left( \begin{array}{c} 0 \\ 0 \end{array} \right)$$
2. Abbildung: linkes Blatt mit $p=0.1$
$$A_2=\left( \begin{array}{cc} 0.2 & -0.26 \\ 0.23 & 0.22 \end{array} \right) \qquad b_2=\left( \begin{array}{c} 0 \\ 1.6 \end{array} \right)$$
3. Abbildung: rechtes Blatt mit $p=0.1$
$$A_3=\left( \begin{array}{cc} -0.15 & 0.28 \\ 0.26 & 0.24 \end{array} \right) \qquad b_3=\left( \begin{array}{c} 0 \\ 0.44 \end{array} \right)$$
4. Abbildung: Kopiermaschine mit $p=0.78$
$$A_4=\left( \begin{array}{cc} 0.85 & 0.04 \\ -0.04 & 0.85 \end{array} \right) \qquad b_4=\left( \begin{array}{c} 0 \\ 1.6 \end{array} \right)$$

$p$ gibt die Aufrufwahrscheinlichkeit der entsprechenden Abbildung an.

<hidden>
{{:kurse:efcomputergrafik:barnsley-farn-chasegame-4-farbig.png?400|}}
</hidden>


**Aufgabe 3**
  - Bestimme die vier Fixpunkte des Barnsley Farns.
  - Schreibe ein Programm, welches ein Barnsley Farn mit dem Chaos Game erzeugt.
  - Was machen die einzelnen Abbildungen? Siehe dazu in der KW 39!