Geometry & Recognition

Bezier 곡선을 이용한 원의 근사처럼 타원을 근사해보도록 하자. 원점을 중심으로 하고 장축 반지름이 $a$, 단축 반지름이 $b$인 타원을 1사분에서 3차 Bezier curve을 이용해서 근사하려면 4개의 control point가 필요하다. 원의 경우처럼, 끝점에서 접선의 기울기를 같게 하는 조건을 부여하면 control point는

$$\mathbf {P_0} = (0, b), \quad \mathbf {P}_1 = (ka, b), \quad \mathbf {P}_2 =( a, kb),\quad \mathbf {P}_3 = (a, 0)$$

로 잡을 수 있다. 따라서

$$\mathbf {B}(t) = (1-t^3) \mathbf {P}_0 + 3t(1-t)^2 \mathbf {P}_1 + 3t^2 (1-t) \mathbf {P}_2 + t^3 \mathbf {P}_3 = \left(\begin {array}{c} a x(t) \\ b y(t) \end {array}\right) $$

$$ x(t) = 3k (1-t)^2 t + 3 (1-t) t^2 + t^3 $$

$$ y(t) = 3k t^2 (1-t) + 3t(1-t)^2 + (1-t)^3 $$

$t=1/2$일 때 $(a/\sqrt {2}, b/\sqrt {2})$을 통과하는 조건을 부여하면, 원과 마찬가지로

$$ k = \frac {4}{3}(\sqrt {2}-1)= 0.5522847498...$$

을 얻는다. Mahalanobis measure를 기준으로 거리를 측정하면  타원의 경우도 벗어남 에러가

$$ \Delta (t) = \sqrt { \frac {B_x^2(t)}{a^2} + \frac {B_y^2(t)}{b^2} }  -1 =\sqrt {x^2(t)+y^2(t)}-1$$

원의 경우와 같음을 쉽게 알 수 있다.

회전된 타원; 

2사분면: $(x, y) \rightarrow (-x, y)$

3사분면: $(x, y) \rightarrow (-x, -y)$

4사분면: $(x, y) \rightarrow (x, -y)$

void BezierEllipse(CDC *pDC, CPoint center, double a, double b) {
    const double k = 0.5522847498;
    CPen red(PS_SOLID, 3, RGB(0xFF, 0, 0));
    CPen *pOld = pDC->SelectObject(&red);
    CPoint P[4];  //control pts;
    P[0] = CPoint(center.x,                    int(center.y - b + 0.5));
    P[1] = CPoint(int(center.x + k * a + 0.5), int(center.y - b + 0.5));
    P[2] = CPoint(int(center.x + a + 0.5),     int(center.y - k * b + 0.5));
    P[3] = CPoint(int(center.x + a + 0.5),     center.y);
    pDC->PolyBezier(P, 4);
    pDC->SelectObject(pOld);
}

void BezierEllipse(CDC *pDC, CPoint center, double a, double b, double ang) {
    const double k = 0.5522847498;
    const double cosang = cos(ang);
    const double sinang = sin(ang);
    CPoint P[4];
    double x[4], y[4], xt[4], yt[4];
    //1사분면: 
    x[0] = 0,     y[0] = b;
    x[1] = k * a, y[1] = b;
    x[2] = a,     y[2] = k * b;
    x[3] = a,     y[3] = 0;
    CPen red(PS_SOLID, 3, RGB(0xFF, 0, 0));
    CPen *pOld = pDC->SelectObject(&red);    
    for (int i = 0; i < 4; i++) {
        xt[i] = x[i] * cosang - y[i] * sinang;
        yt[i] = x[i] * sinang + y[i] * cosang;
        P[i] = CPoint(int(center.x + xt[i] + 0.5), int(center.y - yt[i] + 0.5));
    }
    pDC->PolyBezier(P, 4);
    pDC->SelectObject(pOld);
    //4사분면;(x, -y);
    CPen blue(PS_SOLID, 3, RGB(0, 0, 0xFF));
    pOld = pDC->SelectObject(&blue);
    for (int i = 0; i < 4; i++) {
        xt[i] = x[i] * cosang - (-y[i]) * sinang;
        yt[i] = x[i] * sinang + (-y[i]) * cosang;
        P[i] = CPoint(int(center.x + xt[i] + 0.5), int(center.y - yt[i] + 0.5));
    }
    pDC->PolyBezier(P, 4);
    pDC->SelectObject(pOld);
    //3-사분면;(-x,-y)
    CPen green(PS_SOLID, 3, RGB(0, 0xFF, 0));
    pOld = pDC->SelectObject(&green);
    for (int i = 0; i < 4; i++) {
        xt[i] = (-x[i]) * cosang - (-y[i]) * sinang;
        yt[i] = (-x[i]) * sinang + (-y[i]) * cosang;
        P[i] = CPoint(int(center.x + xt[i] + 0.5), int(center.y - yt[i] + 0.5));
    }
    pDC->PolyBezier(P, 4);
    pDC->SelectObject(pOld);
    //2사분면;(-x,y);    
    CPen magenta(PS_SOLID, 3, RGB(0xFF, 0, 0xFF));
    pOld = pDC->SelectObject(&magenta);
    for (int i = 0; i < 4; i++) {
        xt[i] = (-x[i]) * cosang - y[i] * sinang;
        yt[i] = (-x[i]) * sinang + y[i] * cosang;
        P[i] = CPoint(int(center.x + xt[i] + 0.5), int(center.y - yt[i] + 0.5));
    }
    pDC->PolyBezier(P, 4);
    pDC->SelectObject(pOld);
}

