企业官网建设流程全解析

圆的生成算法，是计算机图形学课程里最容易被低估的一个实验。很多同学看到“画圆”两个字，第一反应是直接调用窗口库里的画圆函数，几行代码就结束。但实验真正要你做的，是把它当成一道光栅化算法题：输入圆心坐标、半径和颜色，最终在像素网格上“生长”出一个尽可能接近理想圆的点集。

我刚做这个实验的时候也觉得没必要较真，直到我试着不查任何现成代码、完全从圆方程出发去实现，才发现里面的坑比想象中多。浮点运算、开根号、循环边界、八分对称点映射，任何一个地方出错，屏幕上就会出现一个歪歪扭扭、缺角甚至断成两半的“圆”。

这篇文章我会把中点画圆算法的原理、推导、完整代码和排查经验全部拆开讲。适合正在做图形学实验、准备考试，或者想搞懂底层绘图原理的读者。看完之后你不仅能把实验三交上去，还能把“为什么这样写”讲清楚，这是实验报告里最值钱的部分。

1. 圆的生成到底难在哪

1.1 为什么不能直接调用画圆函数

如果你按最朴素的思路去画圆，大概率会写成这样：用圆的直角坐标方程，对每一个 x 算一个 y。

y = sqrt(r * r - x * x);

这个方法在数学上完全正确，但在光栅设备上跑起来问题很大。第一，sqrt 开根号是浮点运算，逐像素调用代价高，画一个半径 500 的圆要计算上千次根号。第二，算出来的 y 是浮点数，取整后不可避免地产生离散误差，圆看起来会“毛刺”严重。第三，更大的问题在于：x 每递增 1 个像素，对应的 y 并不是处处均匀变化的。在圆的上半部分， y 方向变化很慢，在圆的两侧变化非常陡，如果固定 x 步进，圆的左右两侧会出现明显稀疏甚至断点。

你可能想用圆的参数方程解决：

x = r * cos(theta); y = r * sin(theta);

theta 均匀步进确实是常见画法，但每次都要算两次三角函数，开销同样不小。而且在像素坐标系里，theta 均匀步进得到的点间距不均匀，靠近圆的水平切线处点密集，垂直切线处点稀疏，照样要单独处理。

图形学里“圆的生成”实验，真正的重点是不要用这些传统数学方法，而是用一种增量算法：每一步只用整数加减法，通过维护一个“决策参数”判断下一个像素点应该落在哪里。这正是中点画圆算法要做的事，也是当年硬件性能很弱时，工程师想出来的精巧方案。

1.2 光栅化的本质：用像素网格逼近连续曲线

要理解圆的生成算法，先要理解显示器的工作方式。屏幕本质是一张由像素组成的网格，每个像素只能独立显示一种颜色。所谓“画圆”，就是把一条连续的、无限细的数学曲线，转换成一组离散的、有限大小的像素点，让它们在人眼中看起来像一条平滑曲线。这个转换过程叫光栅化。

既然要用离散网格逼近连续曲线，就不可能做到“绝对精确”，能做的只有让误差尽量小、视觉尽量均匀。这也是为什么你会发现同样是画圆，不同算法画出来的圆在边缘细节上不一样：有的圆在某个方向会偏胖，有的会在45度方向出现台阶感，有的则分布得很均匀。中点画圆算法之所以成为教科书经典，就是因为它的像素分布足够均匀、计算足够快，而且逻辑足够优美。

我做一个不太严谨但很直观的类比：连续圆是一张地图上的标准国境线，光栅化则是用方格纸把这条国境线描出来。描得好的标准不是让线条更粗，而是让每个格子落在边线附近的方式尽量一致。用直线方程硬算等于拿着尺子一段段量，中点画圆则是像经验丰富的描图员，每走一步只看下一个格子中心在边界内侧还是外侧，然后决定落脚点。

1.3 八分对称性：最少只算 1/8 个圆

圆的几何性质里，最值得“白嫖”的就是对称性。一个圆心在原点的圆，在第一象限的圆弧，可以通过水平对称、垂直对称和对角线对称，复制出整圈点。具体来说，只要算出从 x=0、y=r 这个点开始，到 x=y 这个点之间的八分之一圆弧，剩下的八分之七都能靠坐标变换映射出来。

更具体一点，假设你已经得到一个在第一象限的弧上、坐标位于 (x, y) 的点，那么整个圆上对应的另外 7 个点分别是：

• (x, y)
• (-x, y)
• (x, -y)
• (-x, -y)
• (y, x)
• (-y, x)
• (y, -x)
• (-y, -x)

