Aufgabe 3: Rekursive Besen

Aufgabe 3: Rekursive Besen

Vorüberlegung

Die Borsten verschwimmen zu einem selbstähnlichen Gebilde, auch Fraktal genannt. Zwei Borsten, ich nenne sie Tochterborsten, stehen immer in Abhängigkeit von einer dritten, der Mutterborste. Mit jedem Rekursionsschritt wird jede Tochterborste zu einer Mutterborste für zwei neue Tochterborsten. Da diese beiden neuen nach den gleichen mathematischen Regeln gebildet werden, entsteht ein zum Original affines Bild.

Der Algorithmus ist am einfachsten mit einer Rekursion zu lösen. Diese bildet für eine übergebene Mutterborste zwei Tochterborsten und übergibt diese durch zwei rekursive Aufrufe an sich selbst. Nach einer vorher festgelegten Anzahl an Schritten bricht diese Rekursion ab.

Ich habe bei der Berechnung der Gebilde ein Polarkoordinatensystem benutzt, da dieses durch die Verwendung von Winkeln und Längen einen entscheidenen Vorteil aufweist: die Winkel der Borsten zueinander sind stets konstant. Im Laufe der Rekursion ändern sich lediglich die Längen.

Die Ur-Mutterborste liegt im Koordinatenursprung. Durch die eingegebenen Werte kann daraus das Ursprungsbild berechnet werden. Der Endpunkt errechnet sich jeweils:

X_Ende = X_Anfang + cos(Winkel_{Koordinatensystem}) * Länge

Y_Ende = Y_Anfang + cos(Winkel_{Koordinatensystem}) * Länge

Für jede Tochterborste erstelle ich mathematisch ein neues Koordinatensystem. Dieses ergibt sich aus einer Verschiebung, so daß der Anfangspunkt im Ursprung liegt, und einer Rotation. Somit hat diese Borste in diesem Koordinatensystem den gleichen Winkel wie die Mutterborste und unterscheidet sich nur in der Länge. Um die Tochterborste zu zeichnen, rechne ich dieses neue Koordinatensystem in karthesische Bildschirmkoordinaten um. Somit ergibt sich für die Anfangskoordinate:

X_Anfang = X_Mitte + cos (Winkel_{Koordinatensystem} + Winkel_Borste) * Länge_Mutter * Länge_Borste

Y_Anfang = Y_Mitte + sin (Winkel_{Koordinatensystem} + Winkel_Borste) * Länge_Mutter * Länge_Borste

Da jede Borste 2 Tochterborsten bildet, ist die Gesamtborstenzahl 2^{Rekursionstiefe}+1. Schon bei 2¹⁶+1 = 65537 kommt das Programm normalerweise an gewisse Zeitgrenzen.

Gewöhnlich sind die Tochterborsten kürzer als ihre Mutterborste. Dies führt im Verlauf der Rekursion zu immer kleineren Längen. Da die Bildschirmauflösung Grenzen setzt, habe ich mich entschlossen, bei Borstenlängen, die kleiner als ½ Pixel sind, die Rekursion vorzeitig abzubrechen, da das graphische Ergebnis sonst nur verfälscht sind. Außerdem beschleunigt diese Vorgehensweise die Geschwindigkeit bei großen Rekursionstiefen dramatisch. So konnte ich die Beispielbilder mit einer Rekursionstiefe von 30 berechnen lassen, was nie länger als 2 Sekunden dauerte.

Bedienung

Die Eingabe der Borsten erfolgt auch in Polarkoordinaten. Alle Zahlen müssen positiv und ganzzahlig sein. Die Winkel liegen deshalb im Bereich 0° bis 360°. Größere Werte sind auch zulässig, aber nicht sinnvoll. Negative Werte werden nicht akzeptiert, können aber durch posWinkel = (360° - negWinkel) in positive Zahlen umgerechnet werden. Die Länge wird in Pixel erwartet.

Bei Programmstart ist die Beispielborstensituation voreingestellt (siehe Bildschirmfoto 1). Die Anfangspunkte der Tochterborsten beziehen sich auf den Anfangspunkt der Mutterborste (d.h. Koordinatenursprung), die Endpunkte dagegen auf die Anfangspunkte der jeweiligen Tochterborste.

