美丽的数学 之 奇妙的分形

lee1892

之前我在图表区发了几个帖子：
美丽的数学 之 简单但很漂亮的树
美丽的数学 之 雪花
美丽的数学 之 彩色的灌木丛
美丽的数学 之 一片漂亮的树叶

这些帖子的由来都是数学中被称为“分形”（Fractal）的概念，通常被定义为：一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都（至少近似的）是整体缩小后的形状，即具有自相似的性质。（来自中文WiKi）

一、分枝

下面这个附件的由来是我在上面那个“简单但很漂亮的树”的代码基础上改的，鉴于其特点，我将其称之为“分枝”。

奇妙的分形 之 分枝_By Lee1892.rar (123.98 KB, 下载次数: 1129)

2013-11-25 16:21 上传

点击文件名下载附件

1、名称约定

• 向量：遵循标准的数学中向量的概念，由起点和终点构成，亦可表达为起点、角度、长度，二维平面中的向量需要4个变量来表达，代码中为计算方便计，采用的是后者。
• 分形系数：按前述的定义，每一部分都是整体缩小后的形状，这里分形系数即是指当前迭代与上一次之间的几何形状上的比例，通常都是小于 1 的。
• 分形层数：此帖讨论的分形大多是几何形状按一定的规则迭代运算产生的，显然不可能无限制的计算下去，分形层数是指迭代运算的次数。
  

2、分形方式
分枝 的分形方式为：以当前迭代产生的每一个向量作为源，下一次迭代计算时相对于源向量产生 N 个分枝向量，每个分枝向量的长度按“分形系数”由源向量长度缩小，每个分枝向量的角度由源向量旋转获得，且两相邻分枝的夹角相同（方式1，由源向量朝一个方向旋转；方式2，由源向量向两侧分别旋转。附件按方式2）。

3、产生的效果
我预设了几个参数，可以产生如下图的效果：


第一个常见于各种初级的分形的介绍，我称之为二叉折半树；
第二个即为前面提到的那个帖子的形状；
第六个是正三角形的分形，称为谢尔宾斯基三角形（Sierpinski Triangle）
倒数第二个则是莱维C形曲线（Levy C Curve）

4、核心算法
核心算法十分简短，如下：

1. Private Type VECTOR
   
2.     X As Double
   
3.     Y As Double
   
4.     Angle As Double
   
5.     Length As Double
   
6. End Type
   
7. Private Sub GenData()
   
8.     Dim nCount&, i&, j&, dX#, dY#, dAngle#, dLength#
   
9.     For i = 0 To intGeneration
   
10.         nCount = nCount + intBranchCount ^ i
    
11.     Next
    
12.     ReDim arrVertex(nCount)
    
13.     arrVertex(1) = vctInitial
    
14.     For i = 1 To nCount - intBranchCount ^ intGeneration
    
15.         With arrVertex(i)
    
16.             dAngle = .Angle: dLength = .Length
    
17.             dX = .X + dLength * Cos(dAngle)
    
18.             dY = .Y + dLength * Sin(dAngle)
    
19.         End With
    
20.         For j = 1 To intBranchCount
    
21.             With arrVertex((i - 1) * intBranchCount + j + 1)
    
22.                 .Angle = dAngle + (j - (intBranchCount + 1) / 2) * dblBranchAngle
    
23.                 .Length = dLength * dblLengthFactor
    
24.                 .X = dX: .Y = dY
    
25.             End With
    
26.         Next
    
27.     Next
    
28. End Sub

复制代码

式中arrVertex即为所有计算产生的向量数组，显然按前述的计算方式我们需要用树的数据结构，由于是一个所有节点的分支数量固定的完全树，所以可以采用和二叉堆相同的方式使用一个数组来构造。

是不是很有意思呢~



补充内容 (2013-12-11 11:53):
此贴内容较多，建议点击只看该作者

补充内容 (2014-11-8 15:35):
还有更多的讨论，见美丽的数学 复平面

lee1892

二、线的一次折弯

此贴附件： 奇妙的分形 之 线的一次折弯_By Lee1892.rar (69.96 KB, 下载次数: 556)

2013-11-30 14:45 上传

点击文件名下载附件

前面提到过一个莱维C曲线，实际上它应该是由一条线不断的折弯产生的，每一次都将所有的线段向外侧折弯，对一个线段而言，折弯后的两线段夹角为90度，长度为原来的sqrt(2)*1/2倍。如下图动画所示：


如果，改动一下折弯的方向，相邻两次折弯的方向相反，那么就会得到被称为龙曲线（Dragon Curve）的形状，如下图：


