원을 그리기 위해서는 원의 방정식을 이용하면 된다.  반지름이 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
Circle Drawing Algorithm  (1) 2008.06.03
Wu's Line Algorithm  (1) 2008.06.02
삼각형 외접원의 Inclusion Test  (0) 2008.05.29
Brute Force Triangulation  (0) 2008.05.28
Posted by helloktk