Iteration and Fractals | XiangSiqi’s Blog

type

Post

status

Published

date

Nov 11, 2025

slug

CP2

summary

Iterations and Fractals

Fractal Tree

normal fractal tree

基本思路是，对于两个点，我们首先取连线的三分之一点和三分之二点，然后在这两个点分叉，即按照某个角度伸出1/3长度，这样会产生5个线段，6个点，又对这5个线段执行同样的操作，这样不断扩张，形成分形树。

我们中心函数是分叉函数，输入线段，传出5个线段，所谓线段，应该看作是点对，因此，传入一个点对，传出5个点对：

我们要考虑点对的类型是两个np.array的二维行向量构成的二维行向量，传出的5个点对就是两个点构成的5*2的np.array数组。

现在我们开始考虑点生成，首先，对于两端的点A,F，可以直接计算：

然后考虑枝干，我们考虑利用旋转，即将DB线段逆时针旋转，将DF线段顺时针旋转，首先我们要考虑旋转矩阵：

然后我们就可以直接计算：

这就是最后的两个点，我们根据几何关系组成5个点对：

这样就完成了一次迭代，我们需要一个流程，执行这个函数，将单次执行的结果拼到一起，作为一个epoch的集合，并作为下一次epoch的出发点。

最后我们只需要把每一个pair的点连起来就可以了：

得到：

或许还有一种思路是是，考虑每一条线段的分发都直接加到队列中，并迭代分发各个线段：

complex fractal tree

现在开始考虑在复平面做这件事，从而提高计算速度。方法就是把点写成复数形式，把旋转矩阵写成，其他的相似，结果如下：

绘制时取实部和虚部即可。可以测试计算速度更快：

并且矩阵更小

Vectorization or Insertion

考虑向量化，对于个的矩阵，是已经有的样本点数，可以直接计算它们的分形点集：

Self Similarity

即然分形是自相似的，我们就可以考虑完全复制自己，即对自己做缩小，旋转。

我们需要考虑分形的一些理论，首先是1个点对，然后是5个点对，然后是个点对等等。我们的思路是，将个点对的前个点给缩小后的上一个版本，到个点向左旋转度数，以此类推。

由于先验知识的使用，该方法的效率极高。

Recursion

考虑在两点之间构造一个深度为N的分形，就是在这个两点的5个分线段中构造一个深度为N-1的分形，于是这就是迭代：

Odd or Even

刘震在这些方法中都不把一根线的一组点看作一个2维向量，而是将它们并排在一起，并且利用奇偶索引去访问它们，尽管这种方法可能很不直观。

这样在最基本的方法里，对于初始化矩阵是的，第一次分形后是的，第次分形之后是的。于是思路是，偶数索引是向量起点，奇数索引是向量终点，迭代点数的一半（一组一组迭代），这样产生的新的点就按照线段规则直接加载原来的集合后面。

这种思路同样继承到了复数法，矢量法（或者他成为插值法，因为它把每个分形都插到了对应位置而不是直接在后面添加）和自相似法。

Sierpinski Triangle

Complex Method

我还是先按照自己的思路来，一个基本的思路是，传入一个三角形，切分，涂色，然后传出三个三角形，仍然需要一个外部流程来反复迭代传入传出。

但是刘震不愧是面向过程编程的信徒，他会考虑，当三角形绘制时，应当只绘制出最后制作的那一批三角形。而三角形的制作同样通过遍历已有的的三角形来完成，但是他会意识到，可以通过类似滑动卷积行为来完成，当产生三角形后，只需要移动选中即可制作下一个三角形。

Insertion Method

同样考虑插值法，对于已有的三角形，我们扩大三倍，插入指标即可。

Similarity

同样，结构上也是相似的。

Recursion

如果你要在一个三角形内进行N次迭代，这等价于在内部的3个三角形做N-1次迭代，即递归，当N-1=0时，递归结束。

Koch Snowflake

Ordinary Method

科赫雪花的逻辑更为简单，只需要从一个向量的1/3点让1/3长度朝着固定方向旋转60度，然后得到4个向量，做相同的操作即可：

结果为：

Recursion

所以你毫不费力想到这件事可以用迭代来做：

所谓迭代就是演示一次。

Loop and Insertion

科赫雪花一个重要的特征是它是一个环路，这意味着当给我们一系列点时，我们只需要沿着路径迭代即可。

值得注意的是末端是无法迭代到的，方法是在向量后面手动补上那个点

Vectorization

容易向量化为：

Self Similarity

同样考虑自相似，只不过考虑一个边，可以制造任意depth的单边，然后通过旋转拼成三角形。

Complex Functions and Iterations

Julia Set

Julia集定义为，对于迭代过程

在次迭代后，仍有，则称属于Julia集。如果在次迭代后，，则该点逃逸

我们绘制Julia集的要求是，根据逃逸时的迭代次数分组分颜色绘制。

因此首先是需要遍历一个连续区间的复数点，在次迭代后，有点逃逸，我们需要创建一个矩阵来记录此时的迭代次数，并且再创建一个矩阵来标记已经逃逸，此后不再记录。

这样做仍然是复杂的，刘震的思路是，一直更新矩阵，直到逃逸。

得到

Mandelbrot Set

Mandelbrot集定义为，对于迭代过程：

如果次迭代以后，，那么就属于Mandelbrot集。思路基本相似：

Fractals and Fractal Dimensions

Hausdorff Dimension

边长为的线段，放大2倍之后的长度为，放大2倍；边长为的正方形，放大2倍之后的面积为，放大4倍；边长为的立方体，放大两倍之后的体积为，放大8倍，得到一般规律，为边长放大的倍数，为边长、面积、体积的放大倍数，于是：

成为Hausdorff维数。

例如对于Sierpinski triangle，边长放大2倍，则三角形面积扩大4倍，但是中心三角形不算，故，（对于depth>1的也成立吗？）则：

意味着它不是二维图形。

Similarity Dimension

考虑某个几何体由个局部，每个局部以相似比与整体相似，则相似维数为：

Koch雪花每条边有4个相似图形，相似比为1/3（请回忆Koch的生成过程），因此：

Minkowski–Bouligand Dimension

前面都适用于完全自相似的图形，而Minkowski–Bouligand维数，或称为盒维数，可以适用于不是完全自相似的图形。

它的算法是，将测量对象放到网格空间，网格的单位长度是，对象占据的最小的网格数为，盒维数定义为：

这一表达式意味着，当网格缩放时，发生变化，作成双对数曲线应该是一条直线，直线的斜率就是盒维数。

对于离散缩放：