격자 위에 원을 그려야 하거나 원 모양의 범위를 적용할 때
다음과 같은 식을 사용할 수 있다.
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, 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"); } } | cs |
