原理分析与算法描述

• 待绘制的圆弧

  圆心在原点，半径为R的第一象限上的一段圆弧。且取（0，R）为起点，按顺时针方向绘制该1/8圆弧。

• 决策方程
  $$F(x,y)=x^2+y^2-R^2$$
  对于圆上的点，有F(x,y)=0；

  对于圆外的点，F(x,y)>0；

  对于圆内的点，F(x,y)<0。

M的坐标为：$M(x_i+1,y_i-0.5)$

•当$F(x_M,y_M)<0$时，取$P_u(x_i+1,y_i)$

•当$F(x_M,y_M)>0$时，取$P_d(x_i+1,y_i-1)$

•当$F(x_M,y_M)=0$时，约定取$P_u$。

• 构造判别式
  $$d_i=F(x_M,y_M)=F(x_i+1,y_i-0.5)=(x_i+1{)}^2+(y_i-0.5{)}^2-R^2$$
  •当$d_i\le 0$时，下一点取$P_u(x_i+1,y_i)$；

  •当$d_i>0$时，下一点取$P_d(x_i+1,y_i-1)$。

• 误差项的递推

  $d_i<=0,d_{i+1}=F(x_i+2,y_i-0.5)=d_i+2x_i+3$;

  $d_i>0,d_{i+1}=F(x_i+2,y_i-1.5)=d_i+2(x_i-y_i)+5$;

  $d_0=F(1,R-0.5)=1.25-R$

• 算法步骤

  1.输入圆的半径R。

  2.计算初始值d=1.25-R、x=0、y=R。

  3.绘制点(x,y)及其在八分圆中的另外七个对称点。

  4.判断d的符号。若d≤0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。

  5.当x<=y时，重复步骤3和4。否则结束。

代码实现

std::vector<Point> DrawCircle(Point center, float radius)
{
	std::vector<Point> points;
    int x = 0, y = radius;
    int d = 1.25 - radius;//决策变量初始值
    int xc = center.x, yc = center.y;
    while (y >= x) {//八对称点
        points.push_back({ xc + x, yc + y });
        points.push_back({ xc + x, yc - y });
        points.push_back({ xc - x, yc + y });
        points.push_back({ xc - x, yc - y });
        points.push_back({ xc + y, yc + x });
        points.push_back({ xc + y, yc - x });
        points.push_back({ xc - y, yc + x });
        points.push_back({ xc - y, yc - x });
        if (d <= 0) {//更新决策变量和坐标
            d = d + 2 * x + 3;
            x += 1;
        }
        else {
            d = d + 2 * (x - y) + 5;
            x += 1, y -= 1;
        }
    }
	return points;
}

结果展示

算法优化

• 改进：用d-0.25代替d，减少浮点数运算