[Computer Graphics] circle and ellipse drawing – MATLAB implementation

This is the second day of my participation in the November Gwen Challenge. Check out the details: the last Gwen Challenge 2021

1 the introduction

The core algorithm of circle and ellipse drawing is also Bresenham midpoint algorithm, but the conditions of demarcation point are different.

Because the symmetry of circle and ellipse is also different, such as circle is one-eighth symmetry, and ellipse is one-fourth symmetry, so the drawing method is also different.

2 ideas

2.1 round

Let’s assume that starting at (0,R), when x=y, the normal vector in the x direction is equal to the normal vector in the y direction.

Therefore, only one eighth arc is drawn, and then the whole circle is drawn according to symmetry.

The approximate steps of the algorithm are as follows:

1. First, the standard equation of the circle with the center of the circle at the origin is transformed into an implicit form: F(x,y)=x2+y2−R2F(x,y)=x^2+y^ 2-r ^2F(x,y)=x2+y2−R2

2. Recursively judge the position relation between the midpoint and the arc of the two points to be selected, and then choose one of the two points to be selected, and then continue to judge

3. Two cases of an expression:

   • 
     $d\leq0,d=d+2x+3$
   • 
     $d>0,d=d+2(x-y)+5$

4. Construct expression recursively, loop save point coordinates, draw last time

2.2 the ellipse

For the ellipse, only the first quadrant of the ellipse is drawn, and then the whole ellipse is drawn according to its symmetry

The approximate steps of the algorithm are as follows:

1. First, the standard equation of the ellipse with the center at the center of the circle is reduced to an implicit form: F(x,y)=b2x2+a2y2−a2b2F(x,y)= B ^2x^2+a^2y^2-a^2b^2F(x,y)= B2x2 + A2y2 − A2B2

2. Then the point where the normal vector of X direction is equal to the normal vector of Y direction is found as the dividing point, which can be divided into the upper part and the lower part of the elliptic arc

3. Construct different initial discriminant expressions for the upper part and the lower part respectively

   • 
     $D = b ^ 2 – a ^ 2 + 0.25 a ^ 2$
   • 
     $D = b ^ 2 + 0.5) (x ^ 2 + a ^ 2 (y – 1) ^ 2 – a ^ 2 b ^ 2$

4. Construct expression recursively, loop save point coordinates, draw last time

3 process

3.1 round

First, an initial value is assigned to the judgment expression, that is, d= 1.25-r;

Recirculate the judgment and save the point coordinates

while x<=(2^0.5/2)*R
    if d<0
        d=d+2*(x(end)) +3;
        x(end+1)=x(end) +1;
        y(end+1)=y(end);
    else
        d=d+2*(x(end)-y(end)) +5;
        x(end+1)=x(end) +1;
        y(end+1)=y(end)- 1;
    end
end
Copy the code

If the coordinate matrix needs to be derived, point coordinates can also be saved in sections. The last drawing is done.

3.2 the ellipse

Firstly, a judgment expression is constructed in the upper part of the first quadrant of the elliptic arc, and values are assigned to x and Y coordinate matrices

d=b*b-a*a+0.25*a*a;
while(b*b*x(end)<a*a*y(end))
    if(d<=0)
        d=d+b*b*(2*x(end) +3);
        x(end+1)=x(end) +1;
        y(end+1)=y(end);
    else
        d=d+b*b*(2*x(end) +3) +2*a*a*(1-y(end));
        x(end+1)=x(end) +1;
        y(end+1)=y(end)- 1;
    end
end
Copy the code

Similarly, in the lower part, the corresponding expressions are constructed as follows:

d=b*b*(x(end) +0.5)*(x(end) +0.5)+a*a*(y(end)- 1)*(y(end)- 1)-a*a*b*b;
Copy the code

To convert to the case where the center point is at any position, shift the origin and pass the shift parameter as an entry parameter to the function when called

Shift the origin of coordinates
x=x+m;
y=y+n;
Copy the code

If you need to export the coordinate matrix, you can also save point coordinates in sections

% Stores the coordinates of points on the ellipse
xx=[x,fliplr(x),2*m-x,fliplr(2*m-x)];
yy=[y,fliplr(2*n-y),2*n-y,fliplr(y)];
Copy the code

Finally, only one drawing is required to complete

plot(xx,yy,'y-');
Copy the code

4 the result

Draw a circle and an ellipse at the same time and overlay them as follows:

See Bresenham_circle(gitee.com) for the full code