分形几何 计算机科学与技术系.

Presentation on theme: "分形几何 计算机科学与技术系."— Presentation transcript:

1 分形几何 计算机科学与技术系

2 概述 一种粗糙或零碎的几何形状 几何形状可以分成若干个小部分，每一部分是整体形状的放大或缩小，即具有自相似的“层次”结构
在理想情况下，甚至具有无穷层次放大或缩小。适当的几何尺寸，整个结构并不改变。 分形（fractal）

3 分形几何的产生 1970s，美籍法国数学家B.B.Mandelbrot 在美国《科学》杂志上发表了划时代的论文中
探讨了“英国的海岸线有多长?”这个问题。 不同标度单位： r =1km L1 r =1m L2 L1<L2 11450km 使用较长或最小的尺度都是没有意义的，在这两个自然限度之间，存在着可以变化许多个数量级的“无标度”区，长度不是海岸线的定量特征。

4 分形几何的产生 英国海岸线是个确定值 - 11450km 表明海岸线不能用欧几里德的几何学中的传统标度“长度”去度量 提出了一个分形数学术语
研究一类现象特征的新的数学分科 分形理论是非线性科学的前沿和重要的分支 应用于非规则几何形态-分形几何

5 分形的基本特性 自相似性 局部与整体在形态、功能、信息、时间、空间等方面具有统计意义上的相似性，称为自相似性。
自相似性可以用计算机的递归模型描述。 无标度性 标度是计量的单位，如：长度-- 米，面积– 平方米 分形是无标度的，人们不能用通过长度、面积等标度来描述分形

6 分形与计算机图形学-分形图形学 分形是一种数学术语，以分形特征为研究内容的数学理论。 分形几何是一门以不规则几何形态为研究对象的几何学。
分形几何学与计算机图形学相结合，将会产生一门新的学科——分形图形学。它的主要任务是以分形几何学为数学基础，构造非规则的几何图素，从而实现分形体的可视化，以及对自然景物的逼真模拟。 在图形学领域主要是利用迭代、递归等技术来实现某一具体的分形构造。

7 分形图形学

8 分形的定义 一般认为，满足下列条件的图形称为分形集 分形集具有任意尺度下的比例细节，或者说具有精细结构。
分形集是不规则的，以至于不能用传统的几何语言来描述。 分形集通常具有某种自相似性，或许是近似的或许是统计意义下的自相似。 分形集在某种方式下定义的“分维数”一般大于它的拓扑维数。 分形集的定义常常是非常简单的，或许是递归的。

9 分形维数的定义 维数是几何对象的一个重要特征量
在欧几里德几何中，直线或曲线是1维的，平面或球面是2维的，具有长、宽、高的形体是 3 维的。习惯上将整数维数称为“拓扑维数”。 对于分形图形，如海岸线、Koch曲线、射尔宾斯基（Sierpinski）垫等的复杂性无法用维数等于 1、2、3 这样的数值来描述。 Koch曲线 分维的计算公式 N：与整体自相似的局部个体的个数 S：相似比，等于整体和局部之比 射尔宾斯基垫 据说，南非海岸线的维数是1.02，英国海岸线的维数是1.25。

10 分形维数的定义 分数维数与欧氏几何学中的整数维数相对应 N=2，S=2，即2=21. D=1.0 二叉树
四叉树 N=8，S=2，即8=23. 分维D=3.0 N：与整体自相似的局部个体的个数 S：相似比，等于整体和局部之比 八叉树

11 递归模型 – Koch曲线 Koch曲线是象雪花一样，被称为Koch雪花。 设想从一个线段开始，根据下列规则构造一个Koch曲线：
1．三等分一条线段； 2．用一个等边三角形替代第一步划分三等分的中间部分； 3．在每一条直线上，重复第二步。 Koch曲线的长度为无穷大，因为以上的变换都是一条线段变四条线段，每一条线段的长度是上一级的1/3，因此操作n步的总长度是(4/3)n：若n→∞，则总长度趋于无穷。Koch曲线的分形维数是ln 4/ln 3 ≈ 1.26，其维数大于线的维数。

12 Koch曲线-初始元设计 Koch(ax,ay,bx,by,m) ax,ay（线段端点坐标） bx,by（线段端点坐标）
cx,xy （线段端点坐标） dx,dy（线段端点坐标） ex,ey （线段端点坐标） L （线段长度） alpha （基线与水平线正方向夹角）

