Circle and ellipse

    A circle and ellips are basic output graphics primitives.

    A circle with a center in [xc, yc] and a radius r (half of the diameter) can be representated in the following formulas:
 

  • analytic representation : r2 = (x-x)2 + (y-yc)2,
  • implicit representation : (x-xc)2+ (y-yc) 2-r2 = 0.
  • parametric representation:
      • x = xc + r * cos(alfa)
      y = yc + r * sin(alfa),
    for alfa∈ <0, 2p>.

    A centered ellipse ( if axes are parallel with the co-ordinate axes) with a center in [xc, xc] is representated

    parametricaly:
    x = xc + a * cos(alfa) y = yc + b * sin(alfa),    for alfa ∈ <0, 2p> and a,b are the main axle and half-axle.

    implicitly:
        (x - xc)2       (y - yc)2
     ------------ + ------------ -1 = 0.
            a2                b2

    Rastering the circle

        It is known that a circle can be devided into 360 degrees. When looking at the circle it is obvious that the circle is symmetric with regard to the co-ordinate axis  x and y and the axes of quadrants as well (function x=y and x=-y). It holds for the circle with a center in (0,0), that if a point  (x, y) lies on the circle, then the points (y, x), (y, -x), (x, -y), (-x, -y), (-y, -x), (-y, x) and (-x, y) lie also on the circle. For defining all the point on the circle, it is sufficient to compute 1/8th of the arc of the circle ,  i.e. arc ranging from 0 to 45. Bresenham's algorithm for the rasterization of circle with a centre S=(Stred_X, Stred_Y) computes the position of points on this part. Every computed pixel is is representated on each octant of the raster plane :

     PutPixel(Stred_X + X, Stred_Y + Y)
    PutPixel(Stred_X + X, Stred_Y - Y)
    PutPixel(Stred_X - X, Stred_Y + Y)
    PutPixel(Stred_X - X, Stred_Y - Y)
    PutPixel(Stred_X + Y, Stred_Y + X)
    PutPixel(Stred_X + Y, Stred_Y - X)
    PutPixel(Stred_X - Y, Stred_Y + X)
    PutPixel(Stred_X - Y, Stred_Y - X).

    $$$APPLET

    Applet Select one point on circle.

    Applet : Drawing the circle, 8 symetric points
     
      
     Bresenham's algorithm for circle rastering :

// circle center xi,yi and point on circle xf,yf

public void circle(int xi, int yi, int xf, int yf) 
 {
 // calculate radius of circle
 int radius=(int)(Math.sqrt((xf-xi)*(xf-xi)+(yf-yi)*(yf-yi)));

 int d1 = 3 - (2 * radius);
 int x = 0,i1=x1,i2=x2;
 int y = radius;
 boolean  rov=true;

 // for one eights, while x is not >= y
 while (rov)
 {
 if  (x>=y){rov=false;}
 if (d1 < 0) 
 { d1 = d1 + (4 * x) + 6; }
 else
 { d1 = d1 + 4 * (x - y) + 10; // (1)
    y = y - 1;
 }

 // draw following circle points

   setpix((x1+x),(y1+y));
   setpix((x1+x),(y1-y));
   setpix((x1-x),(y1+y));
   setpix((x1-x),(y1-y));
   setpix((x1+y),(y1+x));
   setpix((x1+y),(y1-x));
   setpix((x1-y),(y1+x));
   setpix((x1-y),(y1-x));
   x++;
 }
}

    Values that are computed (x and y,see  the source code) are always changing, therefore they can not be computed in  advance. The only acceleration of the algorithm  can be done when  multiplying  by 4. The value (x-y) can be shifted twice to left at the bit writing.

    $$$APPLET

    Applet Draw a circle with input raster value

    Another method for the construction of a circle is rotation transformation.
      

    Algoritmus method for rotation transformation:

   int stredx=polx;   int stredy=poly; // circle center
   double p1;  // help variable
   int r; // radius r
   double pi=3.141592654;
   int poc_iter=12; // points on circle
   p1=poc_iter;
   double alfa=(2*pi)/p1; // rotation angle  

  // start point
  double x1=mx-polx;
  double y1=my-poly;
  double x2,y2; 

  for (int i=0;i < poc_iter;i++)
     {
        // rotation of point x1, y1 around center about angle alpha
        x2=x1*Math.cos(alfa) - y1*Math.sin(alfa);
        y2=x1*Math.sin(alfa) + y1*Math.cos(alfa);
 
        // Draw line from [x1,y1] to [x2,y2]
        go.drawLine(polx+(int)(x1),poly+(int)(y1),polx+(int)(x2),poly+(int)(y2));        

        x1=x2;y1=y2;
      } 
    $$$APPLET

    Applet Draw circle with method of transformation of rotation, define point on circle

        To accelerate the computation, it is recommented to compute the value of sinus ranging from 0 to 450 degrees in advance.

    $$$APPLET

    Applet Draw circle, define point on circle

    Rastring of ellipse

        When looking at the circle representation on a graphics device ,  which distance between the rows of pixles is different from the distance between the columns, it is obvious that the circle on the screen looks like an ellipse.

         The construction of a centred ellipse can be done by the Bresenham's algorithm, similarly as at the circle,
    while we have to compute the values as a quadrant  of a circle.

    $$$APPLET

    Applet Ellipse with center in point S[x,y] axes a a b

    $$$APPLET

    Ellipse select corner point for new ellipse. Author Marián Rojko

    Source code