圆是什么？
只要接受过九年义务教育，就不会忘记圆的定义如下：
[ ( x^{2} - x_{c}^{2} ) + ( y^{2} - y_{2}^{2} ) = r^{2} ]
对定义进行变换，可求得 y 如下：
[ y = y_{c} \pm \sqrt{ r^{2} - ( x^{2} - x_{c}^{2} ) } ]
同样的，还有圆的极坐标方程组：
$$\left\{\begin{matrix}x = x_{c} + r\cos \theta \\y = y_{c} + r\sin \theta \end{matrix}\right.$$
但是我们在学习计算机的过程中发现，对一个数进行乘方和开方或是进行三角函数运算是一个较为缓慢的过程，对计算机的性能开销较大，而圆又是图形中无法绕开的问题。那么利用上述的公式计算坐标画圆，就不太合适。
中点圆算法
基于圆的八分对称型，只计算从起点(0,r)到八分之一圆弧终点的路径，再利用其对称性绘制圆整的圆。其方法是以单位间隔取样后，返回最接近圆周的两个像素的中点的像素。
对于给定半径为r，原点为$$ (x_{c},y_{c}) $$的圆。我们假设其圆心在坐标系的(0,0)上，那么最上方的点为(0,y)，我们将正在绘制的点记作$$(x_{0},y_{0})$$其中$$x_{0} = 0,y_{0} = r$$。其中点坐标为
[ (x_{0}, y_{mid}) ]
其中
[ y_{mid} = y_{0} - 0.5 ]
随后，我们向右移动一个像素，得到 $$x_{0} = 1,y_{0} = r$$。随后我们进行计算如下表达式：
[ p = \sqrt{ x_{0}^{2} + y_{0}^{2} } ]
我们发现，当 p>r 时，点在圆外，当 p=r 时，点在圆上，当 p<r时，点在圆内。那么我们当点在圆外时将 $$y_{0}$$ 向下移动一个，得到
[y_{0} = y_{0} - 1]
此时我们发现，圆在八分之一的弧上曲率恒处于 [0,-1] 内，也就是说，$$x_{0}$$每变化1，$$y_{0}$$最多变化1。因此上述公式内选择了直接减一。
不断迭代这个过程，直到 $$x_{0}==y_{0}$$ 我们便得到了一个八分之一圆弧，此时我们将其旋转复制七份，便得到了一个圆弧。
x0 = 200
y0 = 200
r = 10
x0 = 0
y0 = r
w = 1 - y0
while x0 < y0:
# 没超过八分之一圆
draw(x0+x1, y0+y1)
draw(y0+x1, x0+y1)
draw(x0+x1, -y0+y1)
draw(y0+x1, -x0+y1)
draw(-x0+x1, y0+y1)
draw(-y0+x1, x0+y1)
draw(-x0+x1, -y0+y1)
draw(-y0+x1, -x0+y1)
if x0**2 + y0**2 > r**2:
y0 = y0 - 1
x0 = x0 + 1
随后，我们发现连续的乘方运算对性能消耗过多，这在计算机图形绘制上简直是一个灾难，我们重新审视上面的过程，能否通过更简单的运算完成这个任务？
我们首先定义一个判断值 p，他的计算方式如下，代表是否在圆圈内
[ p = x^{2} + y^{2} - r^{2} ]
即当p>0时，点在圆外，p=0时，点在圆上，p<0时，点在圆内，此时我们可以用p来代替上述的乘方操作。
那么p的初始量就是
[ p = x^{2} + y_{mid}^{2} - r^{2} ]
将$$y_{mid}=y-0.5,x=0$$代入得
[ p = 0^{2} + (y-0.5)^{2} - r^{2} ]
消去0
[ p = (r-0.5)^{2} - r^{2} ]
因为$$y=r$$，所以
[ p = r^{2} - 2 \times r \times 0.5 + 0.5^{2} - r^{2} ]
展开得
[ p = 0.25 - r ]
我们这里可以选择两种方式，分别是忽略0.25和把0.25当成1计算，这里我们忽略0.25。那么得到
[ p = -r ]
但是只有一个值显然不足够，此时我们需要计算p的下一个值，记作 $$p_{next}$$
[ p_{next} = (x+1)^{2} + (y-0.5)^{2} - r^{2} ]
那么他们的差值就是
[ p_{step} = p_{next} - p ]
代入化简得
[ p_{step} = 2 \times x + 1 ]
省略其中的常数，得到
[ p_{step} = 2 \times x ]
我们在每一次的迭代中将 $$p_{step}$$ 增加到 p 中，直到p>0，此时点在圆外，我们将y下移一次。
此时我们需要更新p的值，我们重新计算
[ p = p + p_{step} ]
注意到y已经发生变化，我们修改y的值使$$y=y-1$$将式子中$$y-0.5$$替换为$$y-1.5$$，我们得到
[ p = (x)^{2} + (y-0.5)^{2} - r^{2} ]
[ p_{next} = (x+1)^{2} + (y-1.5)^{2} - r^{2} ]
[ p_{step} = p_{next} - p ]
[ p_{step} = (x+1)^{2} + (y-1.5)^{2} - r^{2} - (x)^{2} - (y-0.5)^{2} + r^{2} ]
[ p_{step} = (x+1)^{2} + (y-1.5)^{2} - (x)^{2} - (y-0.5)^{2} ]
显然
[ p_{step} = 2\times x-2\times y +3]
同样的，我们省略其中的常数，得到
[ p_{step} = 2\times x-2\times y]
重复直到x=y，即画完八分之一个圆弧。
这时我们就可以替换上面的代码为
x1 = 200
y1 = 200
r = 10
x0 = 0
y0 = r
w = 1 - y0
p = -r
while x0 < y0:
# 没超过八分之一圆
draw(x0+x1, y0+y1)
draw(y0+x1, x0+y1)
draw(x0+x1, -y0+y1)
draw(y0+x1, -x0+y1)
draw(-x0+x1, y0+y1)
draw(-y0+x1, x0+y1)
draw(-x0+x1, -y0+y1)
draw(-y0+x1, -x0+y1)
if p<0:
p += 2*x0
else:
p += 2*x0 - 2*y0
y0 = y0 - 1
x0 = x0 + 1
至此我们就得到了中点圆算法。
评论0
暂时没有评论