원의 8분의 1 그리기

그래픽스 관련 코딩 인터뷰 내용 중 하나

코딩 인터뷰에서 그래픽스와 관련되어 나올 수 있는 내용 중, 원의 1/8 그리기

원의 1/8 그리기

문제 내용

원의 1/8 부분을 그리는 다음 함수를 구현하라

void DrawEighthOfCircle(int radius)

위 함수를 구현하기 위해 다음 함수가 미리 제공된다.

void SetPixel(int x, int y)

문제 해설

위 문제에서 원을 1/8만 그리는 함수를 구현하라 한것은, 원을 1/8만 그리면, 대칭성을 통해 전체 원을 효율적으로 그릴수 있기 때문이다.

어떤 점(a, b)가 원 위의 한점이라고 하자. 해당 원을 가로지르는 45도와 -45도 기울기의 선분을 두개 그린 다음, 해당 선분을 기준으로 점 (a,b)를 대칭시켜 만들 수 있는 7개의 점들 모두 해당 원 위에 있기 때문이다. 해당 사항을 언급하여 인상을 주어라.
먼저, 공식 x*x + y*y = r*r를 활용하면 원을 그릴 수 있다. 여기서 원의 중점은 0, 0이라고 하자. 중점의 Shifting은 나중에 x에 (x-offsetX), y에 (y-offsetY)만 적용하면 된다.

x와 y값을 한번에 결정할 순 없으니, 두 변수 중 하나를 자유, 다른 하나를 해당 변수에 대한 종속 변수로 변환한다.

y = sqrt(r*r - x*x) or y = -sqrt(r*r - x*x)

우리는 x값을 먼저 변환하고 y값이 x 값에 따라가게 한다. 반대도 상관없다. 그런데 1/8만 그리면 되니까, y값이 음수인 경우는 제외하자.

y = sqrt(r*r - x*x)

여기서 x 값의 범위는 -radius 이상, radius 이하다.

그런데 우리는 원의 1/8만 그리면 되므로, 원을 위쪽 꼭대기인 지점에서 그릴것이다. 원을 그리기 시작하는 지점은 (0, radius)가 된다. 그리고 x 값의 범위는 0이상, radius * 1/2미만(또는 이하)가 된다.
왜냐면, 원을 오른쪽으로 그릴때 1/8 지점이란, 45도 기울기의 선분과 원이 1사분면에서 만나는 위치다. 해당 좌표의 값은 (radius * 1/2, radius * 1/2)가 된다.

다르게 말하면, 해당 좌표에서 원을 오른쪽으로 그려가면 x 값은 y 값보다 커지고, 왼쪽으로 되돌아가면 x값은 y값 보다 작아진다.
따라서 x 값의 범위를 0이상, radius * 1/2 이하라고 표현해도 되지만, x < y인 범위라고 표현해도 된다.

정리하면 다음과 같이 코드를 짠다.


void DrawEighthOfCircle(int radius) {
    int x = 0;
    int y = raidus;
    
    while(x < y) {
        float calculatedY = Math.Sqrt(radius * radius - x * x)
        int y = Math.CeilToInt(calculatedY);
        SetPixel(x, y);
        x++;
    }
}

여기서 y값으로 Math.Sqrt(radius * radius - x * x)를 곧장 대입하지 않았다는 것에 주의한다. 픽셀 좌표는 연속된 값이 아니다. 따라서 선분이 픽셀의 경계를 가로지는 경우를 처리하기 위해 위와 같이 반올림을 사용한다.