实心圆的中点圆算法

Question

该中点画圆算法可以栅格圆的边界使用.但是,我想要填充圆圈,而不是多次绘制像素(这非常重要).

这个答案提供了算法的修改,产生一个实心圆,但有几个像素被访问了几次: 快速算法绘制实心圆？

问:如何在不多次绘制像素的情况下光栅化圆圈？请注意,RAM非常有限!

更新:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CircleTest
{
    class Program
    {
        static void Main(string[] args)
        {
            byte[,] buffer = new byte[50, 50];
            circle(buffer, 25, 25, 20);

            for (int y = 0; y < 50; ++y)
            {
                for (int x = 0; x < 50; ++x)
                    Console.Write(buffer[y, x].ToString());

                Console.WriteLine();
            }
        }

        // 'cx' and 'cy' denote the offset of the circle center from the origin.
        static void circle(byte[,] buffer, int cx, int cy, int radius)
        {
            int error = -radius;
            int x = radius;
            int y = 0;

            // The following while loop may altered to 'while (x > y)' for a
            // performance benefit, as long as a call to 'plot4points' follows
            // the body of the loop. This allows for the elimination of the
            // '(x != y)' test in 'plot8points', providing a further benefit.
            //
            // For the sake of clarity, this is not shown here.
            while (x >= y)
            {
                plot8points(buffer, cx, cy, x, y);

                error += y;
                ++y;
                error += y;

                // The following test may be implemented in assembly language in
                // most machines by testing the carry flag after adding 'y' to
                // the value of 'error' in the previous step, since 'error'
                // nominally has a negative value.
                if (error >= 0)
                {
                    error -= x;
                    --x;
                    error -= x;
                }
            }
        }

        static void plot8points(byte[,] buffer, int cx, int cy, int x, int y)
        {
            plot4points(buffer, cx, cy, x, y);
            if (x != y) plot4points(buffer, cx, cy, y, x);
        }

        // The '(x != 0 && y != 0)' test in the last line of this function
        // may be omitted for a performance benefit if the radius of the
        // circle is known to be non-zero.
        static void plot4points(byte[,] buffer, int cx, int cy, int x, int y)
        {
#if false // Outlined circle are indeed plotted correctly!
            setPixel(buffer, cx + x, cy + y);
            if (x != 0) setPixel(buffer, cx - x, cy + y);
            if (y != 0) setPixel(buffer, cx + x, cy - y);
            if (x != 0 && y != 0) setPixel(buffer, cx - x, cy - y);
#else // But the filled version plots some pixels multiple times...
            horizontalLine(buffer, cx - x, cy + y, cx + x);
            //if (x != 0) setPixel(buffer, cx - x, cy + y);
            //if (y != 0) setPixel(buffer, cx + x, cy - y);
            //if (x != 0 && y != 0) setPixel(buffer, cx - x, cy - y);
#endif
        }

        static void setPixel(byte[,] buffer, int x, int y)
        {
            buffer[y, x]++;
        }

        static void horizontalLine(byte[,] buffer, int x0, int y0, int x1)
        {
            for (int x = x0; x <= x1; ++x)
                setPixel(buffer, x, y0);
        }
    }
}

这是相关的结果:

00000111111111111111111111111111111111111111110000
00000111111111111111111111111111111111111111110000
00000111111111111111111111111111111111111111110000
00000111111111111111111111111111111111111111110000
00000111111111111111111111111111111111111111110000
00000011111111111111111111111111111111111111100000
00000011111111111111111111111111111111111111100000
00000011111111111111111111111111111111111111100000
00000001111111111111111111111111111111111111000000
00000001111111111111111111111111111111111111000000
00000000111111111111111111111111111111111110000000
00000000111111111111111111111111111111111110000000
00000000011111111111111111111111111111111100000000
00000000001111111111111111111111111111111000000000
00000000000111111111111111111111111111110000000000
00000000000011111111111111111111111111100000000000
00000000000001111111111111111111111111000000000000
00000000000000122222222222222222222210000000000000
00000000000000001222222222222222221000000000000000
00000000000000000012333333333332100000000000000000
00000000000000000000012345432100000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000

底部像素绘制太多次.我在这里错过了什么？

