|
Ein weiteres riesiges Anwendungsgebiet der Rekursion ist die Darstellung von Fraktalen am Computer. Unter diesem Punkt sollen aber nicht wie in Punkt 3.1. einfach rekursive Folgen oder Funktionen dargestellt werden. Vielmehr geht es darum, geometrische Formen nach einer Transformation immer wiederholt darzustellen, sodaß sich ein sinnvolles Gebilde ergibt.
3.4.1 Der fraktale Baum
Der fraktale Baum ist ein recht einfaches, aber sehr schönes Beispiel. Der Baumstamm besteht aus der Grundform des Baumes, einem Fünfeck (Abbildung 1). Der Benützer definiert das Aussehen dieser Grundform durch die Eingabe des Abstandes der Punkte A und B, sowie zweier Faktoren V1 und V2, die das Verhältnis der beiden Höhen H1 und H2 zur Länge des Vektors AB angeben. Nach dem Zeichnen des Stammes werden rekursiv auf der linken und auf der rechten Seite der Spitze des Fünfecks zwei weitere geometrisch ähnliche gezeichnet. Als Grundlage der Berechnungen dienen die Länge des Vektors A'linksB' beziehungsweise A'rechtsB' sowie abermals die Verhältnisse V1 und V2. Aus den Angaben wird ein neues Fünfeck als Ast gezeichnet. Zuerst zeichnet das Programm die linke Seite, wobei es so lange fortfährt, bis die zuvor eingegebene Rekursionstiefe erreicht worden ist. Dann wird der Vorgang abgebrochen, und es werden, stufenweise vom äußersten Ast zurückgehend, auch die rechten Äste gezeichnet.
Abschließend soll noch die Berechnung der einzelnen Punkte erläutert werden: Auf den Vektor AB werden drei Normale aufgestellt , zwei davon in dessen Begrenzungspunkten mit der Länge AB* V1 und eine in dessen Halbierungspunkt mit der Länge AB* V2. Somit erhält man das gewünschte Fünfeck, dessen Äste nun durch einen zweifachen Selbstaufruf der Prozedur mit den Begrenzungspunkten der schrägen Seiten erzeugt werden. Das folgende Programm arbeitet nach dem eben erklärten Prinzip:
program rekursiver_baum;
uses crt, graph, tools07, grtools2;
var s : integer;
v1, v2 : real; {1}
aa, bb : pointtype; {2}
sstufe : integer; {3}
verz : integer; {4}
ch : char;
procedure baum(a, b : pointtype; stufe : integer); {5}
var p : array[1..6] of pointtype; {6}
xd, yd : real; {7}
begin
if stufe>0 then begin {8}
delay(verz); {9}
xd:=b.x-a.x; {10}
yd:=b.y-a.y;
p[1]:=a; {11}
p[2].x:=a.x+round(v1*yd);
p[2].y:=a.y-round(v1*xd);
p[3].x:=a.x+round(xd/2)+round(v2*yd);
p[3].y:=a.y+round(yd/2)-round(v2*xd);
p[4].x:=b.x+round(v1*yd);
p[4].y:=b.y-round(v1*xd);
p[5]:=b;
p[6]:=a;
fillpoly(6,p); {12}
dec(stufe); {13}
baum(p[2],p[3],stufe); {14}
baum(p[3],p[4],stufe); {15}
end;
end;
begin
repeat
clrscr;
writeln(\' REKURSIVER GRAFIKBAUM NACH PROF. HERBERT PAUKERT\');
writeln(\' programmiert von Stefan Krywult für seine Informatikfachbereichsarbeit 1998\');
writeln;
write(\'Baumhöhe (z.B: 30) : \'); {16}
readln(s);
write(\'Seitliches Höhenverhältnis (z.B: 2) : \');
readln(v1);
write(\'mittleres Höhenverhältnis (z.B: 2.5) : \');
readln(v2);
write(\'Rekursionstiefe (am besten zwischen 3 und 12) :\');
readln(sstufe);
write(\'Verzögerung: \');
readln(verz);
graphinit(0,0);
setbkcolor(0);
setcolor(15);
setfillstyle(3,7);
aa.x:=getmaxx div 2; {17}
aa.y:=getmaxy-getmaxy div 4;
bb.x:=aa.x+s;
bb.y:=aa.y;
line(aa.x,aa.y,bb.x,bb.y);
baum(aa,bb,sstufe); {18}
wt;
closegraph;
write(\'Nocheinmal ?\');
ch:=upcase(readkey);
until ch=\'N\';
clrscr;
end.
Zuerst werden die benötigten Variablen deklariert: In v1 und v2 werden die Verhältnisse der Höhen zur Grundlinie in Kommazahlen vom Typ Real gespeichert {1}. Die Variablen aa und bb sind vom Typ PointType, in dem die beiden Koordinaten eines Punktes als ganzzahlige Integerwerte aufbewahrt werden {2}. Sie werden beim Aufruf der rekursiven Prozedur vom Hauptprogramm aus als Startparameter übergeben. Die Variable sstufe bestimmt die Anzahl der Baumverästelungen {3}, und mittels verz kann das Zeichnen des Baumes verzögert werden, um den Vorgang besser beobachten zu können {4}.
Die rekursive Prozedur baum wird mit den Endpunkten der Grundkante des zu zeichnenden Fünfecks in a und b sowie der momentanen Rekursionstiefe in stufe als Parameter aufgerufen {5}. Als lokale Variablen werden das Punktefeld p {6}, in dem das Fünfeck für die Ausgabe gespeichert wird, und die Hilfsvariablen xd und yd vom Fließkommazahlen-Typ Real deklariert {7}.
Zuerst wird in der Prozedur überprüft, ob stufe den Wert 0 hat und die Rekursion somit bereits beendet werden muß{8}. Ist das nicht der Fall, kommen die weiteren Befehle der Prozedur zur Ausführung. Der Programmablauf wird zunächst um die in verz gespeicherte Anzahl von Millisekunden verzögert{9}, dann wird der Vektor von a nach b berechnet und in den Hilfsvariablen xd und yd zwischengespeichert {10}. Mit dessen Hilfe werden die Punkte des Fünfecks nach dem oben erklärten Prinzip berechnet und im Punktefeld p gespeichert {11}, damit das Fünfeck mit dem Befehl FillPoly gezeichnet werden kann {12}. Um das zu ermöglichen, ist es notwendig, einen sechsten Punkt mit den selben Koordinaten wie der erste zu speichern und die Anzahl der Punkte neben dem Punktefeld selbst als Parameter zu übergeben. Nun ist der Ast fertig gezeichnet, und die momentane Rekursionsstufe kann um 1 verringert werden {13}. Und schließlich erfolgt ein zweifacher Selbstaufruf der Prozedur, wobei die Endpunkte der linken {14} und der rechten {15} Seite der Spitze und die neue, verminderte Rekursionstiefe als Argumente übergeben werden.
Im Hauptprogramm werden Baumhöhe, seitliches und mittleres Höhenverhältnis, Rekursionstiefe und die Länge der Verzögerungen zwischen den Zeichenschritten vom Benützer eingegeben {16}. Nach der Initialisierung des Grafikmodus werden die Startpunkte des Baumes aa und bb im Bezug auf die Auflösung berechnet {17}, und schließlich wird die Rekursion mit dem Aufruf der Prozedur baum mit diesen Punkten und der zuvor eingegebenen Rekursionstiefe gestartet {18}.
3.4.2 Die Kochkurve
Die Kochkurve, auch Schneeflockenkurve genannt, wird folgendermaßen gebildet (Abbildunge 2): Eine gegebene Strecke wird in drei gleich lange Teile geteilt. Der mittlere wird herausgelöscht, und es wird über diesem Abschnitt ein gleichseitiges Dreieck konnstruiert, dessen Basiskante auf dem mittleren Streckenstück liegt, die aber nicht gezeichnet wird. Das entstandene Gebilde ist ein Zug aus 4 gleich langen Strecken.
Der eben geschilderte Vorgang wird mit jedem dieser Streckenzüge wiederholt, sodaß nun eine Figur mit 16 gleich langen Strecken entsteht. Die Anzahl der Wiederholungen kann durch die Rekursionstiefe gesteuert werden. Folgendes Programm zeichnet eine Kochkurve:
program koch;
uses crt,graph,tools07,grtools2;
var rektief : integer; {1}i,j,modus : integer;gr,verz : integer; {2}a,b : pointtype; {3}
verzf : real; {4}
procedure frakt(p1,p2:pointtype; rt:integer; f:real); {5}
var p : array[1..6] of tpoint; {6}v : tpoint; {7}
inti : integer;
begin
if (rt=0) or keypressed then exit; {8}
v.x:=(p2.x-p1.x) div 3; {9}
v.y:=(p2.y-p1.y) div 3;
p[1]:=p1; {10}
p[2].x:=p[1].x+v.x;
p[2].y:=p[1].y+v.y;
p[3].x:=p[1].x+round(v.x*3/2 + f*v.y*sqrt(3)/2);
p[3].y:=p[1].y+round(v.y*3/2 - f*v.x*sqrt(3)/2);
p[4].x:=p[1].x+2*v.x;
p[4].y:=p[1].y+2*v.y;
p[5]:=p2;
p[6]:=p1;
if (modus=1) or (rt=1) then begin {11}
line(p[1].x,p[1].y,p[2].x,p[2].y);
line(p[2].x,p[2].y,p[3].x,p[3].y);
line(p[3].x,p[3].y,p[4].x,p[4].y);
line(p[4].x,p[4].y,p[5].x,p[5].y);
delay(verz);
end;
dec(rt); {12}
for inti :=1 to 4 do frakt(p[inti],p[inti+1],rt,f); {13}
end;
begin
clrscr;
writeln(\' Programm zum rekursiven Zeichnen der Kochkurve\');
writeln(\' geschrieben von Stefan Krywult im Rahmen seiner Fachbereichsarbeit \'\'98\');
writeln(\' frei nach einer Vorlage aus dem Skriptum \"FRAKTALE STRUKTUREN\" \');
writeln;
repeat
write(\'Bitte geben Sie die Rekursionstiefe ein (4/6/7 empf.):\'); {14}
readln(rektief);
until rektief>=1;
repeat
write(\'Bitte geben Sie die Verzögerung ein (333/100/10 empf.):\');
readln(verz);
until rektief>=0;
write(\'Bitte geben Sie den Verzerrungsfaktor ein:\');
readln(verzf);
write(\'Bitte geben Sie den Modus ein (1=alle Linien darstellen):\');
readln(modus);
clrscr;
graphinit(0,0); {15}
setcolor(1);
cleardevice;
setcolor(15);
a.x:=mmx div 8; {16}
a.y:=mmy div 2;
b.x:=mmx - a.x;
b.y:=mmy - a.y;
frakt(a, b, rektief, verzf); {17}
wt; {18}
closegraph; {19}
clrscr;
end.
Die wichtigsten Variablen in diesem Programm sind rektief {1} und verz {2}, in denen die vom Benutzer eingegebene Rekursionstiefe bzw. die Verzögerung des Darstellungsprozesses gespeichert wird. In den Variablen a und b vom Typ PointType werden die Endpunkte der ursprünglichen Geraden gespeichert {3}, und verzf speichert einen Verzerrungsfaktor für das Zeichnen der Kurve {4}.
Das Herzstück des Programms, die rekursive Prozedur fakt, berechnet nach dem oben erklärten Verfahren über eine bestimmte Strecke, deren Start- und Endkoordinaten in p1 und p2 übergeben werden, den vierteiligen Streckenzug {5}. Auch ein Verzerrungsfaktor f und die momentane Rekursionstiefe werden der Prozedur übergeben. In der Hilfsvariablen p, die als ein Feld von Punkten deklariert ist, wird der Streckenzug zwischengespeichert {6}. In der PointType-Variable v {7} wird ein Drittel der übergebenen Strecke als Vektor gespeichert, dieser dient als Grundlage für die weiteren Berechnungen {9}. Die Befehle der Prozedur werden aber nur dann ausgeführt, wenn die gewünschte Rekursionstiefe noch nicht erreicht, d.h. rt größer 0 ist und keine Taste gedrückt wurde {8}. Nach dem Aufstellen des Vektors v {9} folgt die Berechnung der einzelnen Punkte {10}. Der erste besitzt die selben Koordinaten wie der übergebene Startpunkt der Strecke, der letzte die selben wie deren Endpunkt. Den zweiten und den vorletzten Punkt des Streckenzuges erhält man durch die Addition von v bzw. dem Doppelten von v zum ersten Punkt. Der mittlere Punkt wird errechnet, indem eine Normale mit der Länge v* 3/2 durch den Mittelpunkt der gegebenen Strecke (p1+v*3/2) aufgestellt wird.
Hat der Benutzer 1 als Zeichenmodus eingegeben, wird der Streckenzug bei jedem Prozeduraufruf gezeichnet, sonst nur beim letzten (rt=1) {11}. Nach dem Verringern der momentanen Rekursionstiefe rt um 1 {12} erfolgt in einer Schleife ein vierfacher Selbstaufruf, bei dem die Koordinaten je eines der vier Streckenstücke als Parameter übergeben werden. {13}.
Das Hauptprogramm beschränkt sich auf die Eingabe der Rekursionstiefe, der Verzögerung zwischen den Darstellungsschritten und des Verzerrungsfaktors {14}. Danach wird der Grafikmodus initialisiert {15}, eine bildfüllende Strecke in Abhängigkeit zur Auflösung errechnet {16}. Schließlich wird die rekursive Prozedur frakt mit den entsprechenden Parametern aufgerufen {17}.
Nach dem Zeichnen der Kochkurve wartet das Programm auf einen Tastendruck {18} und schaltet zurück in den Textmodus {19}.
3.4.3 Die Sierpinsky-Dreiecke
Das Sierpinsky Dreieck entsteht, wenn die Halbierungspunkte der drei Seiten eines gleichseitigen Dreiecks so mit einander verbunden werden, daß vier Dreiecke entstehen. Mit den drei äußeren Dreiecken verfährt man dann nach dem selben Prinzip. Der ganze Vorgang wird so lange fortgesetzt, bis die gewünschte Rekursionstiefe erreicht ist (siehe Abbildung 3).
program sierpins;
uses crt,graph,tools07, grtools2;
var rektief : integer;
gr,verz : integer;
i,j,farbe : integer;
procedure frakt(rt,p1x,p1y,p2x,p2y,p3x,p3y:integer);
begin
if not keypressed then begin
if rt>1 then begin
frakt(rt-1,(p1x+p3x) div 2,(p1y+p3y) div 2,(p1x+p2x) div 2,(p1y+p2y) div 2,p1x,p1y);
frakt(rt-1,(p1x+p2x) div 2,(p1y+p2y) div 2,(p2x+p3x) div 2,(p2y+p3y) div 2,p2x,p2y);
frakt(rt-1,(p2x+p3x) div 2,(p2y+p3y) div 2,(p1x+p3x) div 2,(p1y+p3y) div 2,p3x,p3y);
end;
if farbe=1 then setcolor(rt mod 8+8);
delay(verz);
line(p1x,p1y,p2x,p2y);
line(p2x,p2y,p3x,p3y);
line(p3x,p3y,p1x,p1y);
end;
end;
begin
clrscr;
writeln(\' Programm zum rekursiven Zeichnen der SIERPINSKY-DREIECKE\');
writeln(\' geschrieben von Stefan Krywult im Rahmen seiner Fachbereichsarbeit \'\'98\');
writeln;
write(\'Bitte geben Sie die Rekursionstiefe ein (6/7 empf.):\');
readln(rektief);
write(\'Bitte geben Sie die Verzögerung ein: (100/10 empf.):\');
readln(verz);
write(\'Farbdarstellung ? (1=Farbe) :\');
readln(farbe);
clrscr;
graphinit(0,0);
cleardevice;
setcolor(mmc);
frakt(rektief,0,0,mmx,0,mmx div 2,mmy);
wt;
closegraph;
clrscr;
end.
Als globale Variablen werden wieder rektief und verz zum Speichern der eingegeben Rekursionstiefe und der Verzögerung verwendet. Die Variable farbe ist ein Flag, in dem festgehalten wird, ob der Benützer eine Darstellung mit verschiedenen Farben wünscht {1}. Die rekursive Prozedur frakt benötigt als Parameter die momentane Rekursionstiefe rt und die Koordinaten der Eckpunkte des Dreiecks {2}. Die Deklaration lokaler Variablen ist diesmal nicht notwendig. Auch die Befehle dieser Prozedur werden nur dann ausgeführt, wenn keine Taste gedrückt wurde {3}, was einen sofortigen Abbruch des Zeichenvorganges durch einen Tastendruck ermöglicht. Ist die gewünschte Rekursionstiefe noch nicht erreicht und rt daher größer als 1, ruft sich die Prozedur dreimal selbst auf, wobei die um 1 verringerte Rekursionstiefe und die Eckpunkte der nach dem oben genannten Schema berechneten Dreiecke übergeben werden {4}. Ist das Flag farbe auf 1 gesetzt, wird die Zeichenfarbe in Abhängigkeit zur Rekursionstiefe neu gesetzt {5}, wodurch erkennbar ist, welche Dreiecke im selben Rekursionsschritt gezeichnet wurden. Nach einer Verzögerung um die in verz eingegeben Anzahl an Millisekunden {6} wird ein Dreieck entsprechend der übergebenen Koordinaten gezeichnet {7}. Während die Bildschirmausgabe bei den beiden vorigen Programmen im aufsteigenden Ast der Rekursion stattfand, wird sie hier erst im absteigenden Rekursionsast vollführt, was zur Folge hat, daß nicht zuerst die großen und dann die kleinen Dreiecke, sondern zuerst die kleinen und dann die größeren gezeichnet werden.
Im Hauptprogramm wird der Benutzer gebeten, die Rekursionstiefe rektief, den Verzögerungsfaktor verz und das Farbflag farb einzugeben {8}. Nach der Initialisierung des Grafikmodus {9} wird die Prozedur frakt mit der Rekursionstiefe und den Koordinaten eines bildschirmfüllenden Dreiecks als Parameter aufgerufen {10}. Das Farbflag farb ist global deklariert und somit im gesamten Programm zugänglich. Da es sich auch während der Rekursion nicht verändert, muß es nicht als Parameter übergeben werden. Nach dem Zeichnen der Dreiecke wartet das Programm auf einen Tastendruck {11} und schaltet danach wieder in den Textmodus. Damit endet das Programm.
|
