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

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



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

에서 다운로드 가능.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#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, 111113);
    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++ 1;
        }
        else {
            p += 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");
    }
}
cs





+ Recent posts