C/C++微实践 - 分形蕨类树叶

海洋饼干叔叔

发布于：2022年11月3日

C/C++

借助于4个线性方程组，“凭空”生成一片分形的蕨类植物树叶，感受数学之美。

版权声明

本文可以在互联网上自由转载，但必须：注明出处(作者：海洋饼干叔叔)并包含指向本页面的链接。

本文不可以以纸质出版为目的进行改编、摘抄。

1. 迭代函数系统

迭代函数系统（iterated function system）是一种创建分形图案的简单算法。下面我们用迭代函数系统来凭“空”生成一片树叶。利用表1中的4组线性函数均可以根据一个二维平面点的点坐标（x_i,y_i）计算得到一个新的点坐标（x_i+1,y_i+1）。

表1 线性函数组

上述整个计算过程也是迭代的，我们首先选择坐标原点（0,0）赋值给（x_i,y_i），选择上述函数组中的一个用于迭代生成新坐标（x_i+1,y_i+1），然后再把新坐标（x_i+1,y_i+1）赋值给（x_i,y_i），选择上述函数组中的一个计算得到下一个平面坐标点。在重复10万次后，我们就得到了平面上的10万个点，将这10万个点在平面上画出来，即得该迭代函数系统的分形图案。

那么在迭代时，应该选择哪个函数组进行迭代计算呢？答案是在符合概率要求的条件下随机选择。我们为每个函数组指定了选择概率，分别是1%，7%，7%和85%。可以看到，函数组3被选择的概率最高。

这次我们先看看绘图结果，如图1所示。Amazing! 在只有数个参数的情况下，IFS成功地构造了树叶。读者如果放大查看，可以看到，树叶中的某片子树叶与整片树叶一模一样！图像表现出高度的自相似性。

ifs

图1 分形蕨类树叶

2. 创建Qt项目

这个微实践涉及到绘图，而标准的C++库不提供绘图支持。我们选择了Qt Creator来实现该程序。由于程序使用到了Qt的某些专属特性，因此只能在Qt Creator相关环境下编译和运行。

在Qt Creator中选择菜单File->New File or Project，选择Non-Qt Project, Plain C++ Application，项目名称：IFSLeaf。

其中，Build System选择qmake。

双击打开IFSLeaf.pro，按如下图所示修改该文件的内容。其中，第4行有修改，将qt平台引入“配置”，第5行为新增，在qt中加入GUI模块。

3. 代码分析

3.1 ifs()函数

函数ifs()负责使用表1所提供的4个线性方程组迭代生成N=100,000个坐标点。其中，向量xs,ys存储N个坐标点的x及y坐标，向量cs用于存储每个坐标点生成过程中使用的函数组序号0, 1, 2 或者3。

void ifs(vector<double>& xs,
         vector<double>& ys,
         vector<uint8_t>& cs, const int N)
{
    xs.resize(N); ys.resize(N); cs.resize(N);
    double x = 0, y = 0;
    for (unsigned int i=0;i<N;i++){
        double r = rand()/double(RAND_MAX);
        double x1 = 0, y1 = 0;
        if (r<=0.01){
            x1 = 0;
            y1 = 0.15*y;
            cs[i] = 0;
        }
        else if (r<=0.08){
            x1 = 0.21*x - 0.19*y;
            y1 = 0.24*x + 0.27*y + 1.5;
            cs[i] = 1;
        }
        else if (r<=0.15){
            x1 = -0.14*x + 0.26*y;
            y1 = 0.26*x + 0.25*y + 0.47;
            cs[i] = 2;
        }
        else{
            x1 = 0.87*x;
            y1 = -0.05*x + 0.84*y + 1.54;
            cs[i] = 3;
        }
        x = x1;  y = y1;
        xs[i] = x; ys[i] = y;
    }
}

第5行：将向量xs,ys,cs的尺寸修改为N。

第7~32行：循环N次，迭代生成所有点。

