더디지만... 꾸준히...

"C로 배우는 알고리즘" 리스트 4-6 : REF.C에 대응하는 파일 검색과 관련한 프로그램은 아래 링크에 너무 자세히 잘 설명되어 있어서 건너 뛰도록 하겠습니다.

https://wikidocs.net/39

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. 코드

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

1. 개요 & 알고리즘

"C로 배우는 알고리즘"에 설명된 "시어핀스키의 양탄자"를 위한 알고리즘(x, y, r)은 다음과 같습니다.

1. r이 0이 되면 끝이다 (종료 조건)

2. (x-2*r, y+2*r, r/3)에 대해 알고리즘을 실행한다.

3. (x-2*r, y, r/3)에 대해 알고리즘을 실행한다.

4. (x-2*r, y-2*r, r/3)에 대해 알고리즘을 실행한다.

5. (x, y+2*r, r/3)에 대해 알고리즘을 실행한다.

6. (x, y-2*r, r/3)에 대해 알고리즘을 실행한다.

7. (x+2*r, y+2*r, r/3)에 대해 알고리즘을 실행한다.

8. (x+2*r, y, r/3)에 대해 알고리즘을 실행한다.

9. (x+2*r, y-2*r, r/3)에 대해 알고리즘을 실행한다.

10. (x-r/3, y-r/3, x+r/3, y+r/3)에 크기의 사각형을 덜어낸다.

사각형을 그리기 위한 Python 코드입니다.

import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle

fig, ax = plt.subplots(1, 1)
rect = Rectangle((-1, 1), 1, 2, color='blue')
ax.add_patch(rect)
ax.autoscale_view()
plt.show()

Rectangle 패치를 사용했습니다(참조링크1, 참조링크2). Rectangle은 사각형의 왼쪽 아래 좌표를 주고, 가로 길이와 세로 길이를 입력하게 됩니다. 예제에서는 (-1,1)에서 시작해서 가로 1, 세로 2 크기를 갖는 사각형을 그리게 되며, 결과는 아래와 같습니다.

사각형 여러개를 그리기 위해서는 plt.show() 전에 다음 코드를 반복해서 사용하면 됩니다.

rect = Rectangle((-1, 1), 1, 2, color='blue')
ax.add_patch(rect)

2. 동작 코드

총 3가지 그림을 그리게 됩니다. ("C로 배우는 알고리즘" 리스트 4-4 : CARPET.C에 대응)

def carpet1(x, y, r):
    if r > 1:
        carpet1(x - 2 * r, y + 2 * r, r / 3)
        carpet1(x - 2 * r, y, r / 3)
        carpet1(x - 2 * r, y - 2 * r, r / 3)
        carpet1(x, y + 2 * r, r / 3)
        carpet1(x, y - 2 * r, r / 3)
        carpet1(x + 2 * r, y + 2 * r, r / 3)
        carpet1(x + 2 * r, y, r / 3)
        carpet1(x + 2 * r, y - 2 * r, r / 3)

        rect = Rectangle((x-r/6, y-r/6), r/3, r/3, color='blue')
        ax.add_patch(rect)


def carpet2(x, y, r):
    if r > 1:
        carpet2(x - 2 * r, y + 2 * r, r / 2)
        carpet2(x - 2 * r, y, r / 2)
        carpet2(x - 2 * r, y - 2 * r, r / 2)
        carpet2(x, y + 2 * r, r / 2)
        carpet2(x, y - 2 * r, r / 2)
        carpet2(x + 2 * r, y + 2 * r, r / 2)
        carpet2(x + 2 * r, y, r / 2)
        carpet2(x + 2 * r, y - 2 * r, r / 2)

        rect = Rectangle((x - r / 6, y - r / 6), r / 3, r / 3, color='blue')
        ax.add_patch(rect)


def carpet3(x, y, r):
    if r > 1:
        carpet3(x - r, y + r, r / 2)
        carpet3(x + r, y + r, r / 2)
        carpet3(x - r, y - r, r / 2)
        carpet3(x + r, y - r, r / 2)

        rect = Rectangle((x - r / 6, y - r / 6), r / 3, r / 3, color='blue')
        ax.add_patch(rect)

좌표값과 길이를 입력 받아서, 검은 바탕에 사각형의 1/3 위치(x-r/3, y-r/3)에 길이의 1/3 크기(r/3)의 하얀색 정사각형을 그리는 것입니다. 여기서 입력 받은 좌표값은 사각형의 중앙에 해당하는 값입니다. Rectangle patch 기준점은 사각형의 중앙이 아니라 좌측 아래이므로, 길이의 반(1/2)만큼 좌측 아래로 이동합니다. (x-r/3, y-r/3) -> (x-r/3/2, y-r/3/2)

3. 실행 코드

실행코드는 다음과 같습니다.("C로 배우는 알고리즘" 리스트 4-4 : CARPET.C에 대응)

if __name__ == '__main__':
    fig, ax = plt.subplots(1, 1)
    carpet1(0, 0, 60)
#    carpet2(0, 0, 50)
#    carpet3(0, 0, 100)
    ax.autoscale_view()
    plt.show()

세 개의 graph를 그리게 되는데, 각각을 버튼등을 눌러서 실시간으로 전환할 수 있으면 좋겠지만, 일단은 그리려는 그래프의 주석을 풀어서 실행시 그림 하나에 대해서만 동작하도록 했습니다.

carpet1(0, 0, 60)의 실행 화면은 다음과 같습니다.

carpet2(0, 0, 50)의 실행 화면은 다음과 같습니다. (실행시간이 많이 걸렸습니다.)

carpet3(0, 0, 100)의 실행 화면은 다음과 같습니다.

4. Tips

1. 세 개의 그림을 버튼을 눌러서 전환하고 싶었습니다. matplotlib에서 그림이 나올때 아래에 아래와 같은 toolbar가 있습니다.

여기에 "Forward"와 "Back"이 있어서 이 버튼을 이용할 수 있을까하고 이것 저것 찾아보았으나 찾을 수 없었습니다. 그러다가 링크의 설명을 보니, 다른 버튼인 "확대", "이동"등과 같이 사용하는 버튼으로 제가 사용하려는 용도가 아니라는 것을 알 수 있었습니다.

5. 코드

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