알고리즘
2008/09/11 22:26
타원 그리기 _ bresenham
refer to: http://helloktk.tistory.com/entry/Ellipse-Drawing-Algorithm
타원도 원과 같은 알고리즘을 이용하면 된다.
그러나, 타원의 경우 45도씩 영역을 나누어서 계산할 수 없다. 기울기가 완만한 쪽을 선택해 이어진 선을 그린다고 생각해 볼 때, 기울기 dy/dx 가 1 또는 -1인 기준으로 나눠 생각해 볼 수 있다.
타원 방정식
x^2 / a^2 + y^2/b^2 = 1에서 기울기가 -1인 지점(1사분면에서 시계방향으로)은
x = a^2 / sqrt(a^2 + b^2)
y = b^2 / sqrt(a^2 + b^2)
이다.
따라서, 이 지점까지는 x를 독립변수로 잡아야 하고, 나머지는 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 값에 따라
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))
로 주어진다.
다음은, 어느 지점에서 y가 독립변수가 되는지 알아보자.
기울기가 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를 독립변수로 사용하여 그리면 된다. 이 구간에서 초기값은
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) 이므로 판별식은
d = F(x-1/2,y+1)
이고,
d<0 이면,
d_new = F(x-1/2, y+2) = d_old + a^2*(2*(y+1)+1)
d>0 이면,
d_new = F(x-3/2, y+2) = d_old + 2*b^2(x-1) + a^2*(2*(y+1)+1);
초기값은,
x0 = a,
y0 = 0,
d = F(a-1/2,0) = (4*a^2 + b^2*(1-4*a)) / 4;
이다.
as3 로 풀어보면,
