Geometry & Recognition

타원도 기본적으로 원 그리기와 동일한 알고리즘을 이용하여 그릴 수 있다. 하지만 원과 달리 좀 더 고려할 부분이 있다. 전체 영역을 $45^\circ$씩 8개 영역으로 나눈 후 한 영역에서만 계산하고 나머지는 대칭성을 이용하는 방법을 타원에는 바로 적용이 어렵다. 원에서 $45^\circ$ 기준선은 접선의 기울기가 $\frac{dy}{dx} = -1$인 점과 원점을 잇는 선분인데 타원에서는 이 관계가 성립하지 않는다. 타원 방정식 $\frac{x^2 }{ a^2} +\frac{ y^2}{b^2} = 1$ 에서 접선의 기울기가 $-1$인 지점은

$$x = \frac{a^2 }{ \sqrt {a^2  + b^2 }} , \quad y = \frac{ b^2 }{ \sqrt {a^2  + b^2 }}$$

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

픽셀 $(x_k , y_k)$에  점이 찍히면 다음은 어느 픽셀에 점을 찍어야 할까? $0\ge \text{기울기}\ge-1$이므로 오른쪽 옆이나 또는 오른쪽 아래 픽셀이 될 것이다. 이를 판별하는 식을 만들기 위해서 다음 식을 고려하자(나눗셈을 피하기 위해서 타원식에 $a^2b^2$을 곱했다): 

$$F(x, y) = b^2 x^2 + a^2 y^2 - a^2 b^2$$

$(x_k, y_k )$가 타원 위의 점이면 $F=0$을 만족한다. 다음 점이 찍힐 후보 위치가 $(x_k+1, y_k)$ 또는 $(x_k+1, y_k-1)$이므로 중간 위치(Midpoint)에서 $F$의 부호를 기준으로 판별하도록 하자:

$$d_k = F(x_k+1, y_k-1/2) \\ d_k < 0  \quad \text {이면} \quad (x_k+1, y_k),\\   d_k > 0\quad \text {이면} \quad (x_k+1, y_k-1)$$

이후에 판별식의 업데이트는 

$$d_k <0~인 ~경우:\quad           d_{k+1} = F(x_k+2, y_k-1/2) = d_{k} + b^2 ( 2 x_{k+1} +1)$$

$$d_k \ge 0 ~인 ~경우: \quad  d_{k+1} = F(x_k + 2, y_k -3/2) = d_{k} + b^2 (2x_{k+1} + 1)- 2a^2  y_{k+1}$$

로 주어진다. 시작 픽셀에서 판별식의 값은

$$ x_0 = 0, y_0 = b \quad \Rightarrow\quad d_0 = F(1, b-1/2) = (4 b^2 + a^2 (1 - 4 b)) / 4$$

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

$$2b^2 x + 2a^2 y \frac{dy}{dx} = 0 \\ \Rightarrow b^2 x = -a^2 y \frac{dy}{dx} = a^2 y \left| \frac{dy}{dx}\right|  \le a^2 y, \quad -1 \le \frac{dy}{dx} \le 0 \\ \therefore  \quad b^2 x \le a^2 y$$

이 조건이 만족하는 동안 $x$를 독립변수로 사용하여 그리기를 한다.

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

$$ d_k = F(x_k -1/2, y_k +1)$$

로 주어진다. 이 판별식의 업데이트는 

$$d_k <0~인 ~경우:\quad           d_{k+1} = F(x_k - 1/2, y_k+2) = d_{k} + a^2 ( 2 y_{k+1} +1)$$

$$d_k \ge 0 ~인 ~경우: \quad  d_{k+1} = F(x_k  -3 / 2, y_k +2) = d_{k} +a^2 (2x_{k+1} + 1)  - 2 b^2  x_{k+1}$$

로 주어진다. 그리고 시작 픽셀에서 판별식의 값은

$$ x_0 = a, y_0 = 0 \quad \Rightarrow\quad d_0 = 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) d +=  bb * (2 * x + 1);    // (x+1, y) 선택;
        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;
    }

last update: 2021.04.08;