한 개의 Bezier 곡선을 이용해서 원을 표현할 수 없음은 잘 알려진 사실이다. 그럼 Bezier 곡선을 이용해서 얼마나 원(호)을 잘 근사할 수 있을까? 원점에 중심을 둔 반지름 1인 원의 1 사분면 원호가 3차 Bezier 곡선으로 얼마나 잘 표현되는지 알아보자. 3차 Bezier 곡선은 4개의 control point $\{ \mathbf {P}_i | i=0,1,2, 3\}$이 주어진 경우

$$ \mathbf {B}(t) = (1-t^3) \mathbf {P}_0 + 3t(1-t)^2 \mathbf {P}_1 + 3t^2 (1-t) \mathbf {P}_2 + t^3 \mathbf {P}_3$$

으로 표현된다. 원호 근사에 필요한 control point의 위치는 다음 조건을 부여하면 얻을 수 있다.

(1) 시작점($t=0$)과 끝점($t=1$)은 원 위에 있어야 하므로

$$\mathbf {B}(t=0) = (0,1) \quad \rightarrow \quad \mathbf {P_0} = (0,1),$$

$$\mathbf {B}(t=1) = (1,0) \quad \rightarrow \quad \mathbf {P_3} = (1,0).$$

또 시작점과 끝점에서 접선이 원에도 접해야 하므로

$$ {\mathbf {B}'}(t=0) \propto (1,0)\quad \text {and}\quad {\mathbf {B}'}(t=1)\propto (0,-1)$$

에서 나머지 두 control point는 다음과 같이 쓸 수 있다:

$$ \mathbf {P}_1 = (k, 1), \quad \mathbf {P}_2 = (1, k).$$

그럼 $k$ 값은 어떻게 정할 수 있을까?

(2-1) Bezier 곡선의 중간지점이  원 위에 있도록 조건을 부여하면

$$ \mathbf {B}(t=1/2) = (1/\sqrt {2}, 1/\sqrt {2})$$

을 얻고, 이를 이용하면

$$k= \frac {4}{3} (\sqrt {2}-1) = 0.5522847498...$$

을 얻는다.

그럼 원에서 얼마나 벗어날까? 원 중심에서 거리를 차이를 구해보면 Bezier 곡선이 항상 원의 바깥으로 치우쳐 있음을 알 수 있다:

$$\Delta(t) = ||\mathbf {B}(t)||-1\ge 0$$ 

최대로 벗어나는 정도는 $t=(3\pm \sqrt{3})/6$일 때 $\Delta_\text {max}=\frac{1}{3}\sqrt{ \frac{71}{6}-2\sqrt{2}}-1=0.00027253...$이므로 대부분의 경우 크게 벗어남이 없는 원의 근사를 준다.

(2-2) $t=1/2$에서 Bezier 곡선이 원을 통과하는 조건 대신 원에서 벗어남을 최소로 하는 조건을 부여하면 더 좋은 근사를 얻을 수 있다:

$$k=\text{argmin}|\Delta|_\text{max}$$

이 경우  Bezier 곡선은 원의 바깥에 놓이지 않고 교차하게 된다. $t=1/2$에서 최솟값, $t=\frac{1}{2}\left(1\pm \frac{\sqrt{3k^2+20k -12}}{2-3k}\right) $일 때 최댓값을 가지는데, 두 값의 절댓값이 같게 되려면(closed form이 없다)

$$ k = 0.551915023...$$

을 선택해야 하고, 이때 벗어남의 최댓값은 $|\Delta|_\text{max} =  0.00019607...$이므로 더 좋은 근사가 된다.

(2-3) 또 다른 제한조건은 없을까? Bezier 곡선이 만드는 면적이 사분원의 면적을 표현하도록 제한을 가하는 경우:

$$\frac{\pi}{4} = \int_{0}^{1} \frac{1}{2}\left( B_y B'_x - B_x B'_y\right) dt $$

$$ = \int_0^1  \left(-\frac{3}{2} \left(3 k^2 (t-1)^2 t^2+k \left(-2 t^4+4 t^3-6 t^2+4 t-1\right)+2 (t-1) t\right) \right)dt $$

$$= \frac{1}{2}+\frac{3k}{5}-\frac{3k^2}{20}$$ 에서 

$$ k = 2 - \sqrt{ \frac{22 - 5 \pi }{3}} =0.551778477...$$

이다. 이 경우 면적은 같으나 벗어남 오차는 $t=1/2$일 때

$$|\Delta |_\text{max} = \frac{1}{8} \sqrt{332-40 \sqrt{66-15 \pi }-30 \pi }-1= 0.00026849...$$

로 주어지는데, 중심을 지나는 경우보다는 벗어남이 작지만 최소는 아니다.

(2-4) Bezier 곡선의 길이가 원주가 되는 제한조건을 걸 수도 있다:

$$\frac{\pi}{2}  = \int_0^1\sqrt{ (B'_x)^2 + (B'_y)^2}dt.$$

그런데 우측 적분이 closed form으로 주어지지 않는다. 때문에 $k$ 값을 구하기 위해서 전적으로 numerical method에 의존해야 되는데,  그 결과만 쓰면

$$k=0.551777131...$$