圆生成算法

　　圆是图形中经常使用的元素，大部分图形学库中都提供画圆的api，本文介绍不使用任何图形库直接使用TypeScript语言实现在浏览器中画圆的方法。概述
　　html页面使用canvas元素进行绘制，TypeScript对canvas操作进行了简单的封装，这里主要用到设置单个像素点的颜色，代码如下
　　app.tsclass 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 = 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