13 Koch(ax, ay, bx, by, c) { if (m>0) //m递归次数 cx=ax+(bx-ax)/3; cy=ay+(by-ay)/3; ex=bx-(bx-ax)/3; ey=by-(by-ay)/3; L=sqrt((ex-cx)*(ex-cx)+(ey-cy)*(ey-cy)); alpha=atan((ey-cy)/(ex-cx)); if ( (ex-cx)<0) alpha = alpha+ PI; //PI= 3.14 dy = cy+sin(alpha+PI/3)*L; dx = cx+cos(alpha+PI/3)*L; Koch(ax, ay, cx, cy, m-1); Koch(ex, ey, bx, by, m-1); Koch(cx, cy, dx, dy, m-1); Koch(dx, dy, ex, ey, m-1); } else{ draw(ax, ay, bx, by}} void draw(GLfloat x0, GLfloat y0, GLfloat x1, GLfloat y1) { static int i = 0; glBegin(GL_LINES); glColor3fv(colors[i++ % 4]); glVertex2f(x0, y0); glVertex2f(x1, y1); glEnd(); }

14 Koch雪花 Alpha=60 Alpha=30 递归 n=4

15 初始元 初始元

16 L系统模型 美国科学家Aristid   Lindenmayer于1969年为把形式语言理论应用到生物学中，创立了一种并行重写系统。它是描述生物体生长发育过程的数学理论，称作Lindenmayer系统，简称L系统(L-system)。 1984年A.R.Smith首次将L系统应用于计算机图形学中，L系统用于植物生长过程的模拟是非常成功的，为计算机真实感图形的绘制提供了又一个有力的工具。

17 L系统的文法模型 L系统实际上是一组形式语言，由特定的语法加以描述。
字母表：使用到的字母； 公理：初始字符串； 生成规则：字符串的变换形式； 例如，初始字母：F ，生成规则：F->FF[++F-F-F][-F+F+F]

18 L系统的绘图规则-龟形图法 常采用“龟形图法”对L系统进行图形说明。
设想有一只乌龟在海滩上爬行，其当前状态用三个参数描述，记为S(x ,y ,α)，其中x , y 为乌龟所在位置的直角坐标，α为乌龟爬行的方向。假定乌龟爬行的步长为d，在爬行方向α上的角度改变量为θ。 d + θ - θ （1）F：向前爬行一步d并画线。 乌龟从状态S（x , y , α）移动到状态S'（x'，y'，α） 从（x，y）向（x'，y'）画一条线。

19 L系统的绘图规则-龟形图法 （2）＋：逆时针旋转θ角，龟的新状态为S'(x', y', α+θ)；
（4）[ ：将当前乌龟爬行的状态压入堆栈，信息包括乌龟所在的位置与方向等，但不画线； （5）] ：从堆栈中弹出一个状态作为乌龟的当前状态，但不画线； d + θ - θ

20 L系统-Koch曲线 绘图规则： （1）F：生成元最小线元长度，步长为d。 （2）＋：逆时针方向旋转θ角。 （3）－：顺时针方向旋转θ角。
文法模型： 字母表为：F，＋，－ 初始字母为：F 生成规则：F→F＋F――F＋F 迭代结果如下: 迭代0：F 迭代1：F＋F――F＋F 迭代2：(F＋F――F＋F) ＋ (F＋F――F＋F) ―― (F＋F――F＋F) ＋(F＋F――F＋F) … +θ -θ F +θ -θ F

21 L系统-分形草 F：代表主干和旁支，龟爬行步长 +：树生长方向，逆时针旋转为正 - ：树生长方向，顺时针旋转为负 [ ：存储分支点
] ：释放分支点 F 例： 初始字母：F，旋转角度θ 生成规则： F->FF [++F-F-F][-F+F+F] 文法模型 绘图规则

22 随机LS算法实现 void LSystemRule() //生成规则 { //初始化 way[0] = "F[+F]F[-F]F";
way[2] = "FF-[--F+F+F]+[+F+F-F]"; len = 0.5; Alpha = 25; n = 5; stackpointer = 0; for (int i = 0; i <150; i++) {stack[i].point.x = 0; stack[i].direction = 0;} rule = way[rand() % 3]; for (int i = 1; i <= n; i++) int curlen = temprule.length(); int pos = 0, j = 0;

23 while (j < curlen) { if (temprule[j] == 'F') rule += way[rand() % 3]; j++; pos = rule.length() - 1; } else rule += temprule[j]; pos++; } //endwhile temprule = rule; rule.clear(); } //endfor rule = temprule;

