圆心位于像素间隙的圆栅格化算法问题求助

嘿，这个问题挺典型的，我来给你梳理一套高效的解决方案，既能准确筛选出符合要求的像素，又能保证每个像素只被访问一次！

1. 先简化几何模型，利用对称性省力气 #

首先我们可以把像素尺寸设为1（因为半径是像素的整数倍，缩放比例不影响几何关系），圆心固定在(0,0)——也就是四个像素的公共顶点位置。

利用圆的对称性是关键：我们只需要计算第一象限（包括x轴、y轴）的像素，再把结果对称复制到其他三个象限就行，这样能大幅减少计算量，还能保证每个像素只被处理一次。

2. 核心判断逻辑（针对第一象限像素） #

对于第一象限的像素(i,j)（i,j ≥ 0，对应正方形区域[i, i+1] × [j, j+1]），我们用距离平方来判断（避免开根号的精度误差）：
先定义几个关键值：

• 四个顶点到圆心的距离平方：
  d1 = i² + j²（左下角）、d2 = (i+1)² + j²（右下角）、d3 = i² + (j+1)²（左上角）、d4 = (i+1)² + (j+1)²（右上角）
• 圆半径的平方：R_sq = R × R（R是半径，整数）

然后分四种情况判断：

情况A：正方形完全被圆包含 #

如果最远的右上角顶点距离平方d4 < R_sq，说明整个正方形都在圆内，直接选中这个像素。

情况B：正方形部分在圆内、部分在圆外 #

只要有至少一个顶点在圆内（距离平方小于R_sq），同时有至少一个顶点在圆外（距离平方大于R_sq），那这个像素必然和圆有重叠区域，而且不可能仅交于顶点，直接选中。

情况C：圆与正方形的边相交（非顶点） #

如果四个顶点都在圆外，但圆和正方形的某条边有非顶点的交点：
分别检查四条边：

• 左边x=i：判断是否存在y ∈ (j, j+1)使得i² + y² = R_sq → 也就是j² < R_sq - i² < (j+1)²，且i² < R_sq（保证y有实数解）
• 右边x=i+1：同理，判断j² < R_sq - (i+1)² < (j+1)²且(i+1)² < R_sq
• 下边y=j：判断i² < R_sq - j² < (i+1)²且j² < R_sq
• 上边y=j+1：同理，判断i² < R_sq - (j+1)² < (i+1)²且(j+1)² < R_sq
  只要满足其中一条，说明圆和正方形边有非顶点交点，选中该像素。

情况D：仅交于顶点（必须排除） #

如果恰好只有一个顶点在圆上（距离平方等于R_sq），且其他三个顶点都在圆外，那这个正方形和圆仅交于该顶点，直接排除。

3. 对称扩展到所有象限 #

处理完第一象限的像素后，根据对称性生成其他象限的像素：

• 对于(i,j)（i>0,j>0），对称得到(-i,j)、(i,-j)、(-i,-j)
• 对于(i,0)（i>0），对称得到(-i,0)
• 对于(0,j)（j>0），对称得到(0,-j)
• 原点附近的(0,0)像素直接选中（圆心在它的顶点，半径≥1的话，这个正方形内有大量点在圆内）

4. 遍历优化，避免无用计算 #

不需要盲目遍历所有可能的像素：

• 第一象限中，i的范围是0到R（i>R时，正方形左边x=i>R，所有点距离都大于R，不可能和圆相交）
• 对于每个i，j的范围可以限制在0到floor(√(R_sq - i²)) + 1，覆盖所有可能与圆相交的区域

示例伪代码（Python风格） #

R = 5  # 半径，像素尺寸的整数倍
R_sq = R * R
selected_pixels = set()

# 处理第一象限（含坐标轴）
for i in range(0, R + 2):  # 多遍历一个单位，避免漏判边缘像素
    for j in range(0, R + 2):
        d1 = i*i + j*j
        d2 = (i+1)*(i+1) + j*j
        d3 = i*i + (j+1)*(j+1)
        d4 = (i+1)*(i+1) + (j+1)*(j+1)
        
        # 情况A：完全在圆内
        if d4 < R_sq:
            selected_pixels.add( (i,j) )
            continue
        
        # 情况B：部分在圆内
        has_inside = (d1 < R_sq) or (d2 < R_sq) or (d3 < R_sq) or (d4 < R_sq)
        has_outside = (d1 > R_sq) or (d2 > R_sq) or (d3 > R_sq) or (d4 > R_sq)
        if has_inside and has_outside:
            selected_pixels.add( (i,j) )
            continue
        
        # 情况C：边相交（非顶点）
        edge_intersect = False
        # 检查左边x=i
        if i*i < R_sq:
            y_sq = R_sq - i*i
            if j*j < y_sq < (j+1)*(j+1):
                edge_intersect = True
        # 检查右边x=i+1
        if (i+1)*(i+1) < R_sq:
            y_sq = R_sq - (i+1)*(i+1)
            if j*j < y_sq < (j+1)*(j+1):
                edge_intersect = True
        # 检查下边y=j
        if j*j < R_sq:
            x_sq = R_sq - j*j
            if i*i < x_sq < (i+1)*(i+1):
                edge_intersect = True
        # 检查上边y=j+1
        if (j+1)*(j+1) < R_sq:
            x_sq = R_sq - (j+1)*(j+1)
            if i*i < x_sq < (i+1)*(i+1):
                edge_intersect = True
        if edge_intersect:
            selected_pixels.add( (i,j) )
            continue
        
        # 情况D：仅交于顶点，不加入集合

# 对称扩展到其他象限
symmetric_pixels = set(selected_pixels)
for (i,j) in selected_pixels:
    if i > 0:
        symmetric_pixels.add( (-i, j) )
    if j > 0:
        symmetric_pixels.add( (i, -j) )
    if i > 0 and j > 0:
        symmetric_pixels.add( (-i, -j) )

# 输出结果
print("选中的像素坐标：", symmetric_pixels)

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