更新#2:此解决方案有效:

static void circle(byte[,] buffer, int cx, int cy, int radius)
{
    int error = -radius;
    int x = radius;
    int y = 0;

    while (x >= y)
    {
        int lastY = y;

        error += y;
        ++y;
        error += y;

        plot4points(buffer, cx, cy, x, lastY);

        if (error >= 0)
        {
            if (x != lastY)
                plot4points(buffer, cx, cy, lastY, x);

            error -= x;
            --x;
            error -= x;
        }
    }
}

static void plot4points(byte[,] buffer, int cx, int cy, int x, int y)
{
    horizontalLine(buffer, cx - x, cy + y, cx + x);
    if (y != 0)
        horizontalLine(buffer, cx - x, cy - y, cx + x);
}    

Answer 1

对另一个问题的答案非常好.然而,由于它造成混乱,我将稍微解释一下.

你在维基百科看到该算法基本上找到x和y的圆的1/8(角度0到pi/4),然后绘制8分其是它的镜像.例如:

    (o-y,o+x) x         x (o+y,o+x)

(o-x,o+y) x                  x (o+x,o+y) <-- compute x,y

                   o

(o-x,o-y) x                  x (o+x,o-y)

    (o-y,o-x) x         x (o+y,o-x)

另外一个解决方案建议,如果你仔细观察这张图片,这是完全合理的,而不是绘制8个点,绘制4条水平线:

    (o-y,o+x) x---------x (o+y,o+x)

(o-x,o+y) x-----------------x (o+x,o+y) <-- compute x,y

                   o

(o-x,o-y) x-----------------x (o+x,o-y)

    (o-y,o-x) x---------x (o+y,o-x)

现在,如果您计算(x,y)角度[0, pi/4]并为每个计算点绘制这4条线,您将绘制许多水平线填充圆形,而没有任何线条与另一条线重叠.

更新

您在圆圈底部获得重叠线条的原因是(x,y)坐标是圆角的,因此在这些位置中水平(x,y) 移动.

如果你看看这个维基百科图片:

您会注意到,在圆的顶部,一些像素是水平对齐的.绘制源自这些点的水平线重叠.

如果您不想这样,解决方案非常简单.您必须保留之前x绘制的(由于顶部和底部是原始镜像(x,y),您应该保留前面的x代表这些线的y),并且只有在该值发生变化时才绘制水平线.如果没有,则表示您在同一条线上.

鉴于您将首先遇到最里面的点,您应该为前一点画线,只有新点有不同x(当然,最后一行总是被绘制).或者,您可以从角度PI/4向下绘制到0而不是0到PI/4,并且您将首先遇到外部点,因此每次看到新的时都会绘制线条x.

Answer 2

我需要这样做，这是我为此想出的代码。这里的视觉图像显示了绘制的像素，其中数字是遍历像素的顺序，绿色数字表示使用对称性的列完成的反射绘制的像素，如代码中所示。

void drawFilledMidpointCircleSinglePixelVisit( int centerX, int centerY, int radius )
{
    int x = radius;
    int y = 0;
    int radiusError = 1 - x;

    while (x >= y)  // iterate to the circle diagonal
    {

        // use symmetry to draw the two horizontal lines at this Y with a special case to draw
        // only one line at the centerY where y == 0
        int startX = -x + centerX;
        int endX = x + centerX;
        drawHorizontalLine( startX, endX, y + centerY );
        if (y != 0)
        {
            drawHorizontalLine( startX, endX, -y + centerY );
        }

        // move Y one line
        y++;

        // calculate or maintain new x
        if (radiusError<0)
        {
            radiusError += 2 * y + 1;
        }
        else 
        {
            // we're about to move x over one, this means we completed a column of X values, use
            // symmetry to draw those complete columns as horizontal lines at the top and bottom of the circle
            // beyond the diagonal of the main loop
            if (x >= y)
            {
                startX = -y + 1 + centerX;
                endX = y - 1 + centerX;
                drawHorizontalLine( startX, endX,  x + centerY );
                drawHorizontalLine( startX, endX, -x + centerY );
            }
            x--;
            radiusError += 2 * (y - x + 1);
        }

    }

}