圆是图形中经常使用的元素，大部分图形学库中都提供画圆的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画线算法及实践》介绍了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