Python 分形演演算法程式碼詳解

2022-03-29 13:01:50

1. 前言

分形幾何是幾何數學中的一個分支，也稱大自然幾何學，由著名數學家本華曼德勃羅（法語：BenoitB.Mandelbrot）在 1975 年構思和發展出來的一種新的幾何學。

分形幾何是對大自然中微觀與宏觀和諧統一之美的發現，分形幾何最大的特點：

整體與區域性的相似性：一個完整的圖形是由諸多相似的微圖形組成，而整體圖形又是微圖形的放大。

區域性是整體的縮影，整體是區域性的放大。

具有自我疊加性：整體圖形是由微圖形不斷重複疊加構成，且具有無限疊加能力。

什麼是分形演演算法？

所謂分形演演算法就是使用計算機程式模擬出大自然界的分形幾何圖案，是分形幾何數學與電腦科學相融合的藝術。

由於分形圖形相似性的特點，分形演演算法多采用遞迴實現。

2. 分形演演算法

2.1 科赫雪花

科赫雪花是由瑞典數學家科赫在 1904 年提出的一種不規則幾何圖形，也稱為雪花曲線。

分形圖形的特點是整體幾何圖形是由一個微圖形結構自我複製、反覆疊加形成，且最終形成的整體圖案和微圖形結構一樣。在編寫分形演演算法時，需要先理解微圖案的生成過程。

科赫雪花的微圖案生成過程：

先畫一條直線。科赫雪花本質就由一條直線演化而成。
三等分畫好的直線。
取中間線段，然後用夾角為 60° 的兩條等長線段替代。
可在每一條線段上都採用如上方式進行迭代操作，便會構造出多層次的科赫雪花。

科赫微圖形演演算法實現：

使用 Python 自帶小海龜模組繪製，科赫雪花遞迴演演算法的出口的是畫直線。