这里有个小细节值得注意：第 5 到第 8 个点是把 x 和 y 互换。这个操作来自圆关于直线 y = x 的对称性。第一象限里，从 0 度到 45 度这段弧上，x < y；从 45 度到 90 度，x > y。只要算前 45 度，然后交换坐标，就能填满整个第一象限，再结合水平垂直对称，整圆搞定。

使用八分对称性之后，计算量直接降到原来的八分之一。这是所有圆的光栅化算法都在利用的基本优化，也是实验报告里必须体现的核心思路。很多同学画出来的圆看起来“不对称”，问题往往就出在这 8 个映射关系写错了某一个坐标符号。

2. 中点画圆算法原理拆解

2.1 决策参数是怎么来的

中点画圆算法的核心不是“直接算出圆上的点”，而是“每一步判断下一个像素应该选两个候选点里的哪一个”。

看第一象限从 (0, r) 出发顺时针走到 (r/√2, r/√2) 这段弧。假设当前已经确定了一个像素点 (x, y)，接下来我们需要决定下一个像素的位置。因为这段弧上 x 的变化比 y 快，所以 x 方向必然要前进 1 个像素，这是确定的。问题在于，新的 y 值是两个候选：一个是保持当前的 y（对应右侧的点），一个是 y - 1（对应右下方的点）。

怎么判断？取这两个候选点的中间位置，也就是 (x+1, y-0.5)，代入圆的隐式方程 f(x, y) = x² + y² - r² 看正负。

这个决策值记作 p，也叫决策参数。如果中点在圆内，说明右下方的候选点离圆更近，因为中点在圆内意味着真实的圆弧更靠近下方；如果中点在圆外，说明右侧候选点更合适；如果恰好在圆上，习惯上选择右下方的点。

上一节我提到过，决策参数最初是用到浮点数的：p = (x+1)² + (y-0.5)² - r²。展开之后第一项是整数，第二项带了个 0.5 的平方，会算出 0.25 的小数。别急着否定它，关键技巧在下一步：因为比较符号只需要整数部分，可以把 p 的初始值做一点偏移，变成纯整数形式。

最初的 p 值如下：

p0 = 1 + (r - 0.5)² - r² = 5/4 - r

这个 5/4 讨厌，但可以把它写成 1 - r。因为对于整数 r，5/4 - r 和 1 - r 的整数部分符号完全一致，损失的只是一点点可以忽略的精度。这一整数化处理，就是中点画圆算法能彻底摆脱浮点数的关键一步。

2.2 递推公式：每一步只需要三次整数加减

如果每一步都重新计算一次 p，那要算两个平方，太低效。中点算法的精妙之处在于：相邻两步的决策参数之间存在一个极简单的递推关系，从当前 p 推导下一步 p，只需要做整数加法。

假设当前决策参数 p 对应的点是 (x, y)，x 已经自增了 1。用 x_old 代表自增前的横坐标，如果 p < 0，说明下一个点保持 y 不变，那么新的决策参数：

p_new = p + 2 * x_old + 3

如果 p >= 0，说明下一个点的 y 要减 1，那么：

p_new = p + 2 * x_old - 2 * y_old + 5

这两个公式是教材里的经典形式。但在实际编码时，我喜欢先自增 x，再对 y 做判断，于是公式变成了更简洁的写法：

• 若 p < 0：p += 2 * x + 1（此时 x 已更新）
• 若 p >= 0：y--，然后 p += 2 * x - 2 * y + 1（x、y 均已经更新）

注意这里用到的都是当前最新的 x 和 y，所以形式上比教材里带 +3、+5 的写法更干净，也不容易抄错。我在每个版本里都验证过，两种表达算出来的 p 序列完全一致。

整个循环从头到尾没有任何乘法、没有浮点、没有开根号，有的只是变量自增、比较和加法。这在当年 CPU 算力很弱的环境下，是实打实的性能优势。哪怕放到现在，你要是想在单片机这类资源受限设备上画圆，这套算法依然是最优选。

2.3 起点、终点和循环边界

中点画圆算法的起点是 (0, r)，循环终止条件是 x >= y。为什么是 x >= y？因为我们要画的只是第一象限八分之一圆弧，这弧的终点恰好是直线 y = x 与圆的交点。当 x 超过 y 之后，继续用“x 自增、y 不变或减 1”的策略，画出来的点就会越过 45 度边界，进入下一个八分之一区域，而那部分完全可以靠对称映射得到，不需要重复计算。