24 //绘制 while (i < length) { switch (rule[i]) case 'F': Nextnode.point.x = Curnode.point.x + len * cos(Curnode.direction * PI / 180); Nextnode.point.y = Curnode.point.y - len * sin(Curnode.direction * PI / 180); Nextnode.direction = Curnode.direction; glBegin(GL_LINES); glVertex2f(Curnode.point.x, Curnode.point.y); glVertex2f(Nextnode.point.x, Nextnode.point.y); glEnd(); Curnode = Nextnode; break;

25 case '[': stack[stackpointer] = Curnode; stackpointer++; break; case ']': Curnode = stack[stackpointer - 1]; stackpointer--; case '+': Curnode.direction = Curnode.direction + Alpha; case '-': Curnode.direction = Curnode.direction - Alpha; default: ; } i++;

26 Peano-Hilbert曲线 Peano-Hilbert曲线的特点是单入单出，需要两个生成规则的嵌套来实现。
绘图规则： (这里取θ＝90°) （1）F：向前移动一步，步长为d。 （2）＋：逆时针旋转θ角。 （3）－：顺时针旋转θ角。 文法模型： 字母表为：F，＋，－，X，Y。 初始字母为：X 。 生成规则1为：X→－YF＋XFX＋FY－ 生成规则2为：Y→＋XF－YFY－FX＋ 生成规则1 生成规则2

27 Peano-Hilbert曲线 迭代结果如下： 迭代0：X 迭代1：－YF＋XFX＋FY－
迭代2：- (XF－YFY－FX＋)F＋(－YF＋XFX＋FY－) F (－YF＋XFX＋FY－)＋F(＋XF－YFY－FX＋)－ … 注： 本文法模型中，X和Y只进行字符串的替换，不用于绘图，只根据F、＋，－绘图。

28 IFS迭代函数系统模型 迭代函数系统（Iterated Function System，IFS）是分形理论的重要分支。它将待生成的图像看成是由许多与整体相似的（自相似）或经过一定变换与整体相似的（自仿射）小块拼贴而成。

29 仿射变换 相似变换：如果对于任意两点A、B，以及对应点A’、B’，总有A’B’=k·AB（k为正实数），那么，这个变换叫做相似变换，实数k叫做相似比。它只是改变大小、位置和方向 仿射变换：x’ = ax+by+e y’= cx+dy+f 其中a,b,c,d,e,f为仿射变换系数。 仿射变换是一种线性变换，它具有将图形放大、缩小、平移和旋转的性质。 不断地重复应用仿射变换就是一个迭代过程。 仿射变换性质：平直性和平行性

30 仿射变换矩阵的分解 仿射变换可以理解为对坐标点进行比例，旋转，平移等变换后取得的新坐标值。 仿射变换矩阵 可以分解为平移变换矩阵
、比例变换矩阵 、旋转变换矩阵 等的组合。 矩阵相乘的次序由具体的仿射变换确定。

31 压缩仿射变换 迭代系统只能使用压缩仿射变换，原图形上的各点经过仿射变换后，各点之间距离变小，这种仿射变换称为压缩仿射变换。
x’=a1·x+b1·y+e y’=c1·x+d1·y+f1 w1 x’=a2·x+b2·y+e y’=c2·x+d2·y+f2 w2 x’=a3·x+b3·y+e y’=c3·x+d3·y+f3 w3 p1 p2 p3 用多个压缩仿射变换式表达一个图形w1, w2, w3, ……，使用每一个仿射变换式的概率p可以不同，一般面积越大，p值越大。于是，只要获得a, b, c, d, e, f, p（IFS码）的值便可以得到要表达的图形。概率p称为伴随概率。 p1+p2+p3=1

