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

Slides:



Advertisements
Similar presentations
一、 一阶线性微分方程及其解法 二、 一阶线性微分方程的简单应用 三、 小结及作业 §6.2 一阶线性微分方程.
Advertisements

第五节 函数的微分 一、微分的定义 二、微分的几何意义 三、基本初等函数的微分公式与微分运算 法则 四、微分形式不变性 五、微分在近似计算中的应用 六、小结.
2.8 函数的微分 1 微分的定义 2 微分的几何意义 3 微分公式与微分运算法则 4 微分在近似计算中的应用.
2.5 函数的微分 一、问题的提出 二、微分的定义 三、可微的条件 四、微分的几何意义 五、微分的求法 六、小结.
§3.4 空间直线的方程.
《解析几何》 -Chapter 3 §7 空间两直线的相关位置.
3.4 空间直线的方程.
《解析几何》 乐山师范学院 0 引言 §1 二次曲线与直线的相关位置.
第五章 二次型. 第五章 二次型 知识点1---二次型及其矩阵表示 二次型的基本概念 1. 线性变换与合同矩阵 2.
一、二阶行列式的引入 用消元法解二元线性方程组. 一、二阶行列式的引入 用消元法解二元线性方程组.
22.3 实际问题与一元二次方程(1).
Computer Graphics 第八章 分形几何.
清仓处理 跳楼价 满200返160 5折酬宾.
俄罗斯方块:注意观察游戏中用到的 数学的知识
四种命题 2 垂直.
一、原函数与不定积分 二、不定积分的几何意义 三、基本积分公式及积分法则 四、牛顿—莱布尼兹公式 五、小结
第5节 关注人类遗传病.
世上孩子都是宝, 男孩女孩都一样。.
第三节 格林公式及其应用(2) 一、曲线积分与路径无关的定义 二、曲线积分与路径无关的条件 三、二元函数的全微分的求积 四、小结.
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
2-7、函数的微分 教学要求 教学要点.
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
八年级下数学课题学习 格点多边形的面积计算 数格点 算面积.
探索三角形相似的条件(2).
初中数学八年级下册 (苏科版) 10.4 探索三角形 相似的条件(2).
C++中的声音处理 在传统Turbo C环境中,如果想用C语言控制电脑发声,可以用Sound函数。在VC6.6环境中如果想控制电脑发声则采用Beep函数。原型为: Beep(频率,持续时间) , 单位毫秒 暂停程序执行使用Sleep函数 Sleep(持续时间), 单位毫秒 引用这两个函数时,必须包含头文件
Computer Graphics 计算机图形学基础 张 赐 Mail: CSDN博客地址:
走进编程 程序的顺序结构(二).
绘制圆与多边形 椭圆形 绘制椭圆形的方法是 drawOval(x ,y , width , height), 绘制实心椭圆形的方法是
浙教版初中数学九年级(上) 4.6 图形的位似 初中数学资源网 龙港九中数学组.
计算机数学基础 主讲老师: 邓辉文.
工业机器人技术基础及应用 主讲人:顾老师
使用矩阵表示 最小生成树算法.
2.1.2 空间中直线与直线 之间的位置关系.
平行四边形的性质 灵寿县第二初级中学 栗 彦.
第一章 函数与极限.
第二十七章 相 似 27.2 相似三角形 相似三角形的性质.
第二十二章 曲面积分 §1 第一型曲面积分 §2 第二型曲面积分 §3 高斯公式与斯托克斯公式.
线段的有关计算.
2.6 直角三角形(二).
相似三角形 石家庄市第十中学 刘静会 电话:
第四章 四边形性质探索 第五节 梯形(第二课时)
用计算器开方.
复习: 若A(x1,y1,z1) , B(x2,y2,z2), 则 AB = OB - OA=(x2-x1 , y2-y1 , z2-z1)
正切函数的图象和性质 周期函数定义: 一般地,对于函数 (x),如果存在一个非零常数T,使得当x取定义域内的每一个值时,都有
3.1.2 空间向量的数量积运算 1.了解空间向量夹角的概念及表示方法. 2.掌握空间向量数量积的计算方法及应用.
北师大版《数学》五年级上册 组合图形面积.
北师大版《数学》五年级上册 组合图形面积.
第4课时 绝对值.
直线和圆的位置关系 ·.
静定结构位移计算 ——应用 主讲教师:戴萍.
分数再认识三 真假带分数的练习课.
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
平行四边形的性质 鄢陵县彭店一中 赵二歌.
1.4.3正切函数的图象及性质.
第二节 函数的极限 一、函数极限的定义 二、函数极限的性质 三、小结 思考题.
§2 方阵的特征值与特征向量.
在发明中学习 线性代数概念引入 之四: 矩阵运算 李尚志 中国科学技术大学.
4.6 图形的位似     观察思考:这两幅图片有什么特征? 都是有好几张相似图形组成,每个对应顶点都经过一点.
正弦函数的性质与图像.
第5课 美妙的万花筒世界 ——如何实现LOGO重复命令的嵌套.
第四节 向量的乘积 一、两向量的数量积 二、两向量的向量积.
找 因 数.
第三节 数量积 向量积 混合积 一、向量的数量积 二、向量的向量积 三、向量的混合积 四、小结 思考题.
三角 三角 三角 函数 余弦函数的图象和性质.
位似.
§4.5 最大公因式的矩阵求法( Ⅱ ).
第三章 图形的平移与旋转.
3.3.2 两点间的距离 山东省临沂第一中学.
第六单元 整理和复习 平面图形的周长和面积 复习课 浙江省诸暨市浣东五一小学 傅建勇.
Presentation transcript:

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

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

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

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

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

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

分形图形学

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

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

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

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

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

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(); }

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

初始元 初始元

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

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

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

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

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

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

随机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;

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;

//绘制 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;

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++;

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

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、+,-绘图。

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

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

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

压缩仿射变换 迭代系统只能使用压缩仿射变换,原图形上的各点经过仿射变换后,各点之间距离变小,这种仿射变换称为压缩仿射变换。 x’=a1·x+b1·y+e1 y’=c1·x+d1·y+f1 w1 x’=a2·x+b2·y+e2 y’=c2·x+d2·y+f2 w2 x’=a3·x+b3·y+e3 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

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

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

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

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

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;

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((1000 + 7000 * x)/15, (6500 - 6000 * y)/15, RGB(x + 500 * p, p * 100, y + 2000 * p)); n--; }

Sierpinski垫片

Sierpinski垫片

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

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

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

IFS生成的植物形态

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

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

Menger海绵生成元