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

1. 개요 & 알고리즘

이번 포스팅에서는 프랙탈 나무를 그려보겠습니다. "C로 배우는 알고리즘"에 설명된 알고리즘은 다음과 같습니다.

1. 주어진 length와 angle을 이용하여 이동할 상대 좌표를 구한다.

2. 구한 상대 좌표로 선을 그린다. (제어점이 상대 좌표만큼 이동한다)

3. order가 0이면 6으로 간다. (종료 조건)

4. (order-1, length*SCALE, angle+TURN)에 대해 프랙탈 나무 알고리즘을 실행한다.

5. (order-1, length*SCALE, angle-TURN)에 대해 프랙탈 나무 알고리즘을 실행한다.

6. 제어점을 1의 상태로 되돌린다.

"C로 배우는 알고리즘"에서는 linerel(x, y) 함수를 사용했습니다. 링크를 참고해서 정리하면, linerel(x, y)는 (함수에는 표시되지 않지만) 현재 위치를 시작점으로 상대적(relative)으로 x, y만큼 "더" 이동한 위치를 끝점으로 선을 긋는 동작입니다.

즉, 현재 위치를 (xref, yref)라고 하면, (xref, yref)와 (xref+x, yref+y)간에 선을 긋게 됩니다.

2. 동작 코드

프랙탈 나무에 대해서는 다양한 예제를 찾아볼 수 있는데, "Turtle" 모듈을 사용한 예는 대단히 재미있습니다. 그중에서 "C로 배우는 알고리즘"과 거의 같은 코드를 찾을 수 있었습니다. Length, order, angle의 숫자만 바꾸면 되며, 이를 사용하도록 하겠습니다. 원본 코드의 실행예는 다음과 같습니다.

이를 바탕으로 "C로 배우는 알고리즘"에 있는 코드와 비슷하게 약간 변경해 봅니다.

def fixed_tree(x1, y1, angle, depth, order):
    if order > 0:
        x2 = x1 + (math.cos(math.radians(angle)) * depth)
        y2 = y1 + (math.sin(math.radians(angle)) * depth)
        plt.plot([x1, x2], [y1, y2], 'b.-')
        fixed_tree(x2, y2, angle - 30, depth * 0.8, order - 1)
        fixed_tree(x2, y2, angle + 30, depth * 0.8, order - 1)

"C로 배우는 알고리즘"에서는 0.5 radian 단위로 각도를 조정합니다. 하지만 fixed_tree()에서 angle 단위는 degree이므로, 변환하여 0.5 radian과 비슷한 30 degree를 임의로 사용했습니다.

Random 함수를 사용하는 경우의 코드는 다음과 같습니다.

def random_tree(x1, y1, angle, depth, order):
    if order > 0:
        x2 = x1 + (math.cos(math.radians(angle)) * depth)
        y2 = y1 + (math.sin(math.radians(angle)) * depth)
        plt.plot([x1, x2], [y1, y2], 'b.-')

        right_angle = random.randint(0, 40)
        left_angle = random.randint(0, 40)
        depth_scale = random.uniform(0.7, 0.9)

        random_tree(x2, y2, angle - right_angle, depth * depth_scale, order - 1)
        random_tree(x2, y2, angle + left_angle, depth * depth_scale, order - 1)

fixed_tree() 코드에서 각도를 0~40, 길이의 비율을 0.7~0.9 사이에서 random하게 선택하도록 하였습니다.

3. 실행 코드

프랙탈 나무를 그리는 실행 코드는 다음과 같습니다.("C로 배우는 알고리즘" 리스트 4-5 : FTREE.C에 대응)

if __name__ == '__main__':
    order = 10
    fixed_tree(100, 100, 90, 70, order)
#   random_tree(100, 100, 90, 70, order)
    plt.show()

order 10으로 fixed_tree()를 실행한 결과는 다음과 같습니다.

order 12로 fixed_tree()를 실행한 결과는 다음과 같습니다. (시간이 오래 걸리네요)

random_ tree를 실행한 결과는 다음과 같습니다.

4. 코드

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_04/Ch_04_06.py

5. 기타

주로 "C로 배우는 알고리즘"에 적혀 있는 내용을 주고 사용하고, 필요시 인터넷 검색의 결과를 이용하였습니다. 이용한 출처는 밝히는 것을 원칙으로 합니다만, 혹시 실수가 있거나 문제되는 사항이 있다면 알려 주십시오. 수정하도록 하겠습니다.