Midpoint circle algorithm

아이디어 : 원의 대칭성 활용하여 각도가 0°~45°일 때만 그리고, 나머지 부분은 대칭이동하여 그린다.

반지름이 12인 원을 그린다고 가정하자.

8분원을 그릴 때, 다음 두 조건을 만족한다.

1. y값은 항상 1씩 증가하는 한다
2. x값은 같거나 1 감소한다
   

x가 1감소할 때 다음 포인트인 $P_{k+1}$는 다음 2개 중 하나이어야 한다.

Midpoint algorithm은 중심 위치에서 가까운 점을 선택하여 그리게 된다.

1. midpoint가 원 안에 있는 경우
   $x(next) = x(current)$
2. midpoint가 원 밖에 있는 경우
   $x(next) = x(current) - 1$
   

midpoint가 원 내부 혹은 외부에 있는지 판단하는 방법

원점부터 midpoint까지의 거리와 반지름을 비교함으로써 판단할 수 있다.

$P_{k}$가 의미하는 것은 부호를 통해, k번째 x에서 midpoint가 원 내부에 위치하는지 외부에 위치하는지에 대한 정보만 가지고 있다.

$P_{k+1}$ 유도 과정

2가지 알고 있는 사실을 통해 $P_{k+1}$ 을 유도할 수 있다.

결론

$P_{k+1}$은 다음과 같은 식을 통해 구할 수 있다.
$P_{k}$를 알고 있다면, $P_{k+1}$를 구할 수 있고, $P_{k+1}$의 부호에 따라서 다음 point를 결정할 수 있다.

이제 우리는 8분원을 그리기위한 모든 정보를 찾았다.
8분원을 모두 그릴 때까지 point를 구하고, 8분원을 모두 그린 경우 대칭이동을 통해 원의 나머지 부분을 그릴 수 있다.

참고

---

midpoint circle drawing site
midpoint circle drawing youtube