第8行：借助于rand()/RAND_MAX得到一个取值范围为0~1的随机浮点数，请注意double(RAND_MAX)的这个类型转换十分重要，如果是整数除以整数，结果为舍弃掉小数部分的整数。

第10~29行：根据随机数r的值来选择函数组，以确保如表1所述的各函数组的选择概率。简单地说，r的值>0.15的概率约等于0.85，这样就确保了函数组3的被选择概率约等于0.85。在选定了函数组之后，除了通过x,y计算x1,y1之外，还把被选择的函数组序号存入了cs[i]。

第30行：将(x1,y1)赋值给x,y，准备下一轮迭代。

第31行：将(x,y)存入(xs[i],ys[i])。

3.2 绘图

saveJpg()函数负责将向量xs,ys,cs中的点数据存入文件ifs.jpg。显然，xs,ys存储了所有点的原始点坐标，cs则存储了所有点对应的函数组序号。

#include <algorithm>
#include <QImage>
#include <QDir>

QString saveJpg(const vector<double>& xs,
                const vector<double>& ys,
                const vector<uint8_t>& cs)
{
    double xMax = *max_element(xs.cbegin(),xs.cend());  //取x坐标最大值
    double xMin = *min_element(xs.cbegin(),xs.cend());  //取x坐标最小值
    double yMax = *max_element(ys.cbegin(),ys.cend());  //取y坐标最大值
    double yMin = *min_element(ys.cbegin(),ys.cend());  //取y坐标最小值

    int w = (xMax-xMin)*100;    //图像像素宽度 = x坐标跨度 * 100
    int h = (yMax-yMin)*100;    //图像像素高度 = y坐标跨度 * 100

    QImage img(w,h,QImage::Format_RGB32);  //创建指定宽高的QImage对象，它代表一幅像素图
    img.fill(QColor(255,255,255));    //设置背景色为白色
    for (auto i=0;i<xs.size();i++){
        int x = w*(xs[i]-xMin)/(xMax-xMin);  //将xs[i]映射到图像x坐标 
        int y = h-h*(ys[i]-yMin)/(yMax-yMin); //将ys[i]映射到图像y坐标
        auto c = cs[i];  //根据函数组序号确定像素颜色
        auto clr = c==0?Qt::black:(c==1?Qt::red:(c==2?Qt::blue:Qt::green));
        img.setPixelColor(x,y,clr);  //设置图像(x,y)像素的颜色
    }

    QString sFile = QDir::currentPath() + "\\ifs.jpg";  //当前工作路径 + ifs.jpg
    img.save(sFile);  //保存Image至文件
    return sFile;  //返回文件名
}

第9 ~ 12行：通过STL算法以及向量的迭代器获取x和y坐标的最大最小值。关于STL算法以及迭代器，参见本书第19章。

第14 ~ 15行：原始点坐标有正有负，绝对值在10以下，将x坐标,y坐标跨度各乘以100，得到图像的像素宽度及高度，大约在1000以下。

第17行：QImage来自于Qt的<QImage>头文件，它表示一个像素图像，仅可在Qt环境下使用。

第18行：设置图像背景色为白色。

第19 ~ 25行：逐一遍历所有原始坐标点，将坐标映射到图像的像素坐标，并根据对应的函数组编号选择不同的颜色并设置到img。注意，图像的像素坐标是top-left坐标系，其y方向与标准坐标系是反的，所以在第21行进行了” h - “的特殊处理。

第27行：QDir::currentPath()用于返回程序运行的当前路径，其加上\ifs.jpg，即为拟存储文件的完整路径。注意，因为转义的关系，这里使用了\\。

第28行：保存Image至文件。

第29行：返回文件的完整路径，注意，该路径是QString类型，这是Qt里的string类型。

说明：QColor(r,g,b)函数通过三原色原理生成需要的颜色，当r,g,b都是255时，为白色， QColor(255,0,0)为红色，QColor(0,255,0)为绿色，QColor(255,255,0)为黄色…