附件中的代码更改自前述帖子：彩色的灌木丛，其实现方式如下：
1、按之前源向量的概念，首先将源向量的长度改为原来长度的 sqrt(2)*1/2 倍，然后旋转一定的角度，称为 首选转角度
2、以更新后的源向量为新的源向量，以此新源向量的终点作为新向量的起点，新向量的长度同新源向量，新向量的角度由初始源向量旋转而得，称为 次旋转角度
3、所有向量首尾相连，顺序连接所有向量的起点、终点即能获得图案

此贴附件中，为动画演示计，仍使用数组保存所有向量，由于新向量总是由数组末端添加，所以采用链表的方式链接向量。

附件能够实现的功能：
1、可生成多个曲线，以形成组合的图案
2、可保存生成的图案参数
3、不保存显示图案的数据

附件中有数个已经预设的参数，产生图案如下，相信你会有更多的奇妙图案的~


核心代码：

1. Private Type VECTOR
   
2.     X       As Double
   
3.     Y       As Double
   
4.     Angle   As Double
   
5.     Length  As Double
   
6.     Next    As Long
   
7. End Type
   
8. Private Sub FoldLine(ByVal nRoot&, ByVal iLayer%, ByVal iFlip%)
   
9.     Dim nChild&, nNext&, dAngle#, dLength#, dX#, dY#
   
10.     nChild = nRoot + 2 ^ (iLayer - 1)
    
11.     With arrVertex(nRoot)
    
12.         nNext = .Next: .Next = nChild
    
13.         dLength = .Length
    
14.         .Length = dLength * Sqr(2) / 2
    
15.         dAngle = .Angle
    
16.         .Angle = .Angle - dblLeftRotation * IIf(bolLeftFlipped, iFlip, 1)
    
17.         dX = .X + .Length * Cos(.Angle)
    
18.         dY = .Y + .Length * Sin(.Angle)
    
19.     End With
    
20.     With arrVertex(nChild)
    
21.         .X = dX: .Y = dY
    
22.         .Length = dLength * Sqr(2) / 2
    
23.         .Angle = dAngle + dblRightRotation * IIf(bolRightFlipped, iFlip, 1)
    
24.         .Next = nNext
    
25.     End With
    
26. End Sub
    
27. Private Sub Output(ByVal iIndex%, Optional bWait As Boolean = False)
    
28.     Dim i&, n&
    
29.     i = 1
    
30.     Do
    
31.         With arrVertex(i)
    
32.             arrOutput(n, 0) = .X: arrOutput(n, 1) = .Y: i = .Next
    
33.         End With
    
34.         n = n + 1
    
35.     Loop Until i = IIf(bolEndPoint, -1, 0)
    
36.     n = intPatternCount
    
37.     If bolShadow Then n = n * 2 + 1
    
38.     n = n - iIndex
    
39.     shtData.Range("A2").Offset(0, n * 2).Resize(UBound(arrOutput) + 1, 2) = arrOutput
    
40.     If bWait Then WaitMoment Moment
    
41. End Sub

复制代码

lee1892

三、线的多次折弯

本贴附件： 奇妙的分形 之 线的多次折弯_By Lee1892.rar (42.09 KB, 下载次数: 474)

2013-12-2 13:35 上传

点击文件名下载附件

更为普遍的，对线的多次折弯。

前面提到的歇尔宾斯基三角形可以如下图这样来模拟，这种折弯形式被称为歇尔宾斯基箭头曲线（Sierpinski Arrowhead Curve）


如果有去看顶楼提到的雪花那个帖子，那么对于下面这个图案肯定不会陌生，科赫雪花曲线（Koch Snowflake Surve）


此贴附件可以实现如下功能：
1、随意设定每次折弯的次数，以及每次折弯各新向量的角度、变形系数、是否翻转
2、可以保存预设参数
...

此附件预设的几个参数产生的图案如下：

顶楼附件也可产生倒数第二个的效果：


由于参数设置十分开放，可以生成很多稀奇古怪的图案来，比如下图就像是自然生长的灌木：


预存设置漏了一个：

lee1892

四、阿波罗分形垫（Apollonian Gasket）

此帖附件： 奇妙的分形 之 圆_By Lee1892.rar (179.47 KB, 下载次数: 516)

2013-12-5 15:49 上传

点击文件名下载附件

对于任意3个互相相切的圆（C1、C2、C3），必然可以确定另外2个圆（C4、C5），这2个圆与原来的3个圆都相切。
于是形成两组：C1、C2、C3、C4 和 C1、C2、C3、C5
以第一组为例，按前面的描述，C1、C2、C4 互相相切，则可以确定另一个圆与它们相切且不是C3，记为C6；同理，对于C1、C3、C4则可以确定C7；对C2、C3、C4可以确定C8。继续循环，就可以得到被称为阿波罗分形垫的图形。


