圆形光栅化算法 - 像素之间的中心

Question

我有一个问题，我必须 select 部分在圆圈内的所有正方形（想想像素）（即使圆圈只穿过正方形的一个小角，但如果它穿过则不会通过角顶点之一）。半径是像素大小的整数倍。
问题是圆心在像素之间，即在四个像素的角顶点上。
我只想访问每个像素一次。

例如，我想 select 以下图像中的所有白色像素：

R = 8 像素

R = 10 像素

对于圆心在像素中心的圆，这不是问题，我可以使用 Bresenham 算法的常用形式：

public void checkCircle(int x0, int y0, int radius) {
    int x = radius;
    int y = 0;
    int err = -x;

    while (x > 0) {
        while (err <= 0) {
            y++;
            err += 2 * y + 1;
        }
        checkVLine(x0 + x, y0 - y, y0 + y);
        checkVLine(x0 - x, y0 - y, y0 + y);
        x--;
        err -= 2 * x + 1;
    }
    checkVLine(x0, y0 - radius, y0 + radius);
}

public void checkVLine(int x, int y0, int y1) {
    assert(y0 <= y1);
    for (int y = y0; y <= y1; y++)
        checkPixel(x, y);
}

遗憾的是，我不知道如何调整它以支持像素间圆圈。

Answer 1

对于第一象限 - 如果单元格的左下角位于圆圈内，则单元格应被标记，这样您就可以使用简单的循环进行栅格化

for dy = 0 to R-1
     dx = 0
     sq = R * R - dy * dy 
     while dx * dx  < sq
        mark (dx, dy)  
        mark (dx, -dy-1)  
        mark (-dx-1, dy)  
        mark (-dx-1, -dy-1)

要填充整条水平线，您可以计算 dx 的最大值

for dy = 0 to R-1
     mdx = Floor(Sqrt(R * R - dy * dy))
     fill line (-mdx-1,dy)-(mdx,dy)
     fill line (-mdx-1,-dy-1)-(mdx,-dy-1)

圆形光栅化算法 - 像素之间的中心

Circle Rasterization Algorithm - center between pixels

graphics

geometry

rasterizing

bresenham