c - Bresenham 的圆算法

Question

我有以下绘制圆的代码:

#include<stdio.h>
#include<conio.h>
#include<graphics.h>
#include<math.h>

void main()
{
    int xc, yc, x, y, p[100], r, k;
    int gdriver=DETECT, gmode, errorcode;
    printf("\nEnter the center point(xc,yc): ");
    scanf("%d%d", &xc, &yc);
    printf("\nEnter the radius: ");
    scanf("%d", &r);
    printf("\nPlotting...\n");
    sleep(5);
    clrscr();

    initgraph(&gdriver, &gmode, "");
    p[0]=1-r;
    x=0;
    y=r;
    for(k=0;k<=y;k++)
    {
        putpixel(xc+x, yc+y, 9);
        putpixel(xc-x, yc-y, 9);
        putpixel(xc+x, yc-y, 9);
        putpixel(xc-x, yc+y, 9);
        putpixel(xc+y, yc+x, 9);
        putpixel(xc-y, yc-x, 9);
        putpixel(xc+y, yc-x, 9);
        putpixel(xc-y, yc+x, 9);

        if(p[k]>0)
        {
            p[k+1]= p[k]+ 2*(x+1)+1-2*(y+1);
            x++;
            y--;
        }
        else
        {
            p[k+1]=p[k]+2*(x+1)+1;
            x++;
        }
    }
        getch();
}

这部分代码:

putpixel(xc+x, yc+y, 9);
            putpixel(xc-x, yc-y, 9);
            putpixel(xc+x, yc-y, 9);
            putpixel(xc-x, yc+y, 9);
            putpixel(xc+y, yc+x, 9);
            putpixel(xc-y, yc-x, 9);
            putpixel(xc+y, yc-x, 9);
            putpixel(xc-y, yc+x, 9);

主要是绘制点相对于圆的点，它的作用是因为圆的对称性。

但是我无法弄清楚这部分代码到底在做什么；

if(p[k]>0)
        {
            p[k+1]= p[k]+ 2*(x+1)+1-2*(y+1);
            x++;
            y--;
        }
        else
        {
            p[k+1]=p[k]+2*(x+1)+1;
            x++;
        }

谁能解释一下它的作用？提前致谢。

Answer 1

更新公式看起来有点奇怪，下面给出我认为正确的步骤:

您从圆圈的最高点开始顺时针旋转直到角度达到 45 度。

现在，圆上的点大致满足(x^2 + y^2 = r^2)。

想法是一次绘制一个像素，向正方向移动 x方向。如果你发现下一个点(没有向下移动)离圆心太远，那么那个点应该被画得低一个单位。例如，如果您查看像素化的圆圈，您会发现它们基本上可以分解为一系列水平线和像素。水平线的每一端都标记了一个点，在该点上延伸线会离圆圈太远，因此您会看到一个下降点。

请注意，您可以自行决定选择哪些点。有 3 个圆形绘图学科:

1. 内圆:选择圆外没有点的点(这样 x^2 + y^2 < (r+1)^2 for each point r -- 注意这里是 r+1 而不是 r )
2. 外圆:选择圆内不画点的点(这样 x^2 + y^2 > (r-1)^2 for each point r -- 注意这里是 r-1 而不是 r )
3. 中圈:选择最小化 abs(x^2 + y^2 - r^2) 的点.

您可以在算法中选择任何这些学科。除了那个代码块(并且那里的变化很小)之外，这些方法是相同的。

在每种情况下，您都必须计算每个点偏离圆的距离。这需要知道 x^2 + (y-1)^2 - r^2 .我们称该序列为p[k] .如果x^2 + (y-1)^2 - r^2 <= 0 , 然后向下移动会显示太靠近圆心的点，所以下一个点应该是 (x+1, y) .在那种情况下，那么下一个偏差将是:

p[k+1] = (x+1)^2 + (y-1)^2 - r^2 = x^2 + (y-1)^2 - r^2 + 2x + 1 = p[k] + 2*(x + 1) - 1

如果x^2 + y^2 - r^2 > 0 , 那么下一点应该是 (x+1,y-1) , 所以

p[k+1] = (x+1)^2 + (y-2)^2 - r^2 = x^2 + (y-1)^2 - r^2 + 2x + 1 - 2y + 3 = q[k] + 2*(x + 1) - 2*(y - 1) = p[k] + 2*(x+1) - 2 * (y + 1)

这些公式根据您是否有兴趣寻找外圆(像素永远不会太近)、内圆(像素永远不会太远)或中心圆(大致成一直线)而变化，但这是基本思想.