附件的代码，是一个不成熟的阿波罗分形垫生成：
1、没有排除数字过小时的浮点计算误差
2、当初始值（三个圆的半径）相差较大时，不能排除计算很小的圆，而导致较大的圆由于计算方法的限制很靠后，而没有计算
3、对一些值存在圆心计算错误，导致输出图形错误

代码的算法涉及一些基本的三角函数知识、基本的笛卡尔坐标系的线性转换、三圆相切求另两个相切圆的半径的Descartes定理（曲率计算）等。

lee1892

五、正多边形的分形

此贴附件： 奇妙的分形 之 正多边形_By Lee1892.rar (181.76 KB, 下载次数: 473)

2013-12-6 14:14 上传

点击文件名下载附件

前面曾反复提到谢尔宾斯基三角形，其原理是由一个正三角形在其三个角上各生成一个边长1/2大小的小三角形，如下图动画：


推而广之，可以将这个方法应用到所有正多边形上，比如下图的正四边形：


可以注意到，在边数N多于3个的时候，还可以生成第N+1个正多边形位于正中，于是有下图的效果，图中分别是正三角形到正10边形，有、无中心的分形：


细心如你一定注意到对于正六边形不生成中间的时候，其中间围合成的形状是十分熟悉的，就是前面提到的那个雪花的图案。

附件中，设置了变形系数的参数（该参数的输入值是其倒数，即变形系数=1 / 输入值，输入值不大于 1 时，代码计算为相邻分形恰好接触），采用不同的参数还会得到一些其它的图样，比如下图：

lee1892

六、随机的分形：对自然的模拟

本贴附件： 奇妙的分形 之 3分枝的一定随机_By Lee1892.rar (183.11 KB, 下载次数: 416)

2013-12-9 16:33 上传

点击文件名下载附件

追加附件： 奇妙的分形 之 随机模拟树_By Lee1892.rar (178.15 KB, 下载次数: 475)

2013-12-10 09:44 上传

点击文件名下载附件

继续追加： 奇妙的分形 之 彩色的随机模拟树_By Lee1892.rar (214.07 KB, 下载次数: 521)

2013-12-11 10:35 上传

点击文件名下载附件

人们在数学概念上意识到分形不过是在上世纪70年代的事，但我们早就注意到了自然界的这种现象，微观的分子结构，小的蜗牛壳，一片雪花，一棵花菜，一片树叶，一棵树，一座山脉，一条海岸线，无不可以看作某种意义上的分形。

前面提到的种种简单的几何分形都是规律的，然而自然界中事物总是变化纷繁的，我们都知道没有两片雪花是相同的。所以人们在用分形技术模拟自然界中的事物时，会引入一些随机变量，这会产生一些非常有趣的事情。

我不打算为前面的每一个附件都设计一个随机规则，仅仅以第一个 分枝 为例，让我们用它来模拟一棵树。显然树的生长是三维的，我们来模拟其在二维空间的投影的图案。

附件是这样来模拟的：
1、树的每一次生长意味着产生一个分支节点，只产生不超过3个分支，左、中、右
2、在分支节点，主干是肯定继续生长的，所以中间分支必然存在，可能存在左分支或则右分支或则左右都有
3、中间分支基本沿原来的方向继续生长，但可能偏左或偏右，同时其长度可能比标准比例大或小
4、左右分支也同样存在中间分支的角度和长度上的偏差

于是有这样的一个参数界面


然后我们可以改变参数，生成各种各样的树来，是不是很酷呢~


======================================

追加了一个附件，可以模拟树粗细、同节点左右分支的起始点会有偏差（显得更自然一些），有兴趣的可以分列生成的数据进行上色处理就会更像是真实的树了{:soso_e104:}：



======================================
继续追加附件，按各分枝的宽度对生成的数据分列，并对各列数据上色。Excel的图表色彩太单调了~
现在的界面减少了一些参数，而实际上可以更改代码，把一些东西统统变为参数，宽度、宽度的分形比例、分支节点的偏移量、色彩的分布、向上方生长或是向两侧生长的可能性。。。等等


现在看上去就更酷了~~~~

好吧，这一段看上去更像是代码的演进的示例~

======================================
3维的模拟树，网上找的：


分形模拟地形的示意：


商业软件利用分形技术制作的地貌：

lee1892

七、一些知识准备

可能会有人去看了顶楼的那个一片漂亮的叶子的帖子，并疑惑于这样的有规律的随机数据是如何产生的，其背后又有着什么样的数学规律。