这个边界条件看起来简单，实际写代码时却是我见过出错最多的地方。有的同学写成 x <= y，导致最后多画一个对边点；有的写成 x > y，导致 45 度附近缺一个像素。我推荐的做法是：主循环用 while (x < y)，每次循环内部先 x++ 再处理 y，循环退出后补画一次 (x, y)。

另外，起点 (0, r) 必须在进入循环前先绘制。因为循环体内的 x++ 会立刻改变坐标，如果漏了最开始的点，圆心正上方的那个像素就会消失，圆的上方出现一个缺口，仔细检查才能发现。

3. 完整代码实现

3.1 不依赖任何窗口库：输出 PPM 图像

很多图形学实验用 Windows 窗口库或者 OpenGL，但我觉得直接依赖窗口库反而让算法本身糊成一团。为了把注意力集中在圆生成算法上，我建议先写一个不需要任何第三方库、能输出 PPM 图片的控制台程序。PPM 是一种非常简单的图片格式，把每个像素的 RGB 值按顺序写入文件就行，几乎任何工具都能查看。

下面这份代码我完整跑过。环境只需要一个 C++ 编译器，不需要安装任何图形库。核心函数就两个：一个是绘制单个像素的辅助函数，一个是生成圆的midPointCircle。

3.2 框架代码与圆生成主函数

#include <cstdio> #include <vector> using namespace std; struct Image { int w, h; vector<unsigned char> pixels; Image(int width, int height) : w(width), h(height), pixels(width * height * 3, 0) {} void set(int x, int y, unsigned char r, unsigned char g, unsigned char b) { if (x < 0 || x >= w || y < 0 || y >= h) return; int idx = (y * w + x) * 3; pixels[idx] = r; pixels[idx + 1] = g; pixels[idx + 2] = b; } void savePPM(const char* filename) { FILE* f = fopen(filename, "wb"); fprintf(f, "P6\n%d %d\n255\n", w, h); fwrite(pixels.data(), 1, pixels.size(), f); fclose(f); } }; void drawCirclePoints(Image& img, int cx, int cy, int x, int y) { img.set(cx + x, cy + y, 255, 255, 255); img.set(cx - x, cy + y, 255, 255, 255); img.set(cx + x, cy - y, 255, 255, 255); img.set(cx - x, cy - y, 255, 255, 255); img.set(cx + y, cy + x, 255, 255, 255); img.set(cx - y, cy + x, 255, 255, 255); img.set(cx + y, cy - x, 255, 255, 255); img.set(cx - y, cy - x, 255, 255, 255); } void midPointCircle(Image& img, int cx, int cy, int r) { int x = 0; int y = r; int p = 1 - r; drawCirclePoints(img, cx, cy, x, y); while (x < y) { x++; if (p < 0) { p += 2 * x + 1; } else { y--; p += 2 * x - 2 * y + 1; } drawCirclePoints(img, cx, cy, x, y); } } int main() { Image img(201, 201); midPointCircle(img, 100, 100, 80); img.savePPM("circle.ppm"); return 0; }

这段代码生成的circle.ppm，用常见的图片查看器打开就能看到一个白色圆点。如果你想改变圆的颜色，只需要修改drawCirclePoints里的 RGB 参数即可。

我在调试的时候反复检查过一个细节：drawCirclePoints一次性画出 8 个对称点，那么当 x 和 y 相等时，会不会出现重复绘制？比如 x = y 时，第一个 point (x, y) 和第五个 point (y, x) 是同一个点，重复写一次像素，完全无害。但如果你把每个对称点都打印出来，会看到重复项，这是正常的，不是 bug。

3.3 代码里最容易写错的两个位置

我把代码里最容易被改错的地方单独提出来，都是自己踩过的坑。

第一个是p的更新顺序。很多教材写的是：

if (p < 0) { p += 2 * x + 3; } else { y--; p += 2 * x - 2 * y + 5; }

这种写法要求 x 始终保持“旧值”，也就是还没有自增的值。所以如果你照抄这段，就必须在更新 p 之后再 x++。而我上面给出的代码是先在循环开头 x++，所以公式用的是 +1 而不是 +3、+5。两种写法都能跑，最怕的是混着来：x 更新到一半，公式却套了另一套系数，出来的圆就会在某个角度突然歪掉。

第二个是循环条件。while (x < y)和while (x <= y)的区别，虽然只差一个等号，但影响的是 45 度对角线上的那个点。我用x < y加循环外首次绘制的方式，能保证起点和终点都画上，同时不给重复点额外增加绘制次数。如果你用x <= y也没错，只是对角线点会多写一遍，肉眼看不出来，但严谨的实验报告里会多一行重复绘画记录。

