[04-04] 재귀 호출 - 원의 내부 영역 칠하기

1. 개요 & 알고리즘

"C로 배우는 알고리즘"에 설명된 내부 영역 그리기 알고리즘(Flood Fill)은 다음과 같습니다.

1. 현재 위치 (X, Y)의 점을 읽어 그것이 경계색이거나 이미 채워진 부분이면 끝낸다.

2. 현재 위치 (X, Y)의 점을 지정된 색으로 찍는다.

3. (X-1, Y)에 대해 영역을 칠하는 알고리즘을 실행한다.

4. (X+1, Y)에 대해 영역을 칠하는 알고리즘을 실행한다.

5. (X, Y-1)에 대해 영역을 칠하는 알고리즘을 실행한다.

6. (X, Y+1)에 대해 영역을 칠하는 알고리즘을 실행한다.

링크를 참고해서 matplotlib로 원을 그릴 수는 있었습니다. 그런데, 현재 위치 (X,Y)의 점을 읽는 방법을 찾을 수 없었습니다. 그래서 다른 방법을 사용했습니다. 다행히 예제가 원 내부를 칠하는 것이라서, 현재 위치 (X,Y)가 원 내부에 있는지를 수치적으로 판단해서 점을 찍을지 끝낼지를 판단하도록 했습니다.

이렇게 해서 점으로라도 원 내부를 칠할 수 있었지만, 알고리즘의 3, 4, 5, 6 단계에서 동일한 위치에 대해서 재귀 호출이 중복해서 일어납니다. 예를 들며 (0,0)에 대해서 점을 찍는 동작이 현재 위치 (0,0)에 대해서도 일어나지만, 현재 위치 (1,0) 위치에서 (X-1, Y) 재귀 함수를 호출 하는 경우에도 일어납니다. 동일한 위치에 대해서 재귀 호출이 중복되어 일어나는 바람에 Python에서는 재귀 호출이 너무 많다는 에러가 발생했습니다. Python의 List를 이용해서 저장하고, 검색해서 가능한한 중복 호출이 일어나지 않도록 했습니다.

2. 동작 코드

원을 그리는 동작 코드는 다음과 같습니다. 반지름(radius)는 global 변수로 사용했습니다.

def create_circle():
    circle= plt.Circle((0,0), radius= radius, fill=False)
    return circle


def show_shape(patch):
    ax=plt.gca()
    ax.add_patch(patch)
    plt.axis('scaled')

plt.Circle()에서 "fill=False"를 사용해서 원 둘레만 그렸습니다. "fill=False"를 생략하면 색칠한 원이 그려집니다.

위 함수들을 이용해서 원을 그리는 코드는 다음과 같습니다.

c = create_circle()
show_shape(c)
plt.show()

반복 실행을 최대한 줄이기 위해서 List를 이용해서 찍은 점을 저장했는데, List에서 점의 포함 여부를 확인하는 방법은 링크를 참고했습니다. List에 포함 여부를 확인하는 방법은 아래와 같이 매우 간단합니다.

if 'abc' in my_list:

이를 이용해서 원 내부에만 점을 찍는 함수는 다음과 같이 작성했습니다.

def recur_fill(x, y, pixel_list):
    if x > radius or x < -radius:
        return
    else:
        y_ref = math.sqrt(radius*radius - x*x)

    if y < (-1) * y_ref or y > y_ref:
        return
    else:
        plt.plot([x], [y], 'bo')
        pixel_list.append([x, y])

        if not [x-step, y] in pixel_list:
            recur_fill(x-step, y, pixel_list)

        if not [x+step, y] in pixel_list:
            recur_fill(x+step, y, pixel_list)

        if not [x, y-step] in pixel_list:
            recur_fill(x, y-step, pixel_list)

        if not [x, y+step] in pixel_list:
            recur_fill(x, y+step, pixel_list)

작업하려는 도형이 원이었기 때문에 억지스럽게 작성한 코드로 실용성은 없습니다.

3. 실행 코드

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

if __name__ == '__main__':
    c = create_circle()
    show_shape(c)
    pixel_list = []
    recur_fill(0, 0, pixel_list)
    plt.show()

결과는 다음과 같습니다.

재귀 호출을 비재귀 호출 함수로 변경하는 작업은 진행하지 않았습니다.

4. Tips

Python에서 "(-1)*variable"은 그냥 "-variable"로 표현해도 됩니다.

5. 코드

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

6. 기타

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