中点画圆法与中点画线法思想一致,我们这里只画$[\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$的增量来规避乘法运算。

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

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)

下面是一个简短的实现:

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)
fig, ax = plt.subplots(figsize=(10, 10))
add_grid(50, 50)
mid_point_circle(25, 25, 20, 'gray')
plt.show()