Durch Enter wird Zeichnen aktiviert, was zu einer Neuberechnung des Fraktals führt. Dieses wird in einem seperaten Fenster gezeichnet. Dessen Größe ist frei veränderbar. Der Koordinatenursprung liegt dabei immer in der Mitte.

Bei der Rekursionstiefe ist darauf zu achten, daß sinnvolle Werte zu wählen sind, etwa im Bereich 1 bis 20. Größere Werte können schnell sehr zeitaufwendigen Berechnungen führen.

Jede Veränderung führt zu einer Neuzeichnung, deshalb sollte man die Fenstergröße und –lage gleich zu Anfang festlegen.

Programmdokumentation

Die Hauptarbeit wird von 3 Funktionen geleistet:

void GetNumbers();

void OnPaint();

void CalcFractal(float StartX, float StartY, float Winkel, float Faktor, int nSchritt);

Zu beachten ist, daß in zwei Klassen die Struktur nBorsten existiert. Ihr Unterschied liegt nur in der eingetragenen Länge. Im Dialog ist dies die Benutzereingabe, im Zeichenfeld dagegen das Verhältnis zur Mutterborste, normalerweise 0<Länge<1.

GetNumbers

Diese Methode liest die Zahlen aus dem Bildschirmdialog aus. Ihre wesentliche Aufgabe besteht aber darin, alle Winkel von Grad in Radiant umzurechnen. Dazu bediene ich mich der Formal rad = grad*pi:180°.

OnPaint

OnPaint wird bei jeder Neuzeichnung auf Anforderung von Windows oder durch gezielte Anordnung des Benutzers aufgerufen. Hier wird die Vorarbeit für die Konstruktion des Fraktals geleistet.

Zuerst werden die aktuellen Werte aus dem Bildschirmdialog ausgelesen. Sobald die Rekursionstiefe oder die Länge der Mutterborste gleich 0 ist, wird abgebrochen, da so kein Fraktal entstehen. Danach holt sich die Routine Informationen über ihr Fenster und legt die Stiftfarbe fest. Anschließend wird der Mittelpunkt errechnet. Dieser dient zur Festlegung des Startpunktes der Mutterborste.

Als nächstes wird die Länge der Mutterborste bestimmt. Jede Längenangabe wird nun als Vielfaches dieser umgerechnet. Die Borsten sollten nun alle eine Länge kleiner 1 haben.

Abschließend erfolgt der Aufruf von CalcFractal mit der Mutterborste im Koordinatenursprung.

CalcFractal

Diese Funktion ist der wesentlichste Bestandteil. Übergeben wird der Mittelpunkt des zu benutzenden Koordinatensystems, welches um Winkel rotiert wird. Die Verkürzung aller Längen wird mit Faktor bestimmt. Als letztes wird die aktuelle Rekursionstiefe verlangt.

Zunächst erfolgt eine Bestimmung der Länge der Borste. Ist diese kleiner als ein bestimmter Wert, ich habe 0,5 als sinnvoll empfunden, bricht die Funktion ab. Anderenfalls wird die Borste gezeichnet. Ist die vorgeschriebene Rekursionstiefe erreicht, erfolgt ebenfalls ein Abbruch.

Nun werden die Anfangskoordinaten der erste Tochterborste nach den oben beschriebenen Formeln errechnet. Ein rekursiver Aufruf erhält diese als neuen Koordinatensystemmittelpunkt übergeben. Zusätzlich werden der Rotationswinkel (er ist der des aktuellen Koordinatensystems plus den Winkel der Borste), die Längenverkürzung (Produkt der aktuellen mit der Borstenlänge) und die um 1 erhöhte Rekursionstiefe übermittelt.

Für die zweite Tochterborste geschieht dasselbe.

Beispiele

Die ersten sechs Stufen einer Anordnung, die der Beispielanordnung sehr ähnlich ist, sehen wie folgt aus:

Die Parameter waren die voreingestellten Werte:

Mutterborste: 0-(0°/100)

1.Tochterborste: (160°/30)-(45°/60)

2.Tochterborste: (30°/90)-(80°/60)

Schön fand ich auch folgende Bilder:

Dieses ähnelt dem berühmten Farnblatt.

Parameter:

Mutter: 0-(0°/50)

1.Tochter: (160°/15)-(45°/35)

2.Tochter: (10°/60)-(10°/35)

