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个画圆的规则：

内圆内圆:选择不会在圆外绘制任何点的点(因此，请注意，此处为r)

• Outer r)

• Middle abs(x^2 + y^2 - r^2).

：选择不在圆内绘制的点，而不是此处的r+1：选择最小化r)

• Middleabs(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)

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

Answer 2

您正在询问的程序部分是圆绘制算法的核心，它计算圆的一个八分线的x，y坐标(八个putpixel()调用将这个八分线镜像到其他七个，以完成圆)。in this article对该算法进行了详细的说明。