算法介绍

中点圆算法（Midpoint Circle Algorithm）是计算机图形学中的一个经典的算法，用于在离散的像素网格上画圆。
在离散的像素网格上绘制连续曲线时，核心挑战在于光栅化决策。Bresenham 思想为其提供了一套高效的解决方案：

  • 离散化逼近：利用像素中心坐标的整数特性。
  • 决策参数更新：通过判别式的符号指导下一步像素的选择
    • 根据对称性，只需要绘制 1/8 圆
    • 每次候选像素有两个，计算其中点位置，如果中点在圆内，使用外侧候选像素，否则使用内侧候选像素
  • 整数化规约：将复杂的平方、开方或三角函数运算转化为简单的整数加减法。

具体推导

默认圆以原点为圆心，并且只接受整数半径，圆的隐式方程如下

$$
f(x, y) = x^2 + y^2 - R^2
$$

若 $f(x, y) < 0$ 点在圆内，$> 0$ 点在圆外。

在第一象限的八分之一圆弧（$0 \le x \le y$）中，从像素点 $P_1(0,r)$ 开始，已知当前像素点 $P_i(x_i, y_i)$，每次沿着 $x$ 轴步进一格，下一个像素点只有两个候选：

  • $P_1(x_i+1, y_i)$ —— 正右方
  • $P_2(x_i+1, y_i-1)$ —— 右下方

评估中点 $M(x_i+1, y_i-0.5)$ 的位置

$$
d_i = f(x_i+1, y_i-0.5) = (x_i+1)^2 + (y_i-0.5)^2 - R^2
$$

然后进行决策：

  • 若 $d_i < 0$：中点在圆内，说明圆周曲线更接近 $P_1$，选取 $P_1$。
  • 若 $d_i \ge 0$：中点在圆外，说明圆周曲线更接近 $P_2$，选取 $P_2$。

为了避免昂贵的乘法和平方运算，在实际计算时，不需要每次计算 $d_i$，而是计算 $d_i$ 到 $d_{i+1}$ 的增量（都是整数，而且容易计算）用来更新。

因为增量都是整数，初始的中点 $(0, r-0.5)$ 对应的 $d = 1.25 - R$ 还可以进一步简化为 $d = 1 - R$。

完整代码

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
import matplotlib.pyplot as plt
import matplotlib.patches as patches


def get_midpoint_circle_pixels_unsimplified(radius: int):
    """
    Implementation of the Midpoint Circle Algorithm using the original
    mathematical derivation to enhance conceptual understanding.
    """
    x = 0
    y = radius

    # Initial Decision Parameter (Original Form: f(1, R - 0.5))
    # d = (x+1)^2 + (y-0.5)^2 - R^2
    # d = 1 + (R - 0.5)^2 - R^2 = 1.25 - R
    d = (x + 1) ** 2 + (y - 0.5) ** 2 - radius**2

    pixels = set()

    # Iterating through the first octant (0 <= x <= y)
    while x <= y:
        # Using 8-way symmetry to fill all octants
        pts = [(x, y), (y, x), (y, -x), (x, -y), (-x, -y), (-y, -x), (-y, x), (-x, y)]
        for p in pts:
            pixels.add(p)

        # Current candidate pixels:
        # P1 = (x + 1, y), P2 = (x + 1, y - 1)
        # Midpoint M = (x + 1, y - 0.5)
        d = (x + 1) ** 2 + (y - 0.5) ** 2 - radius**2

        if d < 0:
            # Case 1: Midpoint is inside the circle boundary.
            # The circle path is closer to P1 (x + 1, y).
            # y remains the same
            pass
        else:
            # Case 2: Midpoint is outside or on the circle boundary.
            # The circle path is closer to P2 (x + 1, y - 1).
            # y decreases by 1
            y = y - 1

        x = x + 1

    return list(pixels)


def get_midpoint_circle_pixels(radius: int):
    """
    Calculates the integer pixel coordinates for a circle using the
    Midpoint Circle Algorithm (Bresenham's variation).
    """
    x = 0
    y = radius
    d = 1 - radius

    pixels = set()

    while x <= y:
        # Using 8-way symmetry to fill all octants
        pts = [(x, y), (y, x), (y, -x), (x, -y), (-x, -y), (-y, -x), (-y, x), (-x, y)]
        for p in pts:
            pixels.add(p)

        if d < 0:
            d = d + 2 * x + 3
        else:
            d = d + 2 * (x - y) + 5
            y -= 1

        x += 1

    return list(pixels)


def visualize_pixel_grid(radius: int, setter):
    """
    Visualizes the circle on a rigorous grid where each pixel is a cell.
    The origin (0,0) is located at the center of the central grid cell.
    """
    pixels = setter(radius)

    fig, ax = plt.subplots(figsize=(6, 6))

    # Draw each pixel as a unit square centered at its integer coordinate
    # A pixel at (x, y) covers the area from [x-0.5, x+0.5] and [y-0.5, y+0.5]
    for px, py in pixels:
        square = patches.Rectangle(
            (px - 0.5, py - 0.5),
            1,
            1,
            linewidth=0.4,
            edgecolor="black",
            facecolor="royalblue",
            alpha=0.8,
        )
        ax.add_patch(square)

    # Draw the mathematical ideal circle for reference
    ideal_circle = patches.Circle(
        (0, 0),
        radius,
        color="crimson",
        fill=False,
        linewidth=2,
        linestyle="--",
        label="Ideal Circle",
    )
    ax.add_patch(ideal_circle)

    # Set axis limits to fit the circle with padding
    limit = radius + 2
    ax.set_xlim(-limit, limit)
    ax.set_ylim(-limit, limit)

    # Configure grid to align with pixel boundaries
    # Grid lines are at integer + 0.5 or integer - 0.5 positions
    grid_ticks = [i - 0.5 for i in range(-limit, limit + 2)]
    ax.set_xticks(grid_ticks, minor=True)
    ax.set_yticks(grid_ticks, minor=True)
    ax.grid(which="minor", color="gray", linestyle="-", linewidth=0.5)

    # Set integer labels at the center of each cell
    ax.set_xticks(range(-limit, limit + 1))
    ax.set_yticks(range(-limit, limit + 1))

    ax.set_aspect("equal")
    ax.set_title(f"Midpoint Circle Grid (R={radius})", fontsize=14)

    plt.show()


if __name__ == "__main__":
    # visualize_pixel_grid(5, setter=get_midpoint_circle_pixels_unsimplified)
    visualize_pixel_grid(5, setter=get_midpoint_circle_pixels)