[Algorithm] Ellipse Drawing

문제) 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