import turtle
'''
size：直線的長度
level: 科赫雪花的層次
'''
def koch(size, level):
    if n == 1:
        turtle.fd(size)
    else:
        for i in [0, 60, -120, 60]:
            turtle.left(i)      
            # 旋轉後，再繪製
            koch(size // 3, level - 1)

引數說明：

size：要繪製的直線長度。
level：科赫雪花的層次。

0 階和 1 階科赫雪花遞迴流程：

import turtle
turtle.speed(100)
def ke_line(line_, n):
    if n == 0:
        turtle.fd(line_)
    else:
        line_len = line_ // 3
        for i in [0, 60, -120, 60]:
            turtle.left(i)
            ke_line(line_len, n - 1)
# 原始直線長度
line = 300
# 移動小海龜到畫布左下角
turtle.penup()
turtle.goto(-150, -150)
turtle.pendown()
# 1 階科赫雪花
di_gui_deep = 1
ke_line(line, di_gui_deep)
turtle.done()

2 階科赫雪花：

可以多畫幾個科赫雪花，佈滿整個圓周。

import turtle
turtle.speed(100)
def ke_line(line_, n):
    if n == 0:
        turtle.fd(line_)
    else:
        line_len = line_ // 3
        for i in [0, 60, -120, 60]:
            turtle.left(i)
            ke_line(line_len, n - 1)
# 原始線長度
line = 300
# 移動小海龜畫布左下角
turtle.penup()
turtle.goto(-150, -150)
turtle.pendown()
# 幾階科赫雪花
di_gui_deep = int(input("請輸入科赫雪花的階數："))
while True:
    # 當多少科赫雪花圍繞成一個圓周時，就構成一個完整的雪花造型
    count = int(input("需要幾個科赫雪花："))
    if 360 % count != 0:
        print("請輸入 360 的倍數")
    else:
        break
for i in range(count):
    ke_line(line, di_gui_deep)
    turtle.left(360 // count)
turtle.done()

4 個 3 階科赫雪花：每畫完一個後旋轉 90 度，然後再繪製另一個。

6 個 3 階科赫雪花：每畫完一個後，旋轉 60 度再畫另一個。

科赫雪花的繪製並不難，本質就是畫直線、旋轉、再畫直線……

2.2 康託三分集

由德國數學家格奧爾格·康托爾在1883年引入，是位於一條線段上的一些點的集合。最常見的構造是康托爾三分點集，由去掉一條線段的中間三分之一得出。

構造過程：

繪製一條給定長度的直線段，將它三等分，去掉中間一段，留下兩段。
再將剩下的兩段再分別三等分，同樣各去掉中間一段，剩下更短的四段……
將這樣的操作一直繼續下去，直至無窮，由於在不斷分割捨棄過程中，所形成的線段數目越來越多，長度越來越小，在極限的情況下，得到一個離散的點集，稱為康托爾點集。

編碼實現：使用遞迴實現。

import turtle
''''
(sx,sy)線段的開始位置
(ex,ey)線段的結束位置
'''
turtle.speed(100)
turtle.pensize(2)
def draw_kt(sx, sy, ex, ey):
    turtle.penup()
    # 小海龜移動開始位置
    turtle.goto(sx, sy)
    turtle.pendown()
    # # 小海龜移動結束位置
    turtle.goto(ex, ey)
    # 起始點與結束點之間的距離
    length = ex - sx
    # 如果直線長線大於 5 則繼續畫下去
    if length > 5:
        # 左邊線段的開始 x 座標
        left_sx = sx
        # y 座標向下移動 30
        left_sy = sy - 50
        # 左邊線段的結束座標
        left_ex = sx + length / 3
        left_ey = left_sy
        # 右邊線段的開始座標
        right_sx = ex - length / 3
        right_sy = ey - 50
        # 右邊線段的結束座標
        right_ex = ex
        right_ey = right_sy
        draw_kt(left_sx, left_sy, left_ex, left_ey)
        draw_kt(right_sx, right_sy, right_ex, right_ey)
draw_kt(-300, 200, 300, 200)
turtle.done()

康託三分集的遞迴演演算法很直觀。

2.3 謝爾賓斯基三角形

謝爾賓斯基三角形（英語：Sierpinski triangle）由波蘭數學家謝爾賓斯基在1915年提出。

構造過程：

取一個實心的三角形（最好是等邊三角形）。
沿三邊中點的連線，將它分成四個小三角形。
去掉中間的那一個小三角形。
對其餘三個小三角形重複上述過程直到條件不成立。

編碼實現：謝爾賓斯基三角形就是不停的畫三角形，在編碼之前約定三角形點之間的關係以及繪製方向如下圖所示。

import turtle
import math
turtle.speed(100)
'''
 通過連線 3 個點的方式繪製三角形
 pos是元組的元組((x1,y1),(x2,y2),(x3,y3))
def draw_triangle(pos):
    turtle.penup()
    # 移到第一個點
    turtle.goto(pos[0])
    turtle.pendown()
    # 連線 3 個點
    for i in [1, 2, 0]:
        turtle.goto(pos[i])
  
# 計算三角形任意兩邊的中點座標
def get_mid(p1, p2):
    return (p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2
繪製 謝爾賓斯基三角形
def sierpinski_triangle(*pos):
    # 用給定的點繪製三角形
    draw_triangle(pos)
    p1, p2, p3 = pos
    # 計算三角形的邊長
    side = math.fabs((p3[0] - p1[0]) / 2)
    # 如果邊長滿足條件，繼續繪製其它三角形
    if side > 10:
        # p1和p2線段 的中心點
        p1_p2_center_x, p1_p2_center_y = get_mid(p1, p2)
        # p2和p3線段 的中心點
        p2_p3_center_x, p2_p3_center_y = get_mid(p2, p3)
        # p1和p3線段 的中心點
        p1_p3_center_x, p1_p3_center_y = get_mid(p1, p3)
        # 繪製左下角三角形
        sierpinski_triangle(p1, (p1_p2_center_x, p1_p2_center_y), (p1_p3_center_x, p1_p3_center_y))
        # 繪製上邊三角形
        sierpinski_triangle((p1_p2_center_x, p1_p2_center_y), p2, (p2_p3_center_x, p2_p3_center_y))
        # 繪製右下角三角形
        sierpinski_triangle((p1_p3_center_x, p1_p3_center_y), (p2_p3_center_x, p2_p3_center_y), p3)
# 第一個點指左邊點，第二點指上面的點，第三個指右邊的點。
sierpinski_triangle((-200, -100), (0, 200), (200, -100))
turtle.done()

程式碼執行之後的結果：

用隨機的方法（Chaos Game），繪製謝爾賓斯基三角形：

構造過程：

任意取平面上三點 A,B,C，組成一個三角形。

在三角形 ABC 內任意取一點 P，並畫出該點。

找出 P 和三角形其中一個頂點的中點，並畫出來。

把剛才找出來的中心點和三角形的任一頂點相連線，同樣取其中點，並畫出來。

重複上述流程，不停的獲取中心點。

注意，是畫點，上面的線段是為了直觀理解中心點位置。

編碼實現：

import turtle
import random
turtle.speed(100)
turtle.bgcolor('black')
colors = ['red', 'green', 'blue', 'orange', 'yellow']
# 畫等邊三角形
def draw_triangle(pos):
    turtle.penup()
    turtle.goto(pos[0])
    turtle.pendown()
    for i in [1, 2, 0]:
        turtle.goto(pos[i])

def sierpinski_triangle(*pos):
    # 畫三角形
    draw_triangle(pos)
    p1, p2, p3 = pos
    # 在三角形中任取一點
    ran_x, ran_y = (p1[0] + p3[0]) / 2, (p2[1] + p3[1]) / 2
    for i in range(10000):
        # 畫點
        turtle.penup()
        turtle.goto(ran_x, ran_y)
        turtle.pendown()
        turtle.dot(3, colors[i % 5])
        # 隨機選擇 3 個頂點的一個頂點
        ran_i = random.randint(0, 2)
        ding_p = pos[ran_i]
        # 計算任意點和頂點的中心點
        ran_x, ran_y = (ran_x + ding_p[0]) / 2, (ran_y + ding_p[1]) / 2
sierpinski_triangle((-200, -100), (0, 200), (200, -100))
turtle.done()

隨機法是一個神奇的存在，當點數量很少時，看不出到底在畫什麼。當點的數量增加後，如成千上萬後，會看到謝爾賓斯基三角形躍然於畫布上，不得不佩服數學家們天才般的大腦。

下圖是點數量為 10000 時的謝爾賓斯基三角形，是不是很震撼。

2.4 分形樹

繪製分形樹對於遞迴呼叫過程的理解有很大的幫助，其實前面所聊到的遞迴演演算法都是樹形遞進。分形樹能很形象的描述樹形遞迴的過程。

分形樹的演演算法實現：

import turtle
def draw_tree(size):
    if size >= 20:
        turtle.forward(size) # 1
        # 畫右邊樹
        turtle.right(20)
        draw_tree(size - 40) # 2
        # 畫左邊樹
        turtle.left(40)
        draw_tree(size - 40)
        # 後退
        turtle.right(20)
        turtle.backward(size)
turtle.left(90)
draw_tree(80)
turtle.done()

為了理解分形樹的遞迴過程，如上程式碼可以先僅畫一個樹幹兩個樹丫。