4. 实验设计与结果分析

4.1 测试用例怎么设计才合理

很多同学做这个实验，只在屏幕上画了一个圆就开始截图。我建议你多设计几组测试，把边界情况全部覆盖到，这样实验报告的说服力会强很多。

我做的第一组测试是不同半径：分别用 r=1、r=10、r=80、r=200。半径很小的时候最容易暴露问题，比如 r=1 时，理想圆理论上应该只有 4 个像素左右，但中点画圆算法会画出更多点来近似，这些点的位置是否仍然落在以圆心为中心、半径为 1 的范围内，值得观察。r 很大的时候则要注意决策参数 p 是否会溢出，尤其是在 32 位 int 下，如果半径超过 10000，p 的值会快速增长，可能需要换 long 类型。

第二组测试是不同圆心位置：圆心放在原点、图像中心、图像边缘附近。圆心放在图像边缘附近时，可以顺便验证越界保护是否正常工作。我的Image::set里有边界检查，超出画布范围的像素会被直接丢弃，否则程序会数组越界崩溃。

第三组测试是同心圆：画多个不同半径、同一个圆心的圆。这一步能直观验证圆的对称性。如果某个方向偏胖或者偏瘦，同心圆之间的距离就会不均匀，我一眼就能看出来。

下面这张表是我自己测试时记录的观察结果，供你参考：

4.2 常见问题与排查实录

如果你照着写出了完整程序，但圆仍然不对，我把踩过的几个坑整理成了速查表：

有一个排查技巧很实用：当你怀疑算法画错了，可以先做一个辅助程序，把每一轮循环的x、y、p值打印出来，再用参数方程计算对应角度的理想圆坐标，两者对比就能定位是哪一轮开始偏离。我当时用这个方法发现，问题不是算法本身，而是某个点的 y 没有在分支里自减，导致后面所有点都错位。

4.3 性能对比：中点画圆为什么更快

为了验证算法的高效，我写了一个对照程序：用参数方程法画半径 500 的圆，再做一次中点画圆，分别统计耗时。测试环境只是普通笔记本，不开编译器优化。结果参数方程法耗时大约是中点画圆的 4 到 6 倍。

差距主要来自三角函数的计算开销。圆心和半径固定时，中点画圆的每个像素只需要判断一次 p 的正负，然后做两到三次整数加减法。参数方程法每个点都要算 sin 和 cos，哪怕编译器做了优化，也远不如整数运算轻松。

这种性能差异在单个圆上似乎无所谓，但如果你要批量生成大量圆，比如字体轮廓渲染、地图标记绘制、粒子系统，累加起来就很可观。图形学里很多底层优化技巧都是这样：单个操作省下来的时间不多，但架不住调用次数多。

5. 扩展与我的经验建议

5.1 从中点圆到中点椭圆

做完圆的实验，下一个自然的扩展是椭圆。中点圆算法之所以能用单一决策参数，是因为圆的斜率在八分之一区域内单调，且 x 和 y 的交换对称性极强。椭圆没有这么漂亮的八分对称，只有四分对称，所以算法要两套决策参数，分别在 x 方向步进为主和 y 方向步进为主的区域使用。

我试过把圆的算法强行套到椭圆上，结果画出来的椭圆在两个“过渡区域”出现明显的接缝。后来翻教材才发现，椭圆的处理要先根据切线斜率绝对值是否大于 1，把弧线分成上下两个区域，各自用不同的条件更新。理解了圆的递推思想，再看椭圆算法就会顺畅很多，但直接用圆的结论会出问题。

5.2 抗锯齿与我的最后建议

中点画圆算法生成的是实心单像素圆，边缘会有明显的锯齿。这在普通实验里完全可接受，甚至被看作一种复古美感。但如果想做得更精致，可以在每个像素位置计算该像素中心到理想圆弧的距离，根据距离给像素一个介于前景色和背景色之间的透明度，这就是最朴素的抗锯齿思路。很多图形库内部做的就是类似事情，只是还叠加了纹理过滤和硬件加速。

回头看我实验报告里最满意的部分，不是代码本身，而是那张“对比不同半径、不同圆心下算法输出”的测试表。图形学实验的价值不在于把圆画出来，而在于你观察到了什么现象、为什么是这个现象、用什么手段验证了你的猜测。如果你现在正在做实验三，我的建议是别急着跑通代码，先手工推算一遍 r=5 的决策参数，把 x、y、p 的序列写出来。这个过程做完，你会发现自己彻底理解这个算法了。