- M) P' a- ~2 d3 y6 a3 {; K: g% W) ?
6.2 绘制分形8 ^' X, e& S6 m4 {2 r% ~
分形势复杂的几何图案或形状,但却由简单的数学公式所生成。与圆形和矩形等几何图形相比,分形看上去并不规则,也没有明显的模式或描述。但如果仔细观察,你将发现模式的存在,即整个图形有无数个自身的副本构成。由于分形设计平面上的点的相同几何变换的重复引用,因此非常适合使用计算机程序来构建。这一章中,我们将学习如何绘制Barnsley蕨类植物、Sierpinski三角和Manderlbrot集合(后两个出现在编程挑战中),这些都是分形研究领域的常见例子。分形在自然界中比比皆是,常见的例子包括海岸线、树木和雪花。 1 g) D9 N- Z) D$ s/ V
6.2.1 平面上点的变化
5 e% ^) R6 E% E+ `( ?$ y 创建分形的基本思想是点的变换。给定x-y平面上的一个点P(x,y),变幻的一个例子是P(x,y)->Q(x+1, y+1),这意味着应用变换后,创建好了一个新点Q,它位于P向上和向右各一个单位处。如果以Q点作为起始点,将得到另一个点R,它位于点Q向上和向右各一个单位处。假设起始点P位于(1,1),下图展示了这些点的位置。 2 H3 |- g. Q. K" Q
3 A j: ?: c7 p: y0 K" w* T P、Q、R三个点的位置图
4 Z2 v: l) Z0 q' G/ T, l
& z4 ?5 n% |% U% e 因此,变换是一种描述点在x-y平面上移动的规则,从起始位置开始,每一次迭代使得点移动到新的位置。我们可以把变换想象成点在平面上的轨迹。现在换个思路考虑两个变换规则,每次迭代将从这两个规则中随机选择一个。两个规则如下:
& r1 _7 }' g' Z% D, D$ J3 V% [2 H" @! b 规则1:P1(x,y) -> P2(x+1, y-1) + [- U; |6 @: C3 [$ K( V% _0 l) U
规则2:P1(x,y) -> P2(x+1, y+1) - K& w, Y- K+ e6 b7 s
以P(1, 1)作为起始点,如果我们执行4次迭代,将得到以下一系列的点: " E8 }3 n4 v! Y
P1(1, 1) -> P2(2, 0) (规则1)
7 R$ q9 @ L& |- n4 A3 K4 M P2(2, 0) -> P3(3, 1) (规则2)
; _ r0 K3 h. u: n2 ^3 P' j P3(3, 1) -> P4(4, 2) (规则2)
2 j% {2 `2 {- {% l1 b$ Y P4(4, 2) -> P5(5, 1) (规则2) 9 u) d r( u: c
...
9 O& N" s& m, {0 v+ x 两个变换规则是随机选择的,其中每个规则被选择的概率相同。无论选择哪一个规则,点都会右移,因为在两种规则中都会增加x坐标。当点向右移动时,他们会向上或向下移动,从而形成一条Z字路径。以下程序绘制了在指定的迭代次数内进行上述转换规则之一时点的路径: 8 S3 Y' G3 ~: }* |% D; h$ m& |
Example of selecting a transformation from two equally probable
4 k1 f0 S8 z$ \; K9 o7 N: }# N4 ` transformations! l' T c/ _5 I" D$ L- s4 b) h4 o
( z b+ ~ C8 v: n1 |7 N# c* h( q
import matplotlib.pyplot as plt: B. A: L3 C! l& o: {
import random
' v+ `% T5 F# d6 L. _5 l# S0 q( L
6 i' p, u3 L L7 K' |/ J* j def transformation_1(p):( u( T4 c! k" Q7 C6 J
x = p[0]
# h& f A4 x: E' m! B4 i) ? y = p[1]" p3 V: q: R5 X" u$ H: }2 ?
return x + 1, y - 1& n. M5 |0 d7 b
def transformation_2(p):
9 R# }: d# d; w- ?& I x = p[0]
) o b, i- w0 R6 H0 s0 J' U y = p[1]
/ H4 Q) U V. ~0 T return x + 1, y + 19 v3 u% z5 @2 X, l( J; B; h5 S6 _- q+ o& E
def transform(p):
) b) l) E/ r, C7 c+ `$ u # List of transformation functions) X6 ^9 V; Q7 {: M
transformations = [transformation_1, transformation_2]% t. F/ W4 b+ J2 w6 p" M/ H
# pick a random transformation function and call it- X3 [- j) d) |4 Q% @
t = random.choice(transformations)
3 \: `' p# \" T' P, ? x, y = t(p)
6 S& {$ d& W2 S return x, y
0 t% x! [( r3 T4 X$ m* S& ? def build_trajectory(p, n):' B2 M' N; W" m
x = [p[0]]& ?# }) b. H" ]3 d2 c
y = [p[1]]
; D% a. |% }8 e- ?' ~7 ?4 L for i in range(n):% f! _4 `5 {: V# H, o' f5 _: t P) X, ]
p = transform(p)
. f' r- [, b5 l x.append(p[0])
. U5 g" d# a& d$ q y.append(p[1])( s& H6 c5 w/ J, h( b
return x, y
* `3 A! Y3 I2 }, a) w* J- w" ]$ _+ N
if __name__ == __main__:5 u* m" a6 R: G/ W2 Q7 e
# Initial point& C" C8 f3 W* Q$ O2 V) F
p = (1,1)1 s$ u$ i) ~) x5 H+ P" [7 p
n = int(input(Enter the number of iterations: ))/ k4 @, X) R7 G: T* k
x , y = build_trajectory(p, n)' X. f( C5 m4 [
# PLot
4 n( z: ~; Z6 y/ `' @# ~. P" w plt.plot(x, y)$ N; E! E, s# L0 ^* s3 U6 ~
plt.xlabel(X)) h' T; u1 d. H+ l! ?5 V: r. p. H
plt.ylabel(Y)2 f) e! y4 e! F( L
plt.show()我们定义了两个函数transformation_1()和transformation_2(),分别对应于之前的两种变换规则,在transform()函数中,我们创建了一个包含这两个函数名字的列表,然后使用random.choice()函数从该列表中选择去哦中一个进行变换。现在假设我们选择了其中一个变换,蒋点P作为输入参数调用该变换函数,然后分别使用x,y来存储变换后的坐标并且返回它们。 " F' D* B4 s$ D8 G
从列表中随机选择一个元素 5 M! S' B( E! i) x/ [, x5 N+ E3 D( U
我们在第一个分形程序中看到的random.choice()函数可以用来从列表中随机选择一个元素,每一个元素被选中的概率相同,下面是一个例子: import random, k" N& A; A: r0 q5 V9 i. T7 h
>>> l = [1,2,3]
( @" u8 k' S4 V) B. ?- O/ B$ R/ u+ L >>> random.choice(l)
# e2 F& ]2 l* u8 Y 1
+ V! M% ?: Z6 n, n& y >>> random.choice(l)
1 P" \6 r: x' w2 P+ u 3! Z! m1 q V, e7 C/ l
>>> random.choice(l)
, ]1 l0 c7 f$ @! `- C! Y. x: o1 b 3& n: i j' ?% J( k! p
>>> random.choice(l)" o" F: J# n7 M3 ~$ ^6 b* K
1
, E$ P& X. f. I2 t! A- k. M% H; \ >>> random.choice(l) u- W# i( B' k2 w
1
N9 @, P3 F" p, |5 W2 E2 u 这个函数也适用于元组和字符串。在后一种情形中,函数从字符串中随即返回一个字符。
; z2 a* A( K! d 当运行程序,他首先会询问迭代次数n,即应用变化的次数。然后调用build_trajectory()函数,该函数的输入参数为迭代次数n和起始点坐标p,此处设置初始点坐标为(1,1)。build_trajectory()函数重复调用n次transform()函数,并使用两个列表x和y分别存储变换后的x和y坐标。最后使用这两个列表来绘制图形。
H& C# Y' ?; G' u7 f: F2 L- ? 下面两张图分别显示了100次和10000次迭代的点的轨迹图,这两幅图中的Z字形运动都很明显,这种Z字形路径通常被称为一条线上的随机游走。 , b% q l! `( b% j
' ?1 K# |" `1 c0 } 迭代100次的Z字路径 : D/ {7 l Z! i' G$ Q1 b' E+ |5 ]
( I: L& ^# p* ]5 @ W* v/ U
" y+ v9 o9 m: }7 o/ \) R
迭代10000次的Z字路径
; M; Z' s5 Y. b" a- N4 H9 o
& D [2 f1 Q" u0 {% r* _% P0 l" y 这个例子展示了创建分形的基本思想,即从一个点开始并对其重复应用某种变换。接下来,我们将看到一个用相同想法绘制Barnsley蕨类植物的例子。 ( a& T! r6 `2 J. U$ O4 I: T
6.2.2 绘制Barnsley蕨类植物( K- A; s8 {3 z- c2 M
英国数学家Michael Barnsley描述了如何对一个点进行重复的简单变换,从而创建蕨类植物的结构(如下图)。
! S+ X' i! F$ m# |0 ]2 U+ w
" i I0 v! {7 E+ @, X 蕨类植物
% \3 N/ B8 P; m b/ g
$ ?5 b( {1 s: z/ U, h: Q A5 i 他提出了以下步骤来创建类似于蕨类植物的结构,以(0,0)为初始点,按事先分配的概率随机选择下述某种变换。 # c+ b4 {2 Y9 _
(1)变换1(概率为0.85):
$ G- ]+ A9 G# w' q2 |
$ t1 e6 p. z! A1 d2 `) Y (2)变换2(概率为0.07): ! ~8 S' l( G8 }% f: ?* s
3 h. q$ C/ w8 Y- F" J" a( p (3)变换3(概率为0.07):
- U, c2 e+ H* J / b( ]3 f# }" _
(4)变换4(概率为0.01):
/ ~$ o0 I5 q: _: {) D$ e: b7 w2 S: _ : ^( G0 @+ T/ }! Y2 S" E# [
上述每一个变换对应于蕨类植物的一部分。第一个变换被选中的概率最大,因此被执行的次数最多,从而产生了蕨类植物的茎和底部的叶子。第二个和第三个变换分别对应于左边和右边底部的叶子,第四个变换绘制了蕨类植物的茎。
( e0 U7 {' A w" B5 Z 这是一个非均匀概率选择的例子,我们在第五章中已经学习过,以下程序为指定的点数绘制Barnsley蕨类植物。
7 n' M# T6 X$ j Draw a Barnsley Fern
+ |( G" E" z% b& T2 ~1 I' j, l2 `8 q6 a& \* [1 |
import random/ I9 X2 x6 t" U! k
import matplotlib.pyplot as plt& ], v) I5 B) b8 j
def transformation_1(p):
3 Q3 p' v: }& x% F3 O x = p[0]
0 F* I' u: W0 U J9 T0 n/ L y = p[1]& I7 X* d0 F3 R
x1 = 0.85*x + 0.04*y
: x. D6 \2 } x# R y1 = -0.04*y + 0.85*y + 1.6
0 i+ @$ y7 R3 f/ D* i" i/ `' O return x1, y1 K) c! _, w, y: u, t8 D( O& Z, W& ]$ d1 U5 P
def transformation_2(p):
2 i- ~, F& ~3 D4 A7 L x = p[0]
6 G9 U! L8 _7 k* ~ y = p[1]4 ~. P3 Y' }% D9 f' w
x1 = 0.2*x - 0.26*y
6 M* X0 ]5 T( U" e) i. y/ B y1 = 0.23*y + 0.22*y + 1.6. u% g6 f7 |. I) _" c. P& X
return x1, y1
+ z& }9 V0 C* V% x+ D9 a( w def transformation_3(p):
; f+ s! Y6 S# z3 _: D( E h x = p[0]! m5 I( e1 A2 y0 P! |1 v
y = p[1]
) h+ ^8 |( r v7 B x1 = -0.15*x + 0.28*y
) p8 u2 [! }4 t2 Q y1 = 0.26*y + 0.24*y + 0.44
. B, Z. O2 ?( B5 c return x1, y19 d" c1 a5 w2 H6 w4 F
def transformation_4(p):
8 ~( @7 \% n" v% |! X x = p[0]
6 ]* B% _" r/ c/ k( B& H y = p[1]3 V" w B+ m4 l* o
x1 = 0; G4 g/ B; D) m* q. N
y1 = 0.16*y
% @) \6 A+ S3 I3 a, O5 r) d, o return x1, y13 S3 a" V% R8 W: M" }
def get_index(probability):
. j& P, J4 Q5 b0 A: c r = random.random()$ ~! G4 Y$ T, |) Y% L y. f
c_probability = 0
" ^6 t7 ^! O* T+ a$ N sum_probability = []# P8 n" x1 @1 U3 A- c- r
for p in probability:$ M- V2 x) s( h% l
c_probability += p
# T6 J# t; r J# M sum_probability.append(c_probability)
- r6 @) R1 S! F0 A8 H* @ for item, sp in enumerate(sum_probability):; R# X4 ^% N" K7 _- B
if r < sp:1 U; y2 `5 z! E
return item
" q9 x7 M2 D" ~6 n, t. G return len(probability) - 1
- _' @6 D5 [# m/ E/ ^; ^, ?0 M# p t( ~6 U6 |
def transform(p):
$ F- _* a4 g0 U+ {! h. ]' [, G; g # List of transformation functions
5 c& Z! R0 a3 x transformation = [transformation_1, transformation_2, transformation_3, transformation_4]5 {! U/ w6 b* k; w: s: Q
probability = [0.85, 0.07, 0.07, 0.01]3 Z: X0 \4 f0 m! @4 q
# Pick a random transformation function and call it8 ^$ K' C: e$ n: o
tindex = get_index(probability)0 I7 v( i. C' [1 V+ S0 z; K% E, d" M* ^
t = transformation[tindex]
6 L9 x, y1 l7 W0 E* L" d4 p" b. { x, y = t(p)
1 W8 Q; p! ~$ k$ Q, `& v$ s) u return x, y
: E; t8 c3 e6 b) s3 ?/ v: D def draw_fern(n):
* r/ \1 n9 B0 u5 E. L # We start with (0,0)1 l1 U; _3 _3 B+ o
x = [0]* O6 B- Y5 N: o5 L
y = [0]
* F) l' m0 U( [) j5 T x1, y1 = 0, 0
) z. d6 A7 i! n% c& ` for i in range(n):
. z& p- e$ Y& |: D, R8 F: g x1, y1 = transform((x1, y1))6 z5 t3 ~& x: [ n9 L) b0 ]
x.append(x1); L& B! i! S x8 j
y.append(y1)4 v" F5 }& V6 L8 x
return x, y
2 ~* q3 j) T( P' {+ K if __name__ == __main__:5 \6 K+ y3 Z+ p% ~8 H( L
n = int(input(Enter the number of points in the Ferns: ))
9 ` b3 N+ W0 ] x, y = draw_fern(n)9 [3 j! y0 O+ {+ I0 Y
plt.plot(x, y, o)0 |6 s0 B, ]5 B) M3 l1 A, v
plt.title(Fern with {0} points.format(n))
6 s$ G* P# ?4 Q1 j plt.show()
- {# m! h; F/ I+ s' c 运行此程序,他首先询问蕨类植物图中指定的点数,然后开始绘制该图。下面两张图分别展示了具有1000个点和10000个点的蕨类植物图。 7 J& _4 z5 \! F$ \- o
3 K$ z$ S" D% u! c" F9 W+ Y2 T4 h 制定了1000个点的蕨类植物叶片
" C" r& j& u9 d b# x4 L
( ~# _* m4 t6 D1 N- @" z6 ~
& o/ B2 T6 ]& b, {% N5 q% H 指定了10000个点的蕨类植物叶片
0 X. {( m) J' d2 L: s& o) q 0 p, w& f) s! r' t0 t I+ F
这4个变换规则分别在transformation_1(),transformation_2(),transformation_3(),transformation_4()函数中定义。get_index()函数返回按照给定概率下的一种随机变化的索引值,这个概率我们之前已经讲过了,不清楚的可以返回去在第五章非均匀概率那里再次学习。返回索引之后即可选择某一个具体的变换来应用。 & Z6 p. u; V1 F1 b6 a; q
初始点(0,0)变换的次数即为程序输入中指定的蕨类植物点的个数。
( \, q9 N! F) n" f6 h1 Z2 l z- n& n! K
2 l5 \; l- s. | G1 }
9 l6 e' G2 Q9 u; f \+ H# u+ ?9 P o% M1 \
|