원을 그리기 위해서는 원의 방정식을 이용하면 된다. 반지름이 $r$인 경우에 원점이 중심인 원은 $x^2 + y^2 = r^2$이므로 (중심이 원점이 아닌 경우는 단순 평행 이동만 하면 되기 때문에 따로 취급하지 않는다), $x$를 독립변수로 잡으면 $y= \sqrt {r^2 - y^2}$으로 주어져서 1/2 사분면을 그릴 수 있다. 그리고 부호를 반대로 하면 3/4 분면에 그려진다. 그러나 $x$가 $r$에 근접하는 경우 $y$의 변화율이 급격해져서 $y$값이 연속적으로 그려지지 않는다. 이 문제는 전체 4 사분면을 45도 단위로 8개 영역으로 쪼개서 $x$와 $y$의 역할을 적당히 바꾸면서 그리면 이러한 문제를 피할 수 있다. 그러나, 여전히 실수 연산을 수행해야 하는 문제가 남아 있다. 이를 피하는 방법을 고안하도록 하자. 힌트는 Bresenham의 라인 알고리즘에서 얻을 수 있다. 우선, 영역을 $x = 0$에서 $x = y$인 90-도에서 45-도 사이의 구간만 생각하자. 이 구간에서 $y$의 변화율의 크기는 항상 0에서 1 사이 이므로, 8-방향으로 연결성을 갖도록 그리려면 현재의 점이 $(x, y)$로 주어지는 경우
(x, y) ---> (x+1, y) 변화율 = 0;
(x+1, y-1) 변화율 = 1 (절대값)의 두 가지 경우만 있다. 그럼 이 두 점 중 어느 것을 선택을 해야 하는가? 이것을 판별하기 위한 식은 이 두 점의 중심인 $(x, y - 1/2)$이 원의 내부에 있는가 또는 외부에 있는가를 보고서 결정하면 된다.
(x+1, y-1/2) 이 원의 내부점인 경우---->(x+1, y) 선택
원의 외부점인 경우---->(x+1, y-1) 선택;하면 각각의 상황에서 보다 정확한 원에 가까운 점을 선택한 것이 된다. 다음 점에서도 동일한 과정을 거치면 된다.
그러면 $(x+1, y-1/2)$가 원의 내부점인지 외부점인지를 항상 계산해야 하는가? 매 스텝마다 이것을 계산을 할 필요는 없다. 왜냐면 처음 $(0, r-1/2)$에서 계산을 하고
d = x^2+y^2-r^2 at (0, r-1/2) ;
= (5-4*r)/4 ; -> 이런 식으로 표현을 하는 것은 정수 연산만으로
하기 위해서 계산 우선 순위를 조절한 것임.이것과, $F(x, y)=x^2-y^2-r^2$ 라고 할 때,
(1), $(x+1, y)$를 선택할 때 새로운 $d$값은 $(x+2, y-1/2)$에서 계산하므로
d_old = F(x+1, y-1/2) = (x+1)^2+(y-1/2)^2-r^2 ;
d_new = F(x+2, y-1/2) = d_old + 2*(x+1) + 1;(2), $(x+1, y-1)$를 선택할 때, 새로운 $d$값은 $(x+2, y-1-1/2)$에서 계산하므로
d_old = F(x+1, y-1/2) = (x+1)^2+(y-1/2)^2-r^2 ;
d_new = F(x+2, y-3/2) = d_old + 2 * ((x+1) -(y-1)) + 1;인 관계를 이용하면 쉽게 정수 연산만으로 $d$값을 업데이트할 수 있다. 따라서 전체적인 코드는
int x = 0, y = r ;
int d = (5 - 4 * r) / 4;
setPixel (x, y) ;
while ( x < y ) {
++x ;
if (d < 0) // (x+1, y) 선택;
d += 2*x + 1; // ++x와 연관해서 잘 살펴야 한다.
else { // (x+1, y-1) 선택;
--y ;
d += 2 * (x - y) + 1; // ++x,--y;
}
setPixel(x, y);
};8 방향 대칭성으로 인해 점 $(x, y)$를 그리면 아래의 점도 그려야 한다 (처음 점 $(0, r)$은 4방향만, 그리고 $x=y$인 경우도 마찬가지나 따로 분리하기보다는 그냥 그리는 것이 더 낫다).
{(x,-y), (-x,y), (-x,-y), (y,x), (y,-x), (-y,x),(-y,-x)}단, 원의 중심이 원점이 아닐 경우는 전체적으로 평행이동을 시키면 된다.
'Computational Geometry' 카테고리의 다른 글
| Triangulation을 이용한 Imge Effect (0) | 2009.12.18 |
|---|---|
| Ellipse Drawing Algorithm (0) | 2008.06.04 |
| Wu's Line Algorithm (1) | 2008.06.02 |
| Brute Force Triangulation (1) | 2008.05.28 |
| Polygon Triangulation (II) (0) | 2008.05.26 |
