绘制实心圆的快速算法？

Question

我正在使用 Bresenham的圆形算法进行快速圆绘制。但是，我也希望（应用户的要求）画一个圆圈。

有这样快速有效的方法吗？与布雷森汉姆相同的东西？

我使用的语言是C.

Answer 1

阅读了关于Bresenham（也称为“中点”）圆圈算法的维基百科页面似乎最容易做的就是修改它的动作，而不是

setPixel(x0 + x, y0 + y);
setPixel(x0 - x, y0 + y);

和类似的，每次你改为

lineFrom(x0 - x, y0 + y, x0 + x, y0 + y);

也就是说，对于每一对点（具有相同的 y ），Bresenham会让你情节，而是连接一条线

Answer 2

只需使用蛮力。此方法迭代了太多像素，但它只使用整数乘法和加法。你完全避免了Bresenham的复杂性和sqrt的可能瓶颈。

for(int y=-radius; y<=radius; y++)
    for(int x=-radius; x<=radius; x++)
        if(x*x+y*y <= radius*radius)
            setpixel(origin.x+x, origin.y+y);

Answer 3

这是一个C＃粗略指南（不应该很难为C得到正确的想法） - 这是“原始”指南。没有使用Bresenham来消除重复的平根。

Bitmap bmp = new Bitmap(200, 200);

int r = 50; // radius
int ox = 100, oy = 100; // origin

for (int x = -r; x < r ; x++)
{
    int height = (int)Math.Sqrt(r * r - x * x);

    for (int y = -height; y < height; y++)
        bmp.SetPixel(x + ox, y + oy, Color.Red);
}

bmp.Save(@"c:\users\dearwicker\Desktop\circle.bmp");

Answer 4

您可以使用：

void DrawFilledCircle(int x0, int y0, int radius)
{
    int x = radius;
    int y = 0;
    int xChange = 1 - (radius << 1);
    int yChange = 0;
    int radiusError = 0;

    while (x >= y)
    {
        for (int i = x0 - x; i <= x0 + x; i++)
        {
            SetPixel(i, y0 + y);
            SetPixel(i, y0 - y);
        }
        for (int i = x0 - y; i <= x0 + y; i++)
        {
            SetPixel(i, y0 + x);
            SetPixel(i, y0 - x);
        }

        y++;
        radiusError += yChange;
        yChange += 2;
        if (((radiusError << 1) + xChange) > 0)
        {
            x--;
            radiusError += xChange;
            xChange += 2;
        }
    }
}

Answer 5

我喜欢palm3D的回答。对于蛮力，这是一个非常快速的解决方案。没有平方根或三角函数来减慢速度。它的一个弱点是嵌套循环。

将此转换为单个循环使此功能几乎快两倍。

int r2 = r * r;
int area = r2 << 2;
int rr = r << 1;

for (int i = 0; i < area; i++)
{
    int tx = (i % rr) - r;
    int ty = (i / rr) - r;

    if (tx * tx + ty * ty <= r2)
        SetPixel(x + tx, y + ty, c);
}

这种单循环解决方案可以与线条绘制解决方案的效率相媲美。

            int r2 = r * r;
            for (int cy = -r; cy <= r; cy++)
            {
                int cx = (int)(Math.Sqrt(r2 - cy * cy) + 0.5);
                int cyy = cy + y;

                lineDDA(x - cx, cyy, x + cx, cyy, c);
            }

Answer 6

以下是我的表现：
我使用两位精度的固定点值（我们必须管理半点和半点的平方值）
正如之前的回答中提到的，我也使用平方值而不是平方根 首先，我在圆圈的1/8部分检测到我的圆圈的边界限制。我正在使用这些点的对称来绘制4个“边界”。圈子。然后我在圆圈内画出正方形。

与中点圆算法不同，这个算法可以使用均匀直径（也可以使用实数直径，只需稍微改动）。

请原谅我，如果我的解释不清楚，我是法国人;）

