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:
XEnde = XAnfang + cos(WinkelKoordinatensystem) * Länge
YEnde = YAnfang + cos(WinkelKoordinatensystem) * 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:
XAnfang = XMitte + cos (WinkelKoordinatensystem + WinkelBorste) * LängeMutter * LängeBorste
YAnfang = YMitte + sin (WinkelKoordinatensystem + WinkelBorste) * LängeMutter * LängeBorste
Da jede Borste 2 Tochterborsten bildet, ist die Gesamtborstenzahl 2Rekursionstiefe+1. Schon bei 216+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 "0", 103, "EDIT", ES_LEFT | ES_AUTOHSCROLL | ES_NUMBER | WS_CHILD | WS_VISIBLE | WS_BORDER | WS_TABSTOP, 160, 30, 32, 12
CONTROL "100", 104, "EDIT", ES_LEFT | ES_AUTOHSCROLL | ES_NUMBER | WS_CHILD | WS_VISIBLE | WS_BORDER | WS_TABSTOP, 200, 30, 32, 12
CONTROL "160", 105, "EDIT", ES_LEFT | ES_AUTOHSCROLL | ES_NUMBER | WS_CHILD | WS_VISIBLE | WS_BORDER | WS_TABSTOP, 70, 50, 32, 12
CONTROL "30", 106, "EDIT", ES_LEFT | ES_AUTOHSCROLL | ES_NUMBER | WS_CHILD | WS_VISIBLE | WS_BORDER | WS_TABSTOP, 110, 50, 32, 12
CONTROL "45", 107, "EDIT", ES_LEFT | ES_AUTOHSCROLL | ES_NUMBER | WS_CHILD | WS_VISIBLE | WS_BORDER | WS_TABSTOP, 160, 50, 32, 12
CONTROL "60", 108, "EDIT", ES_LEFT | ES_AUTOHSCROLL | ES_NUMBER | WS_CHILD | WS_VISIBLE | WS_BORDER | WS_TABSTOP, 200, 50, 32, 12
CONTROL "30", 109, "EDIT", ES_LEFT | ES_AUTOHSCROLL | ES_NUMBER | WS_CHILD | WS_VISIBLE | WS_BORDER | WS_TABSTOP, 70, 70, 32, 12
CONTROL "90", 110, "EDIT", ES_LEFT | ES_AUTOHSCROLL | ES_NUMBER | WS_CHILD | WS_VISIBLE | WS_BORDER | WS_TABSTOP, 110, 70, 32, 12
CONTROL "80", 111, "EDIT", ES_LEFT | ES_AUTOHSCROLL | ES_NUMBER | WS_CHILD | WS_VISIBLE | WS_BORDER | WS_TABSTOP, 160, 70, 32, 12
CONTROL "60", 112, "EDIT", ES_LEFT | ES_AUTOHSCROLL | ES_NUMBER | WS_CHILD | WS_VISIBLE | WS_BORDER | WS_TABSTOP, 200, 70, 32, 12
CONTROL "10", 113, "EDIT", ES_LEFT | ES_AUTOHSCROLL | ES_NUMBER | WS_CHILD | WS_VISIBLE | WS_BORDER | WS_TABSTOP, 70, 90, 32, 12
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