基于Bresenham圆绘制算法的无间隙坐标覆盖技术问询

你的问题核心在于标准Bresenham算法仅绘制圆的轮廓点，而非填充圆内部的所有整数坐标点。比如(2,2)这个点，到原点的距离平方为8，属于半径3的圆内部（3²=9≥8），但原代码只画了各半径的圆周长，未包含内部点，因此遗漏了这类坐标。

要实现无间隙覆盖，我们需要为每个半径r生成所有到原点距离≤r的整数坐标点，而非仅绘制周长。以下提供两种可行实现方式：

方法1：直接计算法（简单直观） #

遍历所有可能的x坐标，对每个x计算满足x²+y²≤r²的最大y值，再将该x对应的所有y值（从-y_max到y_max）加入点集：

import matplotlib.pyplot as plt

def filled_circle(x0, y0, radius):
    points = []
    r_sq = radius ** 2
    for x in range(-radius, radius + 1):
        x_sq = x ** 2
        # 计算当前x对应的最大y值
        y_max = int((r_sq - x_sq) ** 0.5)
        for y in range(-y_max, y_max + 1):
            points.append((x0 + x, y0 + y))
    # 去重避免重复添加对称点
    return list(set(points))

coords_included_in_circles = []
for r in range(1, 5):
    coords_included_in_circles += filled_circle(0, 0, r)

# 可视化验证
plt.scatter([x for x, y in coords_included_in_circles], [y for x, y in coords_included_in_circles])
plt.axis('equal')
plt.show()

方法2：扫描线填充法（效率更高） #

结合Bresenham的对称性思路，但填充每条扫描线的所有点，减少重复计算：

import matplotlib.pyplot as plt

def scanline_filled_circle(x0, y0, radius):
    points = []
    x = radius
    y = 0
    err = 0

    while x >= y:
        # 填充当前y对应的上下两条水平线（从-x到x）
        for xi in range(-x, x + 1):
            points.append((x0 + xi, y0 + y))
            if y != 0:
                points.append((x0 + xi, y0 - y))
        # 填充当前x对应的左右两条垂直线（从-y到y）
        for yi in range(-y, y + 1):
            points.append((x0 + x, y0 + yi))
            if x != 0:
                points.append((x0 - x, y0 + yi))
        
        y += 1
        err += 1 + 2 * y
        if 2 * (err - x) + 1 > 0:
            x -= 1
            err += 1 - 2 * x

    return list(set(points))

coords_included_in_circles = []
for r in range(1, 5):
    coords_included_in_circles += scanline_filled_circle(0, 0, r)

plt.scatter([x for x, y in coords_included_in_circles], [y for x, y in coords_included_in_circles])
plt.axis('equal')
plt.show()

验证结果 #

运行任意一种方法的代码后，(2,2)会被包含在半径3的填充圆中，所有到原点距离≤4的整数坐标点都会被覆盖，无间隙问题。

内容的提问来源于stack exchange，提问作者Joris