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

版权声明

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

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

1. 迭代函数系统

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

表1 线性函数组

image-20221103215305050

  上述整个计算过程也是迭代的,我们首先选择坐标原点(0,0)赋值给(xi,yi),选择上述函数组中的一个用于迭代生成新坐标(xi+1,yi+1),然后再把新坐标(xi+1,yi+1)赋值给(xi,yi),选择上述函数组中的一个计算得到下一个平面坐标点。在重复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。

image-20221103173607632

  其中,Build System选择qmake。

image-20221103173642955

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

image-20221103173743507

3. 代码分析

3.1 ifs()函数

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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则存储了所有点对应的函数组序号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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 程序执行与结果查看

1
2
3
4
5
6
7
8
9
10
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行报告了图像文件的存储路径。读者按该路径在操作系统文件管理器中找到这个文件,双击打开即可看到那片树叶。

image-20221103223437656

4. 完整源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
//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;
}