3.3 程序执行与结果查看

int main()
{
    const int N = 100000;
    vector<double> xs, ys;
    vector<uint8_t> cs;
    ifs(xs,ys,cs,N);
    auto sFile = saveJpg(xs,ys,cs);
    cout << "File saved: "<< sFile.toStdString();
    return 0;
}

这是程序的main()函数：先在第6行调用ifs生成原始点坐标数据，然后在第7行将其存入文件。在第8行，向控制台报告了文件的路径。

在作者的计算机上，本程序的执行结果为：

1
2
3

QImage::setPixelColor: coordinate (183,962) out of range
QImage::setPixelColor: coordinate (434,675) out of range
File saved: D:/C2Cpp/C16_ObjectCopy/build-IFSLeaf-Desktop_Qt_6_2_4_MinGW_64_bit-Debug\ifs.jpg

由于浮点计算误差的关系，saveJpg()函数中计算得到的像素点坐标可能会超过范围，执行结果中的第1，2行即是img->setPixelColor()函数发生的警告信息。

执行结果的第3行报告了图像文件的存储路径。读者按该路径在操作系统文件管理器中找到这个文件，双击打开即可看到那片树叶。

4. 完整源代码

//Project - IFSLeaf
#include <iostream>
#include <array>
#include <algorithm>
#include <QImage>
#include <QDir>
using namespace std;

void ifs(vector<double>& xs,
         vector<double>& ys,
         vector<uint8_t>& cs, const int N)
{
    xs.resize(N); ys.resize(N); cs.resize(N);
    double x = 0, y = 0;
    for (unsigned int i=0;i<N;i++){
        double r = rand()/double(RAND_MAX);
        double x1 = 0, y1 = 0;
        if (r<=0.01){
            x1 = 0;
            y1 = 0.15*y;
            cs[i] = 0;
        }
        else if (r<=0.08){
            x1 = 0.21*x - 0.19*y;
            y1 = 0.24*x + 0.27*y + 1.5;
            cs[i] = 1;
        }
        else if (r<=0.15){
            x1 = -0.14*x + 0.26*y;
            y1 = 0.26*x + 0.25*y + 0.47;
            cs[i] = 2;
        }
        else{
            x1 = 0.87*x;
            y1 = -0.05*x + 0.84*y + 1.54;
            cs[i] = 3;
        }
        x = x1;  y = y1;
        xs[i] = x; ys[i] = y;
    }
}

QString saveJpg(const vector<double>& xs,
                const vector<double>& ys,
                const vector<uint8_t>& cs)
{
    double xMax = *max_element(xs.cbegin(),xs.cend());
    double xMin = *min_element(xs.cbegin(),xs.cend());
    double yMax = *max_element(ys.cbegin(),ys.cend());
    double yMin = *min_element(ys.cbegin(),ys.cend());

    int w = (xMax-xMin)*100;
    int h = (yMax-yMin)*100;

    QImage img(w,h,QImage::Format_RGB32);
    img.fill(QColor(255,255,255));
    for (auto i=0;i<xs.size();i++){
        int x = w*(xs[i]-xMin)/(xMax-xMin);
        int y = h-h*(ys[i]-yMin)/(yMax-yMin);
        auto c = cs[i];
        auto clr = c==0?Qt::black:(c==1?Qt::red:(c==2?Qt::blue:Qt::green));
        img.setPixelColor(x,y,clr);
    }

    QString sFile = QDir::currentPath() + "\\ifs.jpg";
    img.save(sFile);
    return sFile;
}

int main()
{
    const int N = 100000;
    vector<double> xs, ys;
    vector<uint8_t> cs;
    ifs(xs,ys,cs,N);
    auto sFile = saveJpg(xs,ys,cs);
    cout << "File saved: "<< sFile.toStdString();
    return 0;
}