想要了解个大概的话，可以看看下面的一些内容，或则只是关心好看的效果的话，这一段完全可以跳过~

1、先复习一下复数、复平面

为解决 x^2 = -1，实数显然无解，人们引入了虚数的概念，x = ± 1 * i，这里的 i 表示虚数，于是有了复数的概念 z = x + y*i，其中 x 为实部、y 为虚部。

所有复数的集合就可以构成复平面，与笛卡儿坐标系类似的，y轴表示虚部，x轴表示实部，任何一个复数都可以在复平面上找到一个对应的点。

2、度量空间 Metric Space

度量空间是一个集合，在其中可以定义在这个集合内的元素之间的 “距离”（称为 度量）的概念。最为直观的是三维欧几里得空间，欧几里得度量 定义了两个点之间的距离为其连线的长度。

可以把一个度量空间表达为一个二元组 (M, d)，这里 M 是集合，而 d 是在 M 上的 度量，即一个函数
d : M × M → R

3、压缩映射 Contraction Mapping

度量空间 (M,d) 上的压缩映射，是一个从 M 到它本身的函数 f，存在某个实数 0<k<1，使得对于所有 M 内的 x 和 y，都有：
d(f(x),f(y)) ≤ kd(x,y)

满足以上条件的最小的 k 称为 f 的利普希茨常数（Lipschitz Constant）。

一个压缩映射最多有一个不动点。另外，巴拿赫不动点定理（Banach Fixed Point Theorem）说明，非空的完备度量空间上的每一个压缩映射都有唯一的不动点，且对于 M 内的任何 x，迭代函数序列 x, f(x), f(f(x)), f(f(f(x))), ... 收敛于不动点。

4、仿射变换与变换矩阵 Affine Transformation & Transformation Matrix

在几何中，一个向量空间进行一次线形变换并接上一个平移，变换为另一个向量空间。

在线形代数中，线形变换嫩够用矩阵表示。如果 T 是一个把 R1 映射到 R2 的线形变换，且 x 是一个具有 n 个元素的列向量，那么
T(x) = Ax
m×n 的矩阵 A，称为 T 的变换矩阵。

更多变换矩阵的知识，可参考 中文WiKi：http://zh.wikipedia.org/wiki/%E5%8F%98%E6%8D%A2%E7%9F%A9%E9%98%B5

5、复合函数 Composition Function

在数学领域，两个函数的复合函数指将第一个函数作用于参数，然后再将第二个函数作用于所得结果的函数。具体来说，给定两个函数 f: X → Y 和 g: Y → Z，其中 f 的陪域等于 g 的定义域（称为 f、g 可复合），则其复合函数记为 g ○ f，以 X 为定义域，Z 为陪域，并将任意 x∈X 映射为 g(f(x))。

函数的复合满足结合律：若 f、g可复合，g、h 可复合，则有：
h ○ (g ○ f) = (h ○ g) ○ f

============================================
顶楼的那个叶子的图案被称为 Barnsley's Fern，使用了 4 个仿射变换，一个变换的矩阵公式为：

如果你对矩阵计算熟悉的话就会知道上面的这个公式对应了两个等式：
x = a * x' + b * y' + e
y = c * x' + d * y' + f
上式中，x'、y’ 为上一次迭代计算的结果。

Barnsley's Fern 的参数表如下：

w	a	b	c	d	e	f	p
f1	0	0	0	0.16	0	0	0.01
f2	0.85	0.04	-0.04	0.85	0	1.6	0.85
f3	0.2	-0.26	0.23	0.22	0	1.6	0.07
f4	-0.15	0.28	0.26	0.24	0	0.44	0.07

其中，p 表示的是可能性，即每次迭代计算中，采用 4 种变换中的某一种的可能性。

对应的矩阵变换如下：









如果愿意的话，可以计算一下上面四个变换的不动点，具体办法可参考 巴拿赫不动点定理。

================
以上内容均来自中文或英文 WiKi。

lee1892

八、德拉姆曲线 De Rham Curves 0到1的舞蹈

18楼有更新噢~

本贴附件： 奇妙的分形 之 DeRham曲线_By Lee1892.rar (174.98 KB, 下载次数: 350)

2013-12-14 13:57 上传

点击文件名下载附件

考察一个度量空间 (M,d)，和它的一个 M 上的压缩映射：
d0: M → M
d1: M → M

由巴纳赫不动点定理，它们存在两个不动点，记为 p0 和 p1。设实数 x ∈ [0,1]，并且其二进制扩展表达为：
x = SUM (bk / 2^k) <k=1~∞, bk = 1 或 0>

