简单的算法画椭圆填充在C / C ++ [英] Simple algorithm for drawing filled ellipse in C/C++

问题描述

在SO，发现下面这个简单的算法画实心圆：

On SO, found the following simple algorithm for drawing filled circles:

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);

有一个同样简单的算法，绘制填补椭圆？

Is there an equally simple algorithm for drawing filled ellipses?

推荐答案

更​​简单，没有双无师（不过要小心整数溢出）：

Simpler, with no double and no division (but be careful of integer overflow):

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);
    }
}

我们可以利用两个事实优势，显著优化这样的：

We can take advantage of two facts to optimize this significantly:

• 在椭圆具有纵向和横向的对称性;
• 当你从一个轴前进的路程，椭圆的轮廓斜坡也越来越多。

第一个事实节省了四分之三的工作（几乎）;第二个事实大大减少了试验的次数（我们测试仅沿椭圆的边缘，甚至有我们没有测试每个点）。

The first fact saves three-quarters of the work (almost); the second fact tremendously reduces the number of tests (we test only along the edge of the ellipse, and even there we don't have to test every point).

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);
    }
}

这工作，因为每条扫描线比previous要短，至少有尽可能多 作为一个比前一个短。由于四舍五入到整数像素坐标，这是不完全准确 - 该线可通过一个像素较短小于该

This works because each scan line is shorter than the previous one, by at least as much as that one was shorter than the one before it. Because of rounding to integer pixel coordinates, that's not perfectly accurate -- the line can be shorter by one pixel less that that.

在换句话说，从最长的扫描线（水平直径），该量由每行大于previous 1，表示为短起始 DX 在code，降低由至多一个，保持不变，或增加。第一内为查找在 DX，它与当前扫描线比previous要短，在开始的确切数额 - 1 和上，直到我们的土地就在椭圆内。

In other words, starting from the longest scan line (the horizontal diameter), the amount by which each line is shorter than the previous one, denoted dx in the code, decreases by at most one, stays the same, or increases. The first inner for finds the exact amount by which the current scan line is shorter than the previous one, starting at dx - 1 and up, until we land just inside the ellipse.

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

要比较内部的椭圆测试次数，每个星号是一对在天真的版本测试的坐标：

To compare the number of inside-ellipse tests, each asterisk is one pair of coordinates tested in the naive version:

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

...而在改进的版本：

... and in the improved version:

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

这篇关于简单的算法画椭圆填充在C / C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！