计算机图形学 - 圆生成算法
在屏幕上绘制圆圈比绘制直线稍微复杂一些。有两种流行的圆生成算法：**Bresenham 算法**和**中点圆算法**。这些算法基于确定绘制圆圈所需的后续点的思想。让我们详细讨论这些算法：
圆的方程为 $X^{2} + Y^{2} = r^{2}$，其中 r 是半径。
Bresenham 算法
我们无法在光栅显示器上显示连续的圆弧。相反，我们必须选择最接近的像素位置来完成圆弧。
从下图中，您可以看到我们已将像素置于 (X, Y) 位置，现在需要决定将下一个像素置于何处：N (X+1, Y) 还是 S (X+1, Y-1)。
这可以通过决策参数 **d** 来决定。
- 如果 d <= 0，则选择 N(X+1, Y) 作为下一个像素。
- 如果 d > 0，则选择 S(X+1, Y-1) 作为下一个像素。
算法
**步骤 1** - 获取圆心和半径的坐标，并分别存储在 x、y 和 R 中。设置 P=0 和 Q=R。
**步骤 2** - 设置决策参数 D = 3 – 2R。
**步骤 3** - 当 P ≤ Q 时，重复执行步骤 4 到步骤 8。
**步骤 4** - 调用 Draw Circle (X, Y, P, Q)。
**步骤 5** - 增加 P 的值。
**步骤 6** - 如果 D < 0，则 D = D + 4P + 6。
**步骤 7** - 否则，设置 R = R - 1，D = D + 4(P-Q) + 10。
**步骤 8** - 调用 Draw Circle (X, Y, P, Q)。
Draw Circle Method(X, Y, P, Q). Call Putpixel (X + P, Y + Q). Call Putpixel (X - P, Y + Q). Call Putpixel (X + P, Y - Q). Call Putpixel (X - P, Y - Q). Call Putpixel (X + Q, Y + P). Call Putpixel (X - Q, Y + P). Call Putpixel (X + Q, Y - P). Call Putpixel (X - Q, Y - P).
中点算法
**步骤 1** - 输入半径 **r** 和圆心 $(x_{c,} y_{c})$，并获得以原点为中心的圆周上的第一个点，如下所示：
(x0, y0) = (0, r)
**步骤 2** - 计算决策参数的初始值，如下所示：
$P_{0}$ = 5/4 – r（有关此方程式的简化，请参见以下说明。）
f(x, y) = x2 + y2 - r2 = 0
f(xi - 1/2 + e, yi + 1)
= (xi - 1/2 + e)2 + (yi + 1)2 - r2
= (xi- 1/2)2 + (yi + 1)2 - r2 + 2(xi - 1/2)e + e2
= f(xi - 1/2, yi + 1) + 2(xi - 1/2)e + e2 = 0
Let di = f(xi - 1/2, yi + 1) = -2(xi - 1/2)e - e2
Thus,
If e < 0 then di > 0 so choose point S = (xi - 1, yi + 1).
di+1 = f(xi - 1 - 1/2, yi + 1 + 1) = ((xi - 1/2) - 1)2 + ((yi + 1) + 1)2 - r2
= di - 2(xi - 1) + 2(yi + 1) + 1
= di + 2(yi + 1 - xi + 1) + 1
If e >= 0 then di <= 0 so choose point T = (xi, yi + 1)
di+1 = f(xi - 1/2, yi + 1 + 1)
= di + 2yi+1 + 1
The initial value of di is
d0 = f(r - 1/2, 0 + 1) = (r - 1/2)2 + 12 - r2
= 5/4 - r {1-r can be used if r is an integer}
When point S = (xi - 1, yi + 1) is chosen then
di+1 = di + -2xi+1 + 2yi+1 + 1
When point T = (xi, yi + 1) is chosen then
di+1 = di + 2yi+1 + 1
**步骤 3** - 从 K=0 开始，在每个 $X_{K}$ 位置执行以下测试：
If PK < 0 then next point on circle (0,0) is (XK+1,YK) and PK+1 = PK + 2XK+1 + 1 Else PK+1 = PK + 2XK+1 + 1 – 2YK+1 Where, 2XK+1 = 2XK+2 and 2YK+1 = 2YK-2.
**步骤 4** - 确定其他七个象限中的对称点。
**步骤 5** - 将每个计算出的像素位置 (X, Y) 移动到以 $(X_{C,} Y_{C})$ 为中心的圆形路径上，并绘制坐标值。
X = X + XC, Y = Y + YC
**步骤 6** - 重复步骤 3 到步骤 5，直到 X >= Y。