Rekursionstiefe: 30

Hier ist eine gewisse Ähnlichkeit mit Julia-Mengen vorhanden.

Parameter:

Mutter: 0-(0°/50)

1.Tochter: (160°/15)-(160°/38)

2.Tochter: (10°/60)-(55°/33)

Rekursionstiefe: 30

Erstaunlich ist, daß bei einem zahlenmäßig recht geringem Unterschied zum vorherigen Beispiel ein vollkommen anderes Fraktal entsteht.

Ich würde dies Fraktal als eine Sonnenblume beschreiben.

Parameter:

Mutter: 0-(0°/50)

1.Tochter: (140°/10)-(100°/49)

2.Tochter: (0°/70)-(50°/10)

Rekursionstiefe: 30

Quelltext

DREI.H

#include "resource.h" // ID-Codes einbinden

typedef struct

{

float Winkel, Laenge;

} tPolar; // Typ für Polarkoordinaten

#define Borsten 3 // 3 Borsten insgesamt

#define BorstenPunkte 2*Borsten-1 // Mutterstartpunkt ist immer (0/0)

#define MaxAufloesung 0.5 // Grenzwert für Borstenlänge

class CDreiApp : public CWinApp // Basisklasse ableiten

{

virtual BOOL InitInstance(); // Start überladen

};

class CDisplay : public CFrameWnd // Zeichenfläche

{

public:

CDisplay(); // Konstruktor überladen

afx_msg void OnPaint(); // Neuzeichnen

afx_msg void OnClose(); // Programmende

private:

void CalcFractal(float StartX, float StartY, float Winkel, float Faktor, int nSchritt);

// Fraktal berechnen

CPaintDC* pDC; // Zeiger auf Zeichenklasse

int MidX; // Mittelpunkt der Zeichenfläche

int MidY;

tPolar nBorsten[BorstenPunkte]; // Borstenpunkte

float OriginalLaenge; // die Originallänge

DECLARE_MESSAGE_MAP() // MessageHandler installieren

};

class CDreiDlg : public CDialog // Dialogklasse ableiten

{

public:

CDreiDlg(CWnd* pParent = NULL); // Konstruktor

enum { IDD = IDD_DIALOG }; // ID merken

void GetNumbers(); // Dialog auslesen

tPolar nBorsten[BorstenPunkte]; // Borstenpunkte

int nRekursionstiefe; // max. Rekursionstiefe

protected:

virtual BOOL OnInitDialog(); // Dialogstart

virtual void OnOK(); // Eingabe von Enter

afx_msg void OnZeichnen(); // explizite Zeichnen-Anforderung

afx_msg void OnAbout(); // Programminfo

DECLARE_MESSAGE_MAP() // Messagehandler installieren

};

DREI.CPP

#include <afxwin.h> // MFC-Definitionen einbinden

#include <math.h> // Sinus und Cosinus einbinden

#include "drei.h" // Headerfile einbinden

CDreiApp DreiApp; // Programm statisch erzeugen

BOOL CDreiApp::InitInstance() // Start überladen

{

Enable3dControls(); // 3D-Stil aktivieren

m_pMainWnd = new CDisplay(); // Zeichenfläche ist Hauptfenster

m_pMainWnd->ShowWindow(SW_SHOW); // Zeiger darauf speichern

return TRUE;

}

BEGIN_MESSAGE_MAP(CDisplay, CFrameWnd) // Nachrichten weiterleiten

ON_WM_PAINT()

ON_WM_CLOSE()

END_MESSAGE_MAP()

static CDreiDlg* pDlg; // Zugriff auf Dialog ermöglichen

CDisplay::CDisplay() // Aktivierung Hauptfenster

{

Create(NULL, "Huschelmutzs Vision", WS_OVERLAPPEDWINDOW);

// Dialog nicht-modal kreieren

pDlg = new CDreiDlg(this); // Zeiger sichern

}

void CDisplay::OnPaint() // Neuzeichnen

