Geometry & Recognition

원을 그리기 위해서는 원의 방정식을 이용하면 된다. 반지름이 $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)}

단, 원의 중심이 원점이 아닐 경우는 전체적으로 평행이동을 시키면 된다.