32 Sierpinski垫片 在1915～1916年间，波兰数学家Sierpinski (Waclaw Sierpinski ，1882～1969)将三分Cantor集的构造思想推广到二维平面，构造出千疮百孔的垫片与地毯。 生成规则：取一等边三角形,连接各边中点将原等边三角形等分成4个小等边三角形，然后舍弃位于中间的一个小等边三角形,将剩余3个小等边三角形按同样方法继续分割，并舍弃位于中间的那个等边三角形。如此不断地分割与舍弃，就能得到中间有大量孔隙的Sierpinski垫片。

33 Sierpinski垫片的IFS生成 由于生成的三个小三角形的面积相等，所以我们可以让w1、w2、w3出现的概率相同或相近。
x’=0.5x+0.25 y’=0.5y-0.5 x’=0.5·x+0·y+0 y’=0·x+0.5·y+0 x’=0.5·x+0·y+0.5 x’=0.5·x+0·y+0.25 y’=0·x+0.5·y-0.5 w1 w2 w3 由于生成的三个小三角形的面积相等，所以我们可以让w1、w2、w3出现的概率相同或相近。 x’=0.5x y’=0.5y x’=0.5x+0.5 y’=0.5y

34 1：边长为原三角形的一半，即只进行比例变换
2：向右平移1/2，边长为原三角形的一半。 3：向右平移1/4，向上平移1/2，边长为原三角形的一半。

35 IFS码 取伴随概率为1/3，这样就得出了Sierpinski垫片的IFS码

36 IFS生成算法 long n =100000;（迭代次数） x=y=0; float m[7][7]={0};（存储IFS码值）
float a,b,c,d,e,f,p;（IFS码变量） { //IFS码赋值 W1 m[0][0]=0.5; m[0][1]=0; m[0][2]=0; m[0][3]=0.5; m[0][4]=0; m[0][5]=0; m[0][6]=0.333; //W2 m[1][0]=0.5; m[1][1]=0; m[1][2]=0; m[1][3]=0.5; m[1][4]=0.5; m[1][5]=0; m[1][6]=0.333; //W3 m[2][0]=0.5; m[2][1]=0; m[2][2]=0; m[2][3]=0.5; m[2][4]=0.25; m[2][5]=0.5; m[2][6]=0.334;

37 while (n > 0) { p = (float)rand()/RAND_MAX; if (p <= m[0][6]) { a = m[0][0]; b = m[0][1]; c = m[0][2]; d = m[0][3]; e = m[0][4]; f = m[0][5]; } else if (p <= m[0][6] + m[1][6]) { a = m[1][0]; b = m[1][1]; c = m[1][2]; d = m[1][3]; e = m[1][4]; f = m[1][5]; else if (p <= m[0][6] + m[1][6] + m[2][6]) { a = m[2][0]; b = m[2][1]; c = m[2][2]; d = m[2][3]; e = m[2][4]; f = m[2][5]; else { a = m[3][0]; b = m[3][1]; c = m[3][2]; d = m[3][3]; e = m[3][4]; f = m[3][5]; x1 = (a * x) + (b * y) + e; y1 = (c * x) + (d * y) + f; x =x1; y =y1; pDC->SetPixelV(( * x)/15, ( * y)/15, RGB(x * p, p * 100, y * p)); n--; }

38 Sierpinski垫片

39 Sierpinski垫片

40 枫叶拼贴 对于规整的图形，可以明显地找出几何关系来确定相应的IFS码，而对于不规整的图形（如枫叶），常采用拼贴的方法获得其IFS码。

41 枫叶拼贴 给定6个点，可以列出如下6 个方程，解方程组求得变换系数a，b，c，d，e，f，就可以确定一个仿射变换。 （x1，y1）

42 枫叶拼贴 将6个特征点分别代入公式。 得到 针对拼贴的每一片枫叶求解线性方程组计算一组仿射变换系数a,b,c,d,e,f。

43 IFS生成的植物形态

44 Sierpinski地毯-递归方法 生成规则：取一正方形。将每条边三等分，正方形被等分为9个面积相等的小正方形，舍弃位于中间的一个小正方形。将剩下的8个小正方形按上面同样的方法继续分割，并舍弃位于中间的小正方形。如此不断地分割与舍弃，就能得中间有大量空隙的Sierpinski地毯。 n =1 n =0 n =2 n =4

45 Menger海绵 Menger海绵是由奥地利数学家Menger(Karl Menger，1902～1985)于1926年提出的一种分形曲线。

46 Menger海绵生成元