光栅化圆生成算法——中点画圆算法的原理与实现

中点画圆法与中点画线法思想一致,我们这里只画$[\pi / 4, \pi / 2]$之间的圆弧,然后将其对称到八个方向即可画出整个圆。

若$P(x_p, y_p)$已确定,那么下一个元素只能是$P_1(x_p + 1, y_p)$或$P_2(x_p + 1, y_p - 1)$,同样可以构造函数:$F(x, y) = x^2 + y^2 - R^2$。设$M(x_p + 1, y_p - 0.5)$是$P_1$和$P_2$的中点,当$F(M) < 0$时,$M$在圆内,说明$P_1$离圆弧更近,则$P_1$为下一像素;否则$P_2$为下一像素。

同样判别式为$d = F(M) = F(x_p + 1, y_p - 0.5) = (x_p + 1)^2 + (y_p - 0.5)^2 - R^2$,若$d < 0$,则取$P_1$,$d_1 = F(x_p + 2, y_p - 0.5) = (x_p + 2)^2 + (y_p - 0.5)^2 - R^2 = d + 2x_p + 3$,增量为$2x_p + 3$;若$d \geq 0$,则取$P_2$,$d_2 = F(x_p + 2, y_p - 1.5) = (x_p + 2)^2 + (y_p - 1.5)^2 - R^2 = d + 2(x_p - y_p) + 5$,增量为$2(x_p - y_p) + 5$。然后$d$的初始值为$d_0 = F(1, R - 0.5) = 1.25 - R$。

同样可以使用$e = d - 0.25$代替$d$来避免浮点数运算,初值变为$e = 1 - R$,判别式$d < 0$变为$e < -0.25$,又所有的运算都是整数,则$e < -0.25$等价于$e < 0$,至此可以完全使用整数来实现中点画圆算法。

又观察到$d$的增量是$x, y$的线性函数,于是可以加入$x$和$y$的增量来规避乘法运算。

下面是一些简单的辅助函数,分别是画格点与像素点方块以及将一点对称到八个方向的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle, Circle
from matplotlib.lines import Line2D

def add_grid(size_x, size_y):
major_ticks = np.arange(0, size_x + 1, 5)
minor_ticks = np.arange(0, size_y + 1, 1)
ax.set_xticks(major_ticks)
ax.set_xticks(minor_ticks, minor=True)
ax.set_yticks(major_ticks)
ax.set_yticks(minor_ticks, minor=True)
ax.grid(which='minor', alpha=0.2)
ax.grid(which='major', alpha=0.5)

def pixel_plot(x, y, c):
rect = Rectangle((x, y), 1, 1, color=c)
ax.add_patch(rect)

def symmetry_plot(x0, y0, x, y, c):
pixel_plot(x0 + x, y0 + y, c)
pixel_plot(x0 - x, y0 + y, c)
pixel_plot(x0 + x, y0 - y, c)
pixel_plot(x0 - x, y0 - y, c)
pixel_plot(x0 + y, y0 + x, c)
pixel_plot(x0 - y, y0 + x, c)
pixel_plot(x0 + y, y0 - x, c)
pixel_plot(x0 - y, y0 - x, c)

下面是一个简短的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def mid_point_circle(x0, y0, r, c):
x, y = 0, r
dx, dy = 3, 2 - r - r
d = 1 - r
symmetry_plot(x0, y0, x, y, c)
while x < y:
if d < 0:
d += dx
dx += 2
x += 1
else:
d += dx + dy
dx += 2
dy += 2
x += 1
y -= 1
symmetry_plot(x0, y0, x, y, c)
1
2
3
4
fig, ax = plt.subplots(figsize=(10, 10))
add_grid(50, 50)
mid_point_circle(25, 25, 20, 'gray')
plt.show()

png

如果您觉得这篇文章对您有帮助,请随意打赏。