{

pDlg->GetNumbers(); // Zahlenwerte holen

if ((pDlg->nRekursionstiefe==0)||(pDlg->nBorsten[0].Laenge==0))

return; // wenn kein Fraktal entsteht abbrechen

CPaintDC MyDC(this); // Zeichenfläche holen

CPen pen; // Stift holen

pen.CreatePen(PS_SOLID,1,RGB(0,0,0)); // Stift soll schwarz sein mit Breite 1

MyDC.SelectObject(&pen); // Stift einbinden

pDC = &MyDC; // Zeichenfläche für CalcFractal sichern

CRect rect; // Bildschirmausmaße holen

GetClientRect(rect);

MidX = rect.right/2; // Mitte bestimmen

MidY = rect.bottom/2;

OriginalLaenge = pDlg->nBorsten[0].Laenge; // Originallänge holen

for (int Lauf=0; Lauf<BorstenPunkte; Lauf++)

{ // alle Borstenpunkte durchlaufen

nBorsten[Lauf].Winkel = pDlg->nBorsten[Lauf].Winkel;

// Winkel übernehmen

nBorsten[Lauf].Laenge = pDlg->nBorsten[Lauf].Laenge/OriginalLaenge;

// neue Länge als Verhältnis zur

} // Originallänge

CalcFractal(0,0,nBorsten[0].Winkel,1,1); // Berechnung beginnen im Ursprung

// bei Mutterborste, Normalgröße und

// Rekursionstiefe 1

}

void CDisplay::OnClose() // Programmende

{

if (MessageBox("Wirklich beenden ?","Ende",MB_YESNO|MB_ICONQUESTION)!=IDYES)

return; // Sicherheitsabfrage

pDlg->DestroyWindow(); // nicht-modalen Dialog zerstören

delete(pDlg);

CFrameWnd::OnClose(); // Zeichenfläche schließen

}

void CDisplay::CalcFractal(float StartX, float StartY, float Winkel, float Faktor, int nSchritt)

{ // Fraktal berechnen

float NeueLaenge = Faktor*OriginalLaenge; // Länge bestimmen

if (NeueLaenge<MaxAufloesung) // Unterschreitung des Grenzwertes

return;

pDC->MoveTo(int(StartX)+MidX, -int(StartY)+MidY);

pDC->LineTo(int(StartX+cos(Winkel)*NeueLaenge)+MidX, -int(StartY+sin(Winkel)*NeueLaenge)+MidY);

// Linie zeichnen (mittels Turtle-Grafik)

if (nSchritt>pDlg->nRekursionstiefe) // Rekursionstiefe erreicht ?

return; // wenn ja, dann abbrechen

float NewX = StartX+cos(nBorsten[1].Winkel+Winkel)*nBorsten[1].Laenge*NeueLaenge;

float NewY = StartY+sin(nBorsten[1].Winkel+Winkel)*nBorsten[1].Laenge*NeueLaenge;

// neue Mitte des Koordinatensystems

CalcFractal(NewX,NewY,Winkel+nBorsten[2].Winkel,Faktor*nBorsten[2].Laenge,nSchritt+1);

// 1.Tochterborste berechnen

NewX = StartX+cos(nBorsten[3].Winkel+Winkel)*nBorsten[3].Laenge*NeueLaenge;

NewY = StartY+sin(nBorsten[3].Winkel+Winkel)*nBorsten[3].Laenge*NeueLaenge;

// neue Mitte des Koordinatensystems

CalcFractal(NewX,NewY,Winkel+nBorsten[4].Winkel,Faktor*nBorsten[4].Laenge,nSchritt+1);

// 2.Tochterborste berechnen

}

BEGIN_MESSAGE_MAP(CDreiDlg, CDialog) // Nachrichten weiterleiten

ON_BN_CLICKED(ID_BUTTON_ZEICHNEN, OnZeichnen)

ON_BN_CLICKED(ID_BUTTON_ABOUT, OnAbout)

END_MESSAGE_MAP()

CDreiDlg::CDreiDlg(CWnd* pParent) // Konstruktor

{

Create(IDD, pParent); // nicht-modal erzeugen

}

BOOL CDreiDlg::OnInitDialog() // Dialogstart

{

CDialog::OnInitDialog(); // zur Grundklasse weiterleiten

(GetDlgItem(ID_EDIT_MUTTER_ENDE_X))->SetFocus();

// Focus setzen

return FALSE; // diesen von Windows nicht verändern

}

void CDreiDlg::OnOK() // Eingabe von Enter

{

OnZeichnen(); // Fraktal neu zeichnen

}