这时，有：
cx: M → M
其度量函数为：
cx = db1 ○ db2 ○ ... ○ dbk ○ ...

可以发现每一个 cx 都将 d0 和 d1 的普遍吸引域映射到 M 上的一个点，记为 px。由一个实参 x 获得的所有 px 的集合，被称为 德拉姆曲线。

德拉姆曲线连续的条件：
d0(p1)=d1(p0)

嗯，这一段确实太抽象了点儿。接下来的几个实例可以帮助我们稍微形象点儿的理解它。

1、Césaro 曲线
其两个不动点为 p0 = 0 和 p1 = 1，不同的 Césaro 曲线是由一个复数 a（a = α + β i）来定义的，|a| < 1  且 |1-a| < 1 （复数的绝对值是其在复平面上代表的点距离原点的距离，即 |z| = sqr(x^2 + y^2) ）。

其压缩映射的两个度量函数被定义为复平面上的两个复函数：
d0(z) = az'
d1(z) = a + (1 - a)z'
其仿射变换为：


a = 0.3 + 0.3 i

a = 0.5 + 0.5 i 就是 莱维C曲线


2、Koch-Peano 曲线
类似的，将上述函数中的变量换为其共轭复数（复数的共轭：z = x + y i 与 z = x - y i 共轭，没有上划线用下划线表示共轭），就变成了 Koch-Peano 曲线了。
d0(z) = az'
d1(z) = a + (1 - a)z'
其仿射变换为：



a = 0.5 + √3 / 6 i 为 Koch 雪花曲线

a = 0.5 + 0.5 i 为 Peano 曲线 （不好看，不贴了）
a = 0.6 + 0.37 i

a = 0.6 + 0.45 i


3、德拉姆 曲线 的一般化
按上述的仿射变换公式，显然一般化的形式如下：

式中包括了全部的向量的线性变化：旋转、偏移、放大缩小等。

由前述的设定，对于 d0 取不动点 p0 = 0 则有 a = d = 0，对于 d1 取不动点 p1 = 1 则有 j = 1 - h 及 m = -l。而由 德拉姆曲线连续的条件 d0(p1)=d1(p0)，可得 h = b 及 m = e。将这些变量换以希腊字母，就可以获得 德拉姆曲线的公式：




补充内容 (2014-10-25 00:48):
连续的德拉姆曲线见：http://club.excelhome.net/forum. ... 988&pid=7906838

lee1892

九、Barnsley Fern 与 IFS (Iterated Function System)

本贴附件： 奇妙的分形 之 叶子与IFS By Lee1892.rar (38.3 KB, 下载次数: 413)

2014-9-25 16:10 上传

点击文件名下载附件

前面第七节提到了Barnsley Fern的计算方法，这种迭代计算的模式被称为 IFS，其计算是对矩阵的仿射变换。

此附件添加了数个人为设置的参数，能形成如下的图案：


同时，还增加了4个自动生成随机参数的选项，这4个随机生成的方法简单的设置了不同的限制，但并不是按仿射变换的旋转、偏移、缩放来设置规则的。
效果如下：


当然，需要指出的是虽然附件中的全部实现都只涉及4个仿射变换，但实际上变换数量并不受限制。

lee1892

此贴我不再加内容了，或许会另外开贴。

作了个目录如下，希望有看到且有权力编辑帖子的能帮我放到顶楼最前面。

目录
序号	名称	附件
一	[01楼] 分枝	奇妙的分形 之 分枝
二	[02楼] 线的一次折弯	奇妙的分形 之 线的一次折弯
三	[04楼] 线的多次折弯	奇妙的分形 之 线的多次折弯
四	[05楼] 阿波罗分形垫（Apollonian Gasket）	奇妙的分形 之 圆
五	[12楼] 正多边形的分形	奇妙的分形 之 正多边形
六	[18楼] 随机的分形：对自然的模拟	奇妙的分形 之 3分枝的一定随机 奇妙的分形 之 随机模拟树 奇妙的分形 之 彩色的随机模拟树
七	[21楼] 一些知识准备
八	[24楼] 德拉姆曲线 De Rham Curves 0到1的舞蹈	奇妙的分形 之 DeRham曲线
九	[42楼] Barnsley Fern 与 IFS (Iterated Function System)	奇妙的分形 之 叶子与IFS

TFQWFN

下载学习了

840205910

太高深了，学习不了。也不知道在什么领域运用得到。

840205910

表面看起来代码好像不复杂的

网名

楼主真是高手，太高深了，在什么领域运用得到？

ammyc

好好学习，天天向上

longming3

可以用vba开发类似游戏了