Komplexe Zahlen

Möchte man mit komplexen Zahlen rechnen, dann bietet die C++-Standardlibrary was passendes. Das Template std::complex<> bietet alle üblichen Operationen wie Addition und Multiplikation.

Video

Quelltext

Die Projektdatei für qmake:

QMAKE_CXXFLAGS += -std=c++11
SOURCES += mandelbrot.cpp
TARGET = mandelbrot
QT += widgets gui

Der eigentliche Quellcode:

#include <complex>
#include <iostream>
#include <thread>
#include <mutex>
#include <chrono>

#include <QApplication>
#include <QMainWindow>
#include <QPainter>
#include <QLabel>
#include <QPixmap>

using namespace std;

unsigned int const colors = 256;

unsigned int iterate(complex<float> point, unsigned int iter_max, unsigned int abs_max)
{
    complex<float> z(0);
    unsigned int iter = 0;
    while (iter < iter_max && abs(z) < abs_max) {
        z = z*z + point;
        ++iter;
    }
    return iter;
}

complex<float> getComplex(int x, int y, int max_x, int max_y, float left, float top, float right, float bottom)
{
    return complex<float>(
        left+(right-left)*x/max_x,
        top+(bottom-top)*y/max_y
    );
}

class MBLabel : public QLabel
{
    QPixmap pm;
    bool done;
    mutex m;
    std::vector<QColor> palette;
    
public:
    
    MBLabel()
        : QLabel(), pm(600,400), done(false)
    {
        resize(600,400);
        pm.fill();
        palette.reserve(colors);
        for (int x = 0; x < colors/32; ++x) {
            palette.push_back(QColor(x*32*255/colors,0,0));
        }
        for (int x = 0; x < colors/32; ++x) {
            palette.push_back(QColor(255,x*32*255/colors,0));
        }
        for (int x = 0; x < colors/16; ++x) {
            palette.push_back(QColor(((colors/16-x)*16)*255/colors,255,0));
        }
        for (int x = 0; x < colors/16; ++x) {
            palette.push_back(QColor(0,((colors/16-x)*16)*255/colors,x*16*255/colors));
        }
        for (int x = 0; x < colors/16; ++x) {
            palette.push_back(QColor(x*16*255/colors,0,255));
        }
        for (int x = 0; x < colors/4; ++x) {
            palette.push_back(QColor(((colors/4-x)*4)*255/colors,x*4*255/colors,255));
        }
        for (int x = 0; x < colors/2; ++x) {
            palette.push_back(QColor(x*2*255/colors,255,255));
        }
        palette[colors-1] = QColor(0,0,0);
    }

    void calculate()
    {
        QPainter p(&pm);

        for (int y = 0; y < 400; ++y) {
            for (int x = 0; x < 600; ++x) {
                unsigned int iterations;
                {
                    iterations = iterate(
                        getComplex(x, y, 600, 400, -2.2, -1, 0.8, 1),
                        //getComplex(x, y, 600, 400, 0.25, 0.45, 0.4, 0.55),
                        colors,
                        2000
                    );
                }
                lock_guard<mutex> l(m);
                p.setPen(palette[iterations-1]);
                p.drawPoint(x, y);
            }
        }
    }
    
    void paintEvent(QPaintEvent *ev) 
    {
        lock_guard<mutex> l(m);
        QPainter p(this);
        p.drawPixmap(0,0, pm);
        QLabel::paintEvent(ev);
        // come again in 10 ms
        startTimer(10);
    }    
    
protected:
    
    void timerEvent(QTimerEvent *event) Q_DECL_OVERRIDE
    {
        update();
    }
};

int main(int argc, char *argv[])
{
    QApplication app{ argc, argv };
    
    QMainWindow main_win;
    MBLabel label;
    main_win.setCentralWidget(&label);
    main_win.resize(600,400);

    thread t { &MBLabel::calculate, &label };
    
    main_win.show();
    app.exec();
    t.join();
}

Erklärung

std::complex<> nimmt als Template-Parameter den numerischen Typ für die Darstellung von rellem und imaginären Anteil. Der Standard spezifiziert, dass nur float, double und long double als Parametertypen zulässig sind. Durch den Parametertypen kann der Entwickler wählen, wie präzise die Berechnungen intern sein müssen und letztlich wieviel Speicherplatz er dafür zu investieren gedenkt. In meinem Fall reicht float hinsichtlich der Genauigkeit aus.

Um die Verwendung etwas interessanter zu machen implementiert das Programm oben die Visualisierung des "Apfelmännchens" - der Mandelbrotmenge. Diese ist durch eine rekursive Folge über die komplexen Zahlen definiert:

zn+1=zn2+c
z0=0

z und c sind hier komplexe Zahlen. Die Zahl c ist Element der Mandelbrotmenge wenn der Betrag der Folge z für das gegebene c nicht divergiert (also gegen + oder - Unendlich geht). Was es genau damit mathematisch auf sich hat ist nicht weiter interessant hier, aber die Darstellung der Mangelbrotmenge als zweidimensionales Bild sieht einfach nett aus. Man bildet dazu einfach die verschiedenen c auf Pixel in einem Bild ab und färbt jeden abhängig davon ein, wie schnell der Betrag der Folge divergiert.

Die Abbildung geschieht durch die Funktion getComplex(): Sie nimmt die aktuellen Pixelkoordinaten, die Gesamtgröße des Bildes und und einen rechteckigen Ausschnitt aus der komplexen Zahlene, der in dem Bild darzustellen ist. Die gegebenen Pixelkoordinaten werden in den korrespondierenden Punkt in der komplexen Zahlenebene umgerechnet und zurückgeliefert.

Die Ausgabe von getComplex() dient wiederum als Eingabe für die Funktion iterate(), die testet, ob die Folge an der entsprechenden Stelle divergiert oder nicht. Echt beweisen kann man das numerisch natürlich nicht, aber für alle praktischen Belange reicht es aus, die Folge für ein paar Runden zu berechnen und abzuschätzen, wo es hingehen wird. Zu diesem Zweck wird ein maximaler Betrag vorgegeben bei dessen Überschreitung wir annehmen, dass die Folge divergiert, sowie eine maximale Rundenanzahl nach der wir annehmen, dass sie es nicht tut. Die Funktion initialisierung nun die Folge für z0 und berechnet so lange das nächste Glied, bis entweder die Rundenanzahl abgelaufen ist oder bis wir den Maximalwert des Betrages erreichen. Die Berechnung (Zeile 22) zeigt, dass std::complex<> die üblichen Operatoren wie + und * unterstützt. In Zeile 21 ist zu sehen, dass die Funktion std::abs() für std::complex<> definiert ist und den korrekten Betrag der komplexen Zahl zurückliefert. Die Anzahl an gerechneten Runden bis zum Abbruch dient als Indikator für die Geschwindigkeit, mit der die Funktion divergiert (falls überhaupt) und kann über eine Farbpalette auf eine passende Pixelfarbe abgebildet werden. 

Die betreffenden Iterationen werden nun für jeden Pixel im Bild berechnet und dieser wird passend eingefärbt. Ergebnis ist die bekannte farbenfrohe Darstellung der Mandelbrotmenge.