圆周长最简单的算法（圆生成算法）
圆周长最简单的算法（圆生成算法）代码如下解决圆出现断点的问题可以使用极坐标法，可以根据角度计算圆上的坐标点，这样就可以利用沿圆周的等距点来绘制出圆了。x的坐标范围为[xc-r xc r]，可以遍历x，根据上面的公式求出y值（有两个值y1 y2），逐个设置像素坐标(x y1)、(x y2)的颜色值就可以绘制出圆了。代码参考如下// 续app.ts let start = Date.now(); webgl.glColor3f(1.0 0 0); let [xc yc r] = [110 110 100]; for (let x = yc - r; x < yc r; x ) { let tmp = Math.sqrt(r ** 2 - (x - xc) ** 2); let y1 = yc tmp; let y2 = yc - tmp; webgl.setPi
圆是图形中经常使用的元素，大部分图形学库中都提供画圆的api，本文介绍不使用任何图形库直接使用TypeScript语言实现在浏览器中画圆的方法。
概述html页面使用canvas元素进行绘制，TypeScript对canvas操作进行了简单的封装，这里主要用到设置单个像素点的颜色，代码如下
app.ts
class WebGL {
canvas: HTMLCanvasElement;
ctx: CanvasRenderingContext2D;
// 构造函数
constructor(canvas: HTMLCanvasElement) {
this.canvas = canvas;
this.ctx = canvas.getContext("2d");
this.vertices = []
}
// 设置颜色值
glColor3f(r: number g: number b: number) {
this.ctx.fillStyle = "rgba(" r*255 " " g*255 " " b*255 " " 1.0 ")";
}
// 填充1x1像素的矩形（即一个像素大小）来实现单个像素颜色设置
setPixel(x: number y: number) {
this.ctx.fillRect(x y 1 1);
}
// rgba指定的颜色清空整个canvas实现刷新canvas背景
glClearColor(r: number g: number b: number a:number) {
this.ctx.fillStyle = "rgba(" r*255 " " g*255 " " b*255 " " a ")";
this.ctx.fillRect(0 0 this.canvas.clientWidth this.canvas.clientHeight);
}
}
var canvas = <HTMLCanvasElement>document.getElementById("canvas001");
var webgl = new WebGL(canvas);
// 设置为黑色背景
webgl.glClearColor(0 0 0 1);
注：为了突出重点，这里没有列出完整代码，稍有基础完全可以参考自行实现。
勾股定理法画圆圆上的点到圆心的距离相等，已知圆心坐标(xc yc)和半径r，根据勾股定理可以得出
x的坐标范围为[xc-r xc r]，可以遍历x，根据上面的公式求出y值（有两个值y1 y2），逐个设置像素坐标(x y1)、(x y2)的颜色值就可以绘制出圆了。
代码参考如下
// 续app.ts
let start = Date.now();
webgl.glColor3f(1.0 0 0);
let [xc yc r] = [110 110 100];
for (let x = yc - r; x < yc r; x ) {
let tmp = Math.sqrt(r ** 2 - (x - xc) ** 2);
let y1 = yc tmp;
let y2 = yc - tmp;
webgl.setPixel(x y1);
webgl.setPixel(x y2);
}
let end = Date.now();
console.log("1-勾股定理法画圆耗时: " (end - start) "ms");
绘制效果见下图，可以明显看出在圆的左右两侧出现了明显的断点（由于斜率两侧较大，y值的变化较大），显然是不理想的，另外该方法中涉及平方、平方根运算，计算量相对是比较大的。
解决圆出现断点的问题可以使用极坐标法，可以根据角度计算圆上的坐标点，这样就可以利用沿圆周的等距点来绘制出圆了。
代码如下
// 续app.ts
start = Date.now();
webgl.glColor3f(1.0 0 0);
[xc yc r] = [400 110 100];
//把一个圆周分成360份，也就是用360个点来画圆
for (let i = 0; i < 360; i ) {
let x = xc r * Math.cos(i);
let y = yc r * Math.sin(i);
webgl.setPixel(x y);
}
end = Date.now();
console.log("2-极坐标法画圆耗时: " (end - start) "ms");
绘制效果见下图，可以看出还是有一些零散的断点，但分布是均匀的，可以通过把一个圆周分成更多的份数来解决这个问题，这个算法需要三角运算，同样存在运算量相对较大的问题。
之前的文章《Bresenham画线算法及实践》介绍了Bresenham中点算法进行线段的绘制，该算法还适合圆和其他曲线，关键是该算法以决策参数增量为依据，可以做到仅涉简单的整数处理，具有非常高的性能，下面介绍该算法实现的原理。
- 根据圆的对称性，可以把圆分成八份，只要计算其中一段圆弧坐标，根据对称性无需计算就可以得出其他7段圆弧的坐标，参见上图所示，先考虑圆心在坐标原点的圆，如果圆心不在原点的情况绘制时只需要增加圆心坐标xc、yc的距离就可以了；
- 以编号为1的那一段圆弧(x=0到x=y段)为例，假如已经确定了(xk yk)的坐标，那么针对xk 1，通过判断yk、yk-1的中点yk-1/2在圆内还是圆外来决定下一个像素坐标，如果中点在圆内则坐标(xk 1 yk)更接近圆曲线，如果中点在圆外则坐标(xk 1 yk-1)更接近圆曲线，根据圆的方程可以构造如下的圆函数，通过求函数值进行判定。
- 为进一步减少算法的计算量，我们定义一个决策参数pk，假如已经确定了像素(xk yk)，那么pk就是将中点(xk 1 yk-1/2)代入圆函数的值，pk<0则(xk 1 yk)更接近圆，否则(xk 1 yk-1)更接近圆。
- 后续的决策参数pk 1可以通过增量计算获得，pk 1的值因pk的正负而有不同的增量。
- 最后，需要确定pk的初始值p0，选取第一象限x=0到x=y分段的圆弧，首个像素坐标为(0 r)，则p0=f(0 1 r-1/2)。假如将半径r指定为整数，则将5/4直接简化为1并不会影响p0的正负性，则p0=1-r也是一个整数，那么后续的增量pk也将都是整数，整个Bresenham中点画圆算法就只需要进行整数处理，大大节省了计算量。
根据上面的思路实现的代码参考如下
// 续app.ts
// circlePlot为自定义WebGL类中的方法，实现了Bresenham画圆算法，(x_c y_c)为圆心坐标，r为半径
circlePlot(x_c: number y_c: number r: number) {
let [x0 y0] = [0 r];
let p = 1 - r;
let y = y0;
for (let x = x0; x < y; x ) {
if (p < 0) {
// 中点在园内
p = 2 * x 1;
} else {
// 中点在圆外或圆上
y -= 1;
p = 2 * (x - y) 1;
}
this.setPixel(x_c x y_c y);
// 利用对称性绘制其他圆弧
this.setPixel(x_c y y_c x);
this.setPixel(x_c y y_c - x);
this.setPixel(x_c x y_c - y);
this.setPixel(x_c - x y_c y);
this.setPixel(x_c - y y_c x);
this.setPixel(x_c - x y_c - y);
this.setPixel(x_c - y y_c - x);
}
}
// Bresenham算法绘制圆
start = Date.now();
webgl.glColor3f(1.0 0 0);
webgl.circlePlot(690 110 100);
end = Date.now();
console.log("3-Bresenham中点画圆耗时: " (end - start) "ms");
下图是将三种方法绘制在一起的三个圆的效果，最右边的为Bresenham算法绘制的圆，效果更好些，根据记录的时间来看其算法耗时也是最小的（勾股定理法、极坐标法也可以利用对称性仅计算1/8圆弧就可以了，画一个圆性能上比较估计并不明显，当大量进行绘制时才能体现出Bresenham算法的优势）。
[1]. 《计算机图形学》（第三版）Donald Hearn、M.PaulineBaker著，3.9 圆生成算法，P80
