원 그리기 미드포인트 알고리즘 (Midpoint circle algorithm)

격자 위에 원을 그려야 하거나 원 모양의 범위를 적용할 때

다음과 같은 식을 사용할 수 있다.

d가 0보다 크면 원 외부, d가 0보다 작으면 원 내부로 판단하는 것이다.

그러나 원을 그릴 때는 범위 내의 모든 점에 대입해야 할 뿐만 아니라 

매번 곱셈 연산을 3번 사용하여야 한다.

midpoint algorithm을 사용하면 이를 효율적으로 해결할 수 있다.

(원의 반지름이 n일 때 O(n))

원리

[그림1]

이 알고리즘의 원리는 결정된 한 점이 있을 때

한 칸 옆인 에 대응되는 y 값이 인지 인지 판단하는 것이다.  (위 그림에서 까만색 점 2개)

[그림 1]과 같이 원에 포함되는 것으로 결정된 한 점

가 있을 때 가 원의 내부인지 외부인지 판별하는 식은 아래와 같이 나타낼 수 있다.

중간점이 원 내부에 포함될 경우(p<=0), [그림1]에서 p의 위쪽 점을 선택하고,

p점이 원 밖일 경우(p>0) p의 아래쪽 점을 선택하는 것이다.

같은 방법으로 을 다음과 같이 점화식으로 나타낼 수 있다.

이제 을 결정해야 하는데,

위에서 서술한 바와 같이 의 부호에 따라 선택되므로 다음과 같이 나타낸다.

이를 활용하여 의 식을 간단히 하면

코드를 좀더 간편하게 하기 위해 대신 를 활용하면

최종적으로 아래 식을 얻을 수 있다.

한편 p의 초기값 는 위에서 식에 x의 초기값 0과 y의 초기값 r을 대입하여

5/4 - r이라는 것을 알 수 있다.

그런데 p의 점화식을 보면 초기값 외에는 모두 정수의 덧셈/뺄셈 연산이므로 (2x는 x+x로 계산)

p0을 int형으로 하고 1-r로 두어도 무방하다.

위 과정을 x > y가 되기 전까지 반복한다.

[그림 2]

실제로 그려보면 아래 그림과 같은 8분원(octant)을 얻을 수 있다.

[그림 3]

그리고 아래와 같이 대칭인 8개 점을 동시에 그리면 전체 원이 그려진다.

(x, y)

(x, -y)

(-x, y)

(-x, -y)

(y, x)

(y, -x)

(-y, x)

(-y, -x)

[그림 4]

4방향으로 뚫려 있는 부분은 따로 채워준다. 

[그림 5]

8개 부분을 따로 표시해 보면 아래 그림과 같다.

[그림 6]

원 채우기

y값이 변할 때 해당 y좌표에 해당하는 부분을 모두 칠하면

가운데 정사각형 영역을 제외한 부분을 채울 수 있다.(하단 코드 참조)

[그림 7]

나머지 정사각형 부분은 쉽게 채울 수 있다.(하단 코드 참조)

[그림 8]

모두 단색으로 칠해보면 아래 그림과 같은 원이 나온다.

[그림 9]

콘솔창에서는 한계가 있어 Javascript를 사용하여 그린 큰 원.

[그림 10]

구현

[그림 9]를 그릴 때 작성한 C언어 코드이다.

gcc컴파일러로 컴파일 가능하다.

나머지 코드들은

https://github.com/tibyte/algorithms/tree/master/bresenham/midpoint_circle

에서 다운로드 가능.

#include <bits/stdc++.h>
 
const int SIZE = 28;
 
void drawCircle(int arr[SIZE][SIZE], int r, int x, int y);
void display(int arr[SIZE][SIZE]);
 
int main(void)
{    
    int arr[SIZE][SIZE] = {0,};
    
    drawCircle(arr, 11, 11, 13);
    display(arr);
    
    return 0; 
}
 
 
void drawCircle(int arr[SIZE][SIZE], int r, int cx, int cy)
{
    int x, y;
    int p;
    
    x = 0;
    y = r;
    p = 1 - r;
    
    arr[y+cy][x+cx] = 1;
    arr[-y+cy][x+cx] = 1;
    arr[x+cy][y+cx] = 1;
    arr[x+cy][-y+cx] = 1;
 
    x = 1;
    while(x < y) {
        
        if(p < 0) {
            p += x+x + 1;
        }
        else {
            p += x+x + 1 -y-y;
            --y;
            for(int i=0; i<x; i++) {
                arr[y+cy][i+cx] = 1;
                arr[-y+cy][i+cx] = 1;
                arr[y+cy][-i+cx] = 1;
                arr[-y+cy][-i+cx] = 1;
                arr[i+cy][y+cx] = 1;
                arr[-i+cy][y+cx] = 1;
                arr[i+cy][-y+cx] = 1;
                arr[-i+cy][-y+cx] = 1;
            }
        }
        arr[y+cy][x+cx] = 1;
        arr[-y+cy][x+cx] = 1;
        arr[y+cy][-x+cx] = 1;
        arr[-y+cy][-x+cx] = 1;
        arr[x+cy][y+cx] = 1;
        arr[-x+cy][y+cx] = 1;
        arr[x+cy][-y+cx] = 1;
        arr[-x+cy][-y+cx] = 1;
        
        ++x; 
    }
 
    for(int i=cy-y+1; i<cy+y; i++) {
        for(int j=cx-y+1; j<cx+y; j++) {
            arr[i][j] = 1;
        }
    }
}
 
 
void display(int arr[SIZE][SIZE])
{    
    for(int i=0; i<SIZE; i++) {
        for(int j=0; j<SIZE; j++) {
            if(arr[i][j])
                printf("■");
            else
                printf("　");
        }
        printf("\n");
    }
}