문제) Modify Midpoint circle drawing algorithm to draw Ellipses
타원의 방정식)
. (x^2 / a^2) + (y^2 / b^2) = 1
. (b^2 * x^2) + (a^2 * y^2) = (b^2 * a^2)
. (b^2 * x^2) + (a^2 * y^2) - (b^2 * a^2)
(음수이면 타원의 외부, 양수이면 타원의 내부, 0이면 타원 위의 점)
. EllipseError(xi, yi) = abs((b^2 * xi^2) + (a^2 * yi^2) - (b^2 * a^2))
방법)
. 1사분면(quadrant)에 대해 계산하고 4-way symmetry를 이용하여 2,3,4분면에 그린다.
. 1사분면에서 tangent line의 slope는 항상 음수
. tangent line의 slope가 -1보다 큰 곳과 작은 곳을 나누어 계산한다.
구현) Pseudo code(Algol 코드와 유사함)
Procedure PlotEllipse(CX, CY, XRadius, YRadius : Integer);
var X, Y, XChange, YChange, EllipseError, TwoASquare, TwoBSquare, StoppingX, stoppingY : Integer;
begin
{ CX : 타원의 중심의 X좌표 }
{ CY : 타원의 중심의 Y좌표 }
TwoASquare := 2 * XRadius * XRadius; { 제곱을 미리 계산 }
TwoBSquare := 2 * YRadius * YRadius;
{ 동 -> 북 }
X:= XRadius;
Y:= 0;
XChange := YRadius*YRadius*(1-2*XRadius);
YChange := XRadius*XRadius;
EllipseError := 0;
StoppingX := TwoBSquare*XRadius
StoppingY := 0;
while(StoppingX >= StoppingY) do {1st set of points, y'>-1}
begin
Plot4EllipsePoints(X,Y);
++Y;
StoppingY := StoppingY + TwoASquare;
EllipseError := EllipseError + YChange;
YChange := YChange + TwoASquare;
if ((2*EllipseError + XChange) > 0) then
begin
--X;
StoppingX := StoppingX - TwoBSquare;
EllipseError := EllipseError + XChange;
XChange := XChange + TwoBSquare
end
end;
{ 북 -> 동 }
X := 0;
Y := YRadius;
XChange := YRadius*YRadius;
YChange := XRadius*XRadius*(1-2*YRadius);
EllipseError := 0;
StoppingX := 0;
while (StoppingX <= StoppingY) do {2nd set of points, y' < -1}
begin
Plot4EllipsePoints(X,Y); {subroutine appears later}
++X;
StoppingX := StoppingX + TwoBSquare;
EllipseError := EllipseError + Xchange;
XChange := XChange + TwoBSquare;
if ((2*EllipseError + YChange) > 0) then
begin
--Y;
StoppingY := StoppingY - TwoASquare;
EllipseError := EllipseError + YChange;
YChange := YChange + TwoASquare
end
end
end; {procedure PlotEllipse}
{ 4-way symmetry point draw }
procedure Plot4EllipsePoints(X, Y : integer)
begin
display(CX+X,CY+Y); {point in quadrant 1}
display(CX-X,CY+Y); {point in quadrant 2}
display(CX-X,CY-Y); {point in quadrant 3}
display(CX+X,CY-Y); {point in quadrant 4}
end; {procedure Plot4EllipsePoints}
참고)
Jerry R. Van Aken, An Efficient Ellipse-Drawing Algorithm, IEEE Computer Graphics & Applications, September 1984, pp.24~35
A Fast Bresenham Type Algorithm For Drawing Ellipses : http://homepage.smc.edu/kennedy_john/BELIPSE.PDF