void DrawFilledCircle(int circleDiameter, int circlePosX, int circlePosY)
{
    const int FULL = (1 << 2);
    const int HALF = (FULL >> 1);

    int size = (circleDiameter << 2);// fixed point value for size
    int ray = (size >> 1);
    int dY2;
    int ray2 = ray * ray;
    int posmin,posmax;
    int Y,X;
    int x = ((circleDiameter&1)==1) ? ray : ray - HALF;
    int y = HALF;
    circlePosX -= (circleDiameter>>1);
    circlePosY -= (circleDiameter>>1);

    for (;; y+=FULL)
    {
        dY2 = (ray - y) * (ray - y);

        for (;; x-=FULL)
        {
            if (dY2 + (ray - x) * (ray - x) <= ray2) continue;

            if (x < y)
            {
                Y = (y >> 2);
                posmin = Y;
                posmax = circleDiameter - Y;

                // Draw inside square and leave
                while (Y < posmax)
                {
                    for (X = posmin; X < posmax; X++)
                        setPixel(circlePosX+X, circlePosY+Y);
                    Y++;
                }
                // Just for a better understanding, the while loop does the same thing as:
                // DrawSquare(circlePosX+Y, circlePosY+Y, circleDiameter - 2*Y);
                return;
            }

            // Draw the 4 borders
            X = (x >> 2) + 1;
            Y = y >> 2;
            posmax = circleDiameter - X;
            int mirrorY = circleDiameter - Y - 1;

            while (X < posmax)
            {
                setPixel(circlePosX+X, circlePosY+Y);
                setPixel(circlePosX+X, circlePosY+mirrorY);
                setPixel(circlePosX+Y, circlePosY+X);
                setPixel(circlePosX+mirrorY, circlePosY+X);
                X++;
            }
            // Just for a better understanding, the while loop does the same thing as:
            // int lineSize = circleDiameter - X*2;
            // Upper border:
            // DrawHorizontalLine(circlePosX+X, circlePosY+Y, lineSize);
            // Lower border:
            // DrawHorizontalLine(circlePosX+X, circlePosY+mirrorY, lineSize);
            // Left border:
            // DrawVerticalLine(circlePosX+Y, circlePosY+X, lineSize);
            // Right border:
            // DrawVerticalLine(circlePosX+mirrorY, circlePosY+X, lineSize);

            break;
        }
    }
}

void DrawSquare(int x, int y, int size)
{
    for( int i=0 ; i<size ; i++ )
        DrawHorizontalLine(x, y+i, size);
}

void DrawHorizontalLine(int x, int y, int width)
{
    for(int i=0 ; i<width ; i++ )
        SetPixel(x+i, y);
}

void DrawVerticalLine(int x, int y, int height)
{
    for(int i=0 ; i<height ; i++ )
        SetPixel(x, y+i);
}

要使用非整数直径，可以提高定点精度或使用双精度值。 根据dY2 +（ray-x）*（ray-x）和ray2（dx＆＃178; + dy＆＃178;和r＆＃178;）之间的差异，甚至可以制作一种反别名/ p>

Answer 7

如果你想要一个快速算法，考虑绘制一个N边的多边形，N越高，圆就越精确。

Answer 8

我发现palm3D的强力算法是一个很好的起点。此方法使用相同的前提，但它包括几种跳过检查大多数像素的方法。

首先，这是代码：

int largestX = circle.radius;
for (int y = 0; y <= radius; ++y) {
    for (int x = largestX; x >= 0; --x) {
        if ((x * x) + (y * y) <= (circle.radius * circle.radius)) {
            drawLine(circle.center.x - x, circle.center.x + x, circle.center.y + y);
            drawLine(circle.center.x - x, circle.center.x + x, circle.center.y - y);
            largestX = x;
            break; // go to next y coordinate
        }
    }
}

接下来，解释。

首先要注意的是，如果找到给定水平线的圆内最小x坐标，则立即知道最大x坐标。 这是由于圆的对称性。如果最小x坐标位于圆的边界框左边10个像素处，则最大x为圆的边界框右侧后10个像素。

从高x值迭代到低x值的原因是，将以较少的迭代找到最小x值。这是因为由于圆圈向外弯曲，最小x值比大多数线条的圆心的中心x坐标更接近边界框的左边，如此图片 接下来需要注意的是，由于圆圈也是垂直对称的，所以你找到的每一条线都会给你一条自由的第二条线，每当你在圆圈的上半部分找到一条线时，你会在下半部分得到一条线。 radius-y y坐标。因此，当找到任何一行时，可以绘制两行，只需要迭代y值的上半部分。

最后要注意的是，如果你从位于圆心中的y值开始然后向y移动到顶部，那么每个下一行的最小x值必须更接近中心圆的x坐标比最后一行。这也是由于当你向上移动圆圈时，圆圈更接近中心x值。 以下是关于这种情况的视觉效果。

总结：

1. 如果找到一条线的最小x坐标，则可以免费获得最大x坐标。
2. 您在圆圈的上半部分找到的每条线都会在圆圈的下半部分免费提供一条线。
3. 从中心y坐标到顶部迭代时，每个最小x坐标必须比每行的前一个x坐标更接近圆心。

您还可以存储（radius * radius）的值，还可以存储（y * y）而不是计算它们  多次。

Answer 9

我只会生成一个点列表，然后使用多边形绘制函数进行渲染。