c++ - 在 C/C++ 中绘制填充椭圆的简单算法

Question

在SO上，发现了以下绘制实心圆的简单算法:

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 1

更简单，没有 double 也没有除法(但要小心整数溢出):

for(int y=-height; y<=height; y++) {
    for(int x=-width; x<=width; x++) {
        if(x*x*height*height+y*y*width*width <= height*height*width*width)
            setpixel(origin.x+x, origin.y+y);
    }
}

我们可以利用两个事实来显着优化这一点:

• 椭圆具有垂直和水平对称性；
• 随着您远离某个轴，椭圆的轮廓会越来越倾斜。

第一个事实节省了四分之三的工作(几乎)；第二个事实极大地减少了测试的数量(我们只在椭圆的边缘进行测试，即使在那里我们也不必测试每个点)。

int hh = height * height;
int ww = width * width;
int hhww = hh * ww;
int x0 = width;
int dx = 0;

// do the horizontal diameter
for (int x = -width; x <= width; x++)
    setpixel(origin.x + x, origin.y);

// now do both halves at the same time, away from the diameter
for (int y = 1; y <= height; y++)
{
    int x1 = x0 - (dx - 1);  // try slopes of dx - 1 or more
    for ( ; x1 > 0; x1--)
        if (x1*x1*hh + y*y*ww <= hhww)
            break;
    dx = x0 - x1;  // current approximation of the slope
    x0 = x1;

    for (int x = -x0; x <= x0; x++)
    {
        setpixel(origin.x + x, origin.y - y);
        setpixel(origin.x + x, origin.y + y);
    }
}

这是有效的，因为每条扫描线都比前一条短，至少一样多因为那个比前面那个短。由于四舍五入到整数像素坐标，这并不完全准确 - 线条可能会短一个像素。

也就是说，从最长的扫描线(水平直径)开始，每行比上一行短的量，代码中表示为dx，最多减少1 ，保持不变，或增加。第一个内部 for 找到当前扫描线比前一个扫描线短的确切数量，从 dx - 1 开始，直到我们正好落在椭圆内.

                       |         x1 dx x0
                       |######    |<-->|
 current scan line --> |###########    |<>|previous dx
previous scan line --> |################  |
two scan lines ago --> |###################
                       |##################### 
                       |###################### 
                       |######################
                       +------------------------

为了比较椭圆内测试的数量，每个星号是在朴素版本中测试的一对坐标:

 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************

...在改进的版本中:

                        *
                             **
                                  ****
                                       ***
                                          ***
                                            ***
                                             **
                                             **