kurse:efcomputergrafik:kw38

Wir brauchen zwei neue Konzepte.

  1. Arbeiten mit Zufallszahlen. Arbeitet dazu das Kapitel 3.10 Zufall durch, inkl. der Aufgaben. Kapitel 3 arbeitet mit dem GPanel.
  2. Rekursion. D.h. Funktionen rufen sich selber auf!? Arbeite dazu das Kapitel 2.9 Rekursionen durch, inkl. der Aufgaben. Kapitel 2 arbeitet mit der Turtle.

Bevor wir zu den Fraktalen kommen zwei klassische Aufgaben.

Aufgabe 1

  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 $$
  2. 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} $$
  3. 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?

Click to display ⇲

Click to hide ⇱

$\frac{\sqrt{5}-1}{2}$, d.h. der goldene Schnitt. Schau zu den obigen Aufgaben das folgende YouTube Video an und ergänze…Fibonacci und Memoization

Erstelle jeweils eine rekursive und eine nicht rekursive Version.

Als erstes Fraktal wollen wir das Sierpinski Dreieck berechnen.

Click to display ⇲

Click to hide ⇱

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 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?

Click to display ⇲

Click to hide ⇱

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

(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

  1. Der Schwerpunkt gehört nicht zur Grenzmenge! Wird trotzdem mit diesem Punkt gestartet, so erhalten alle Dreiecke in ihrem Schwerpunkt einen Fehlpunkt.
  2. Wählen wir hingegen einen der drei Fixpunkte als Startpunkt, dann approximieren wir die korrekte Grenzmenge, ohne störende Fehlpixel.
  3. 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.

Click to display ⇲

Click to hide ⇱

Die drei Fixpunkte sind die drei Eckpunkte A, B und C.

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.

Click to display ⇲

Click to hide ⇱

Aufgabe 3

  1. Bestimme die vier Fixpunkte des Barnsley Farns.
  2. Schreibe ein Programm, welches ein Barnsley Farn mit dem Chaos Game erzeugt.
  3. Was machen die einzelnen Abbildungen? Siehe dazu in der KW 39!
  • kurse/efcomputergrafik/kw38.txt
  • Last modified: 2019/09/24 08:52
  • by Marcel Metzler