By Sijmen J. Mulder, 3 August 2023.

- Question 1: rectangular copy
- Question 2: strcpy
- Question 3: flood fill check
*Question 4: circle drawing*(this page)

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 radiusr, 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:

- We’re not supposed to be using floating point math – it was 1994 after all.
- Using large steps for the angles yields an ugly circle with clearly visible corners (Figure 1).
- Now we have to implement line drawing too!

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(*x*^{2} + *y*^{2})
< *r*

The square root is an expensive floating point operation, but we can do without:

*x*^{2} + *y*^{2}
< *r*^{2}

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.)