最初发布在sjmulder.nl。
iabaoqian1 的casey four interview questions要求他的1994年Microsoft互助。
此页面是关于最终采访问题：绘制一个圆圈。我必须承认这让我起初有点挠头！
给定的 plot（）函数，可用于绘制单个像素，编写一个函数，用半径为中心点（cx，cy）绘制一个圆的函数 r ，仅使用整数数学：
void plot(int x, int y); /* provided */ void plot_circle(int cx, int cy, int r); /* implement */
我的第一个想法是在小步骤中逐步跨越角度0到360，然后使用 sin（Angle）*r 和 cos（Angle）*r 计算位于圆上，最后在它们之间划清界限。幸运的是，我甚至想起了cos/sin的东西，但是有问题：
- 我们不应该使用浮点数学 - 毕竟是1994年。
- 使用大步骤的角度产生一个丑陋的圆圈，带有明显可见的角（图1）。
- 现在我们也必须实现线图！
图1：一个从16个离散角步中绘制的圆圈。不漂亮。
因此，让我们尝试一下：从（CX，CY-R）开始。这是圆的顶部，很容易计算。绘制一个点。我们知道圆的右侧（对于 r 像素），所以朝一个像素右走。从顶部向右行驶，圆向下倾斜，因此我们可能必须向下走一个或多个步骤才能保持在边缘。
正是我们需要进行多少步骤才能再次达到边缘，我们可以发现圆的边缘始终是半径 r 远离中间的圆在半径5中，中心距边缘的每个点5个单位。因此，我们需要下台，直到我们距离（CX，CY） r r r （图2）。
图2：拥抱边缘
我们可以使用Pythagoras' Theorem进行距离测试：
sqrt（ x ^2^ + y ^2^） r
平方根是一个昂贵的浮点操作，但是我们可以没有：
x ^2^ + y ^2^2^ r ^2^
现在我们可以编写仅绘制一个象限的函数的第一个版本：
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;
}
}
水平步骤与圆圈的最右边的 r 界定，垂直步骤在与中心水平时结束。请注意，如果 y 轴指向坐标系（与计算机图形中经常使用），我们实际上是从圆的底部开始，并绘制了右下象限。
现在我们有四分之一的圆（图3）。
图3：1/4，那里的路程
实际上，我们几乎一直到那里！无需四次重复此循环，我们可以简单地在倒置的 x 和 y 上绘制每个点三次即可镜像弧：
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;
}
}
我们可以做出的最终更改是，从右边缘到顶部的路径与从顶部到右边缘相同，除了坐标拨动了 - 例如如果从顶部向右和向下走，可以从圆的右侧向上和离开相同的步骤。我们只能计算一个圆的1/8，然后将其镜像7次（图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;
}
}
图4：打开复印机！
最后，这里是我美丽的临时终端文本绘图仪的“屏幕截图”：
旁边：我在本文的the original web version上做了一个愉快的时光。最初，我使用Inkscape制作SVG，但是在以暗模式查看此页面时，线条几乎看不到。通过将<svg>代码直接编写到HTML中，我可以使用CSS在黑暗模式下调整颜色，例如网站的其余部分。尝试一下！ （使用您的操作系统或浏览器设置。）
评论欢迎在Mastodon或以下。