재귀 (5) - 프랙탈 트리 (Fractal Tree)

1. 알고리즘 개요

프랙탈이란 자기 유사성을 갖는 기하학적 구조를 의미한다. 자기 유사성이란 일부의 조각이 전체의 형상과 비슷한 것을 의미한다. 유명한 프랙탈 구조로는 눈꽃 결정이나 아래의 프랙탈 삼각형 등이 있다.

 

[그림] 프랙탈 삼각형

 

이러한 프랙탈 구조가 나무의 모양으로 나타난 것을 Fractal Tree (프랙탈 트리)라고 한다. 우리는 재귀함수를 이용하여 아름다운 프랙탈 트리를 만들어볼 예정이다. 프랙탈은 무한히 자기 자신의 구조를 복제하므로 우리가 공부하고있는 재귀함수와 매우 유사한 성질이 있고, 실제로 재귀함수로 매우 쉽게 프랙탈 도형을 만들 수 있다.

 

[그림] 프랙탈 트리

 

2. Fractal Tree 그리기

 

프랙탈 트리를 만드는 방법은 간단하다. 중앙의 줄기를 $L_{0}$이라고 한다면 $L_{0}$로부터 첫번째로 뻗어나가는 가지를 $L_1$라고 한다. (위 그림 참고) 이 새로운 가지는 기존 중앙의 줄기에 대비해 $turn$의 각도로 벌어져있다. $L_{0}$의 길이가 $L$라고 할 때, $L_1$의 길이는 $L \times scaled$ (단, $scaled \leq 1.0$)가 된다. 즉, 기존의 길이에 1보다 작은 임의의 수를 곱하여 기존 줄기보다 길이가 짧아진다. 이 $L_1$에서 뻗어나간 가지를 $L_2$라고 한다.(위 그림 참고) 마찬가지로 $L_2$는 $L_1$의 길이에 $scaled$값을 곱하여  더욱 짧아지고, 기존의 각도보다 $turn$ 만큼 더 벌어져있다. 중앙의 가지 $L_{0}$에 비하면 $2 \times turn$만큼 벌어져 있는 것이다. 

 

이를 기반으로 우리가 가지들의 좌표를 알아내려면 어떻게 해야할까? 현재 각도와 빗변의 길이가 주어졌기 때문에 삼각함수를 이용하면 너비와 높이를 구할 수 있고 너비와 높이는 곧 (x, y) 좌표가 된다. 빗변의 길이는 일정하게 줄어들고 각도는 일정하게 증가하므로 새로운 빗변과 각도를 지속해서 구할 수 있고, 이를 이용해 계속해서 (x, y) 좌표를 찾아내고 선으로 이어주면 프랙탈 트리가 완성된다. 새로운 가지의 x좌표는 기존의 x좌표에서 $L \times  sin \theta$만큼 이동한 좌표이고 새로운 y좌표는 기존의 y좌표에서 $L \times cos \theta$만큼 이동한 좌표이다. 위의 그림에서 $turn$부분의 각도를 기준으로 cos와 sin을 생각해보면 이해할 수 있을 것이다.

 

3. 소스 코드

 

import math
from matplotlib import pyplot as plt

colors = ["#984b00", "#317c00"]


def fixed_tree(x, y, angle, length, order, total):
    if order > 0:
        x2 = x + (math.cos(math.radians(angle)) * length)
        y2 = y + (math.sin(math.radians(angle)) * length)
        color = colors[0 if order >= 3 else 1]
        plt.plot([x, x2], [y, y2], color)

        fixed_tree(x2, y2, angle - 30, length * 0.8, order - 1, total)
        fixed_tree(x2, y2, angle + 30, length * 0.8, order - 1, total)

if __name__ == '__main__':
    order = 12
    fixed_tree(x=100, y=100,
               angle=90,
               length=70,
               order=order,
               total=order)

    plt.show()

 

구현에는 Python과 matplotlib.pyplot을 이용하였다. 12단계의 order를 거치며 새로운 각도는 기존의 각도 대비 좌우로 30도씩 차이나게 하였고 길이는 매 order마다 0.8배가 되게하였다. 새로운 가지를 그릴 때 마다 재귀함수를 호출하여 계속해서 가지를 추가해나간다. 이 소스코드를 이용하여 그린 프랙탈 트리는 아래와 같다.

 

 

그러나 이렇게 그린 프랙탈 트리는 나무의 모양보다는 규칙성으로 인해 인위적인 모습이 강하다. 때문에  각도 $turn$과 가지의 길이에 계속해서 곱해지는 $scaled$를 매 호출마다 다르게 하는 Random Tree를 그리면 조금 더 자연스러운 나무의 모양이 되는 그 모습은 아래와 같다. 

 

import math
import random

from matplotlib import pyplot as plt

colors = ["#984b00", "#317c00"]


def random_tree(x, y, angle, length, order, total):
    if order > 0:
        x2 = x + (math.cos(math.radians(angle)) * length)
        y2 = y + (math.sin(math.radians(angle)) * length)
        color = colors[0 if order >= 3 else 1]
        plt.plot([x, x2], [y, y2], color)

        l_angle = random.uniform(0, 40)
        r_angle = random.uniform(0, 40)
        scaled = random.uniform(0.7, 0.9)

        random_tree(x2, y2, angle - l_angle, length * scaled, order - 1, total)
        random_tree(x2, y2, angle + r_angle, length * scaled, order - 1, total)


if __name__ == '__main__':
    order = 12
    random_tree(x=100, y=100,
               angle=90,
               length=70,
               order=order,
               total=order)

    plt.show()

 

 

매번 변화하는 각도와 길이를 랜덤으로 부여하자 실제 나무와 같은 그림을 그릴 수 있었다. 이 처럼 재귀함수를 이용하면 계속해서 반복되는 프랙탈 도형을 매우 쉽게 그릴 수 있다.

 

모든 소스코드는 Github에서 확인할 수 있습니다.

gusdnd852/TIL

 

4. Reference 

[04-06] 재귀 호출 - 프랙탈 나무(Tree)