Bresenham画圆算法

使用 Bresenham 算法扫描转换圆的方式如下：从 90° 到 45° 生成点，将仅在 +x 和 -y 方向上移动，如图所示

对真实圆的最佳逼近将由光栅中与真实圆距离最小的像素描述。 我们希望从

90° 到 45°。 假设最后一个扫描转换的像素是 P₁，如图所示。 通过采取以下两种操作之一，可以找到最接近真实圆的每个新点。

1. 在 x 方向上移动一个单位，或
2. 在 x 方向上移动一个单位，并在负 y 方向上移动一个单位。

设 D (S_i) 为从原点到真实圆的距离的平方减去到点 P₃ 的距离的平方。 D (T_i) 为从原点到真实圆的距离的平方减去到点 P₂ 的距离的平方。 因此，会出现以下表达式。

            D (S_i)=(x_i-1+1)²+ y_i-1² -r²
            D (T_i)=(x_i-1+1)²+(y_i-1 -1)²-r²

由于 D (S_i) 将始终为 +ve 且 D (T_i) 将始终为 -ve，因此可以如下定义一个决策变量 d

d_i=D (S_i )+ D (T_i)

因此，
d_i=(x_i-1+1)²+ y_i-1² -r²+(x_i-1+1)²+(y_i-1 -1)²-r²

从这个方程，我们可以驱动 d_i 的初始值如下

如果假设圆心位于原点，那么在第一步，x = 0 且 y = r。

因此，
            d_i=(0+1)²+r² -r²+(0+1)²+(r-1)²-r²
            =1+1+r²-2r+1-r²
            = 3 - 2r

此后，如果 d_i<0，则仅递增 x。

x_i+1=x_i+1         d_i+1=d_i+ 4x_i+6

& if d_i≥0,then x & y are incremented
x_i+1=x_i+1         y_i+1 =y_i+ 1
d_i+1=d_i+ 4 (x_i-y_i)+10

Bresenham画圆算法

步骤1： 开始算法

步骤 2： 声明 p、q、x、y、r、d 变量
        p、q 是圆心的坐标
        r 是圆的半径

步骤 3： 输入 r 的值

步骤 4： 计算 d = 3 - 2r

步骤 5： 初始化       x=0
          &nbsy= r

步骤 6： 检查是否扫描转换了整个圆
            如果 x > = y
            停止

步骤 7： 使用八向对称的概念绘制八个点。 中心位于 (p, q)。 当前活动像素为 (x, y)。
                putpixel (x+p, y+q)
                putpixel (y+p, x+q)
                putpixel (-y+p, x+q)
                putpixel (-x+p, y+q)
                putpixel (-x+p, -y+q)
                putpixel (-y+p, -x+q)
                putpixel (y+p, -x+q)
                putpixel (x+p, -y-q)

步骤 8： 找到要扫描的下一个像素的位置
            如果 d < 0
            then d = d + 4x + 6
            递增 x = x + 1
            如果 d ≥ 0
            then d = d + 4 (x - y) + 10
            递增 x = x + 1
            递减 y = y - 1

步骤 9： 转到步骤 6

步骤 10： 停止算法

示例： 使用 Bresenham 算法绘制 6 个圆点。 当圆的半径为 10 个单位时。 圆心是 (50, 50)。

解决方案： 令 r = 10（给定）

步骤 1： 取初始点 (0, 10)
                d = 3 - 2r
                d = 3 - 2 * 10 = -17
                d < 0 ∴ d = d + 4x + 6
                      = -17 + 4 (0) + 6
                      = -11

步骤 2： 绘制 (1, 10)
          d = d + 4x + 6 (∵ d < 0)
                = -11 + 4 (1) + 6
                = -1

步骤 3： 绘制 (2, 10)
           d = d + 4x + 6 (∵ d < 0)
                = -1 + 4 x 2 + 6
                = 13

步骤 4： 绘制 (3, 9) d 为 > 0，所以 x = x + 1, y = y - 1
                          d = d + 4 (x-y) + 10 (∵ d > 0)
                = 13 + 4 (3-9) + 10
                = 13 + 4 (-6) + 10
                = 23-24=-1

步骤 5： 绘制 (4, 9)
            d = -1 + 4x + 6
                = -1 + 4 (4) + 6
                = 21

步骤 6： 绘制 (5, 8)
            d = d + 4 (x-y) + 10 (∵ d > 0)
                = 21 + 4 (5-8) + 10
                = 21-12 + 10 = 19

所以 P₁ (0,0)⟹(50,50)
            P₂ (1,10)⟹(51,60)
            P₃ (2,10)⟹(52,60)
            P₄ (3,9)⟹(53,59)
            P₅ (4,9)⟹(54,59)
            P₆ (5,8)⟹(55,58)

使用 Bresenham 圆绘制算法绘制圆的程序

输出