타원도 원과 마찬가지의 알고리즘을 이용하여서 그림을 그릴 수 있다. 그러나, 타원의 경우는 좀 더 복잡함이 수반된다. 전체 영역을 45도씩 8개의 영역으로 나누고, 한 영역에서만 계산하고 나머지는 대칭성을 이용하는 방법을 바로 타원에는 적용이 불가능하다. 우선 45도는 기울기가 dy/dx = -1인 점을 기준으로 하였는데 타원에서는 이것이 성립하지 않는다.

타원의 방정식 x^2 / a^2 + y^2/b^2 = 1 에서 기울기가 1인 지점은 (1사분면에서 y축에서 시계방향으로 회전시)

 

        x = a^2 / sqrt(a^2 + b^2),
        y = b^2 / sqrt(a^2 + b^2)

 

로 주어진다. 따라서 이 지점까지는 x를 독립변수로 잡아야 하고, 나머지 y = 0까지의 (1사분면에서)는 y를 독립변수로 잡아야 한다. 여타의 사분면은 대칭성을 이용하면 바로 그릴 수 있다.

사용자 삽입 이미지


타원의 경우도 원과 마찬가지로, 다음 점을 선택하는 판별식을 만들 수 있다. 현재의 점이 (x, y) 인 경우에 가능한 다음 점은 원과 똑같이 (x+1. y), (x+1, y-1)인데, 이 두 점의 중간점에서의 타원 내부인가 외부인가를 가지고 결정하면 된다.

        
F(x, y) = b^2 * x^2 + a^2 * y^2
a^2 *b^2;

 

라고 놓으면, 우리가 사용하는 판별식은


         d = F(x+1, y-1/2)

 

이다. 따라서,

        
d <0  이면 -
à  (x+1, y) ;

         d >0  이면 -à (x+1, y-1)


을 선택하게 된다. 각각의 선택이 이루어 진 후에 판별식의 값도 업데이트 되어야 하는데,


        
d_old  < 0 인 경우는

             d_new = F(x+2, y) = d_old + b^2 * ( 2 * (x+1) + 1);

         d_old  > 0 인 경우는

             d_new = F(x+2, y-3/2) =d_old + b^2* ( 2*(x+1) + 1) a^2 *(2*(y-1))       


로 주어진다.

이제 다음 문제는 x가 독립변수로써 얼마나 사용되고, 어느 지점에서 y가 독립변수가 되어야 하는가 이다. 이것은 기울기가 dy /dx 가 0에서 -1 사이인 지점까지가 x가 독립변수이므로,  우선 타원식을 미분하면

           b^2 * x + a^2 * y (dy/dx) = 0;
           ==>     b^2 * x  = - a^2 * y * (dy/dx) = a^2 * y * |dy/dx| <= a^2 * y ,   -1 <= dy/dx <=0;
           ==>     b^2 * x  <= a^2 * y ;

이 조건이 만족하는 동안 x 를 독립변수로 사용하여 그리기를 한다. x 가 독립변수인 구간에서는 초기값들은


        
x0 = 0,  y0=b,
         d = (4*b^2 + a^2*(1-4*b))/4;


로 주어진다.
 

y가 독립변수인 구간으로 넘어가자. 이 경우는 x=a, y=0 에서 출발하면 위 영역에서 x와 y의 역할을 바꾼 방식이 된다. 주어지는 경우에 다음 점 후보는 (x, y+1) 또는 (x-1, y+1)이다. 중간점은 (x-1/2, y+1)이므로 판별식은


        
d = F(x-1/2, y+1)


로 주어진다. 이 판별식에 따라서


        
d < 0 이면  (x, y)
à (x, y+1)

d_new = F(x-1/2, y+2)= d_old + a^2*(2*(y+1)+1)

         d > 0 이면 (x, y)à (x-1, y+1)

d_new = F(x-3/2, y+2)= d_old - 2*b^2*(x-1)+ a^2*(2*(y+1)+1);


로 주어진다. 초기값은

          x0=a, y=0 ;
          d = F(a-1/2, 0) =   (4*a^2 + b^2*(1 - 4*a)) / 4;

이다.


전체적인 코드는
// setPixel(CDC *pDC, int x, int y)에 (x,y),(-x, y), (x,-y),(-x,-y) 를 동시에 그리도록 구현이 되어야
// 한다. 그리고 중심이 원점이 아닌 경우에는 평행이동시켜야 한다.
    int x = 0, y = b ;
    int aa = a*a ;
    int bb = b*b ;
    int d = (4*bb + aa*(1-4*b))/4 ;


    setPixel (pDC, x, y) ;    
    while ( bb * x < aa * y) {
        ++x ;
        if (d < 0) {                           // (x+1, y) 선택;
            d +=  bb * (2 * x + 1);
        }
        else {                                // (x+1, y-1) 선택;
            --y ;
            d += bb*(2 * x + 1) - 2 * aa * y ;
        }
        setPixel(pDC, x, y);

    };
    //y-독립변수 구간;
    x = a, y = 0;
    d = (4*aa + bb*(1-4*a))/4;
    setPixel(pDC, x, y) ;
    while(bb * x > aa * y) {
        ++y ;
        if(d < 0) {
            d += aa*(2*y + 1);
        } else {
            --x ;
            d += - 2*bb*x + aa*(2*y + 1);  
        }
        setPixel(pDC, x, y);
    }

사용자 삽입 이미지


물론 실수연산을 하면, 아래의 코드로 타원을 그릴 수 있다. 접선의 기울기의 크기 |dy/dx| = 1 인 점을 기준으로 하여 그 값이 1 보다 작은 지점에서는 x를 독립변수로, 큰 지점에서는 y를 독립변수로 잡으면,
          x-구간    ===>  b^2 * x < a^2 * y;
          y-구간    ===>  b^2 * x > a^2 * y;
이므로, 아래처럼 쓸 수 가 있다:

    int aa = a*a, bb = b*b;
    x = 0; y=b;
    while (bb*x <= aa*y)
    {
        y = (int)((double)b/a * sqrt(aa - x*x) + 0.5);
        setPixel(pDC, x, y);
        ++x;
    }
    y = 0;
    while (bb*x > aa*y)
    {
        x = (int)((double)a/b * sqrt(bb - y*y) + 0.5);
        setPixel(pDC, x, y) ;
        ++y;
    }


'Computational Geometry' 카테고리의 다른 글

삼각형 채우기  (0) 2009.12.19
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
Posted by helloktk