By Sijmen J. Mulder, 3 August 2023.
Casey of Molly Rocket posted four interview questions asked for his 1994 Microsoft intership.
This page is about the final interview question: drawing a circle. I have to admit that this got me scratching my head a little bit at first!
Given a plot() function, which can be used to draw individual pixels, write a function that draws a circle around center point (cx,cy) with radius r, using only integer math:
void plot(int x, int y); /* provided */ void plot_circle(int cx, int cy, int r); /* implement */
My first thought was to step through angles 0 to 360 in small steps, then use sin(angle)*r and cos(angle)*r to calculate the positions on the circle, and finally draw lines between them. Lucky me for even remembering the cos/sin thing but there are problems:
So let’s try something else: start from (cx,cy-r). This is the top of the circle and easily calculated. Plot a point. We know the circle goes on to the right (for r pixels), so step right by one pixel. From the top going right the circle slopes down, so we might have to take one or more steps down to remain on the edge.
Just how many steps down we need to make to meet the edge again we can find with the observation that the edge of the circle is always exactly the radius r away from the middle – for a circle of radius 5, the center is 5 units away from every point on the edge. Hence, we need to step down until we are less than r pixels away from (cx,cy) (Figure 2).
We can use Pythagoras’ Theorem for the distance test:
sqrt(x2 + y2) < r
The square root is an expensive floating point operation, but we can do without:
x2 + y2 < r2
Now we can write the first version of the function that draws just a single quadrant:
void plot_circle(int cx, int cy, int r)
{
int x, y;
for (x=0, y=r; x < r; x++)
for (; y >= 0; y--) {
plot(cx+x, cy+y);
if (x*x + (y-1)*(y-1) < r*r)
break;
}
}The horizontal steps are bounded to r, the far right of the circle, and the vertical steps end when level with the center. Note that if the y axis points down in the coordinate system (as it often does in computer graphics), we’re actually starting at the bottom of the circle and drawing the bottom right quadrant.
Now we have a quarter of a circle (Figure 3).
Actually, we’re almost all the way there! There’s no need to repeat this loop four times, we can simply plot each point three more times at the inverted x and y to mirror the arc:
void plot_circle(int cx, int cy, int r)
{
int x, y;
for (x=0, y=r; x < r; x++)
for (; y >= 0; y--) {
plot(cx+x, cy+y);
plot(cx+x, cy-y);
plot(cx-x, cy+y);
plot(cx-x, cy-y);
if (x*x + (y-1)*(y-1) < r*r)
break;
}
}A final change we can make is with the observation that the path back from the right edge to the top is the same as from the top to the right edge, except with the coordinates flipped – e.g. if from the top you go right and down, the same steps can be made up and left from the right side of the circle. We can compute just 1/8th of a circle and mirror it 7 times (Figure 4):
void plot_circle(int cx, int cy, int r)
{
int x, y;
for (x=0, y=r; x < y; x++)
for (; y >= 0; y--) {
plot(cx+x, cy+y);
plot(cx+x, cy-y);
plot(cx-x, cy+y);
plot(cx-x, cy-y);
plot(cx+y, cy+x);
plot(cx+y, cy-x);
plot(cx-y, cy+x);
plot(cx-y, cy-x);
if (x*x + (y-1)*(y-1) < r*r)
break;
}
}Finally, here’s a “screenshot” of my beautiful makeshift terminal text plotter:
###################
##### #####
### ###
### ###
### ###
### ###
## ##
### ###
## ##
## ##
## ##
## ##
## ##
## ##
## ##
# #
## ##
## ##
# #
## ##
# #
## ##
# #
## ##
# #
## ##
# #
# #
# #
## ##
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
## ##
# #
# #
# #
## ##
# #
## ##
# #
## ##
# #
## ##
# #
## ##
## ##
# #
## ##
## ##
## ##
## ##
## ##
## ##
## ##
### ###
## ##
### ###
### ###
### ###
### ###
##### #####
###################
Aside: I had a fun time making the graphics on this
page. Initially I used Inkscape to make the SVGs, but when viewing this
page in dark mode the lines would barely be visible. By writing
<svg> code directly into the HTML I could use CSS to
adjust the colors in dark mode, like the rest of the site. Try it! (Use
your OS or browser setting.)