void CDreiDlg::OnZeichnen() // explizite Zeichnen-Anforderung

{

DreiApp.m_pMainWnd->Invalidate(); // OnPaint der Zeichenfläche indirekt

// aufrufen

}

void CDreiDlg::GetNumbers() // Dialog auslesen

{

int nID = ID_EDIT_MUTTER_ENDE_X; // erstes Eingabefeld

for (int Lauf = 0; Lauf<BorstenPunkte; Lauf++)

{ // für jeden Borstenpunkt

nBorsten[Lauf].Winkel = GetDlgItemInt(nID++)/180.0*3.1415926;

// Winkel gleich in Radiant umrechnen

nBorsten[Lauf].Laenge = GetDlgItemInt(nID++);

// Länge unverändert übernehmen

}

nRekursionstiefe = GetDlgItemInt(ID_EDIT_REKURSIONSTIEFE);

// Rekursionstiefe auslesen

}

void CDreiDlg::OnAbout() // Programminfo

{

MessageBox("geschrieben von Stephan Brumme\nin Watcom C++ 10.6 mit MFC 3.2",

"Über...",MB_OK|MB_ICONINFORMATION);

}

DREI.DLG

100 DIALOG FIXED IMPURE 3, 14, 238, 107

STYLE DS_MODALFRAME | DS_3DLOOK | WS_OVERLAPPED | WS_CAPTION | WS_VISIBLE

CAPTION "Aufgabe 3: Rekursive Besen"

FONT 8, "Helv"

BEGIN

CONTROL "&Zeichnen", 114, "BUTTON", BS_PUSHBUTTON | WS_CHILD | WS_VISIBLE | WS_TABSTOP, 110, 90, 55, 14

CONTROL "&Autor", 115, "BUTTON", BS_PUSHBUTTON | WS_CHILD | WS_VISIBLE | WS_TABSTOP, 175, 90, 55, 14

CONTROL "Mutterborste:", 122, "STATIC", SS_LEFT | WS_CHILD | WS_VISIBLE, 5, 30, 46, 8

CONTROL "Winkel", 116, "STATIC", SS_LEFT | WS_CHILD | WS_VISIBLE, 75, 15, 23, 8

CONTROL "Lange", 117, "STATIC", SS_LEFT | WS_CHILD | WS_VISIBLE, 115, 15, 24, 8

CONTROL "1. Tocherborste:", 122, "STATIC", SS_LEFT | WS_CHILD | WS_VISIBLE, 5, 50, 53, 10

CONTROL "Winkel", 118, "STATIC", SS_LEFT | WS_CHILD | WS_VISIBLE, 165, 15, 24, 8

CONTROL "Lange", 119, "STATIC", SS_LEFT | WS_CHILD | WS_VISIBLE, 205, 15, 21, 8

CONTROL "Anfangspunkt", 120, "STATIC", SS_LEFT | WS_CHILD | WS_VISIBLE, 80, 5, 45, 8

CONTROL "Endpunkt", 121, "STATIC", SS_LEFT | WS_CHILD | WS_VISIBLE, 170, 5, 36, 8

CONTROL "2. Tochterborste:", 123, "STATIC", SS_LEFT | WS_CHILD | WS_VISIBLE, 5, 70, 56, 8

CONTROL "Rekursionstiefe:", 124, "STATIC", SS_LEFT | WS_CHILD | WS_VISIBLE, 5, 90, 53, 8

END

RESOURCE.H

#define IDD_DIALOG 100

#define ID_EDIT_MUTTER_ENDE_X 103

#define ID_EDIT_MUTTER_ENDE_Y 104

#define ID_EDIT_TOCHTER1_ANFANG_X 105

#define ID_EDIT_TOCHTER1_ANFANG_Y 106

#define ID_EDIT_TOCHTER1_ENDE_X 107

#define ID_EDIT_TOCHTER1_ENDE_Y 108

#define ID_EDIT_TOCHTER2_ANFANG_X 109

#define ID_EDIT_TOCHTER2_ANFANG_Y 110

#define ID_EDIT_TOCHTER2_ENDE_X 111

#define ID_EDIT_TOCHTER2_ENDE_Y 112

#define ID_EDIT_REKURSIONSTIEFE 113

#define ID_BUTTON_ZEICHNEN 114

#define ID_BUTTON_ABOUT 115