[04-05] 재귀 호출 - 프랙탈(양탄자)

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

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

6. 기타

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