15

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

是否有同样简单的算法来绘制填充椭圆？

4

4 回答 4

20

更简单，没有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在代码中表示，最多减少一个，保持不变，或者增加。第一个内部for查找当前扫描线比前一个扫描线短的确切数量，从上dx - 1到上，直到我们恰好落在椭圆内。

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

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

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

...在改进的版本中：

                        *
                             **
                                  ****
                                       ***
                                          ***
                                            ***
                                             **
                                             **
于 2012-04-25T19:41:04.777 回答
8

椭圆（关于原点）是沿x或y轴线性拉伸的圆。所以你可以像这样修改你的循环：

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

您可以看到，如果width == height == radius，那么这相当于您绘制圆的代码。

于 2012-04-25T19:30:33.927 回答
8

代替

x*x+y*y <= radius*radius

和

Axx*x*x + 2*Axy*x*y + Ayy*y*y < radius*radius

你有三个常数，Axx，Axy，Ayy。当 Axy=0 时，椭圆的轴线水平和垂直。Axx=Ayy=1 做一个圆圈。Axx 越大，宽度越小。Ayy 和身高类似。对于以任何给定角度倾斜的任意椭圆，需要一些代数来计算常数。

从数学上讲，Axx、Axy、Ayy 是一个“张量”，但也许你不想涉足那些东西。

更新 - 详细的数学。我不认为 SO 可以像 Math SE 那样做出很好的数学运算，所以这看起来很粗糙。 倾斜的椭圆，x'，y' 坐标与椭圆对齐，x，y 直线水平，垂直 您想用 x,y 坐标中的椭圆绘制（或做任何事情）。椭圆是倾斜的。我们创建一个与椭圆对齐的替代坐标系 x',y'。显然，椭圆上的点满足

(x'/a)^2 + (y'/b)^2 = 1

通过考虑一些精心挑选的随机点，我们看到

x' =  C*x + S*y
y' = -S*x + C*y

其中 S、C 是 sin(θ) 和 cos(θ)，θ 是 x' 轴相对于 x 轴的角度。我们可以用符号 x = (x,y) 和类似的符号来缩短它，R 是一个涉及 C 和 S 的 2x2 矩阵：

x' = R x

椭圆方程可以写成

T( x' ) A'' x' = 1

其中'T'表示转置，去掉'^'以避免戳到每个人的眼睛，所以“a2”真正意味着a^2，

一个'' =

1/a2     0  
 0     1/b2

使用x' = R x 我们发现

T(R x ) A'' R x = 1

T( x ) T(R) A'' R x =1

T( x ) A x = 1

其中 A，使倾斜绘图扫描线算法起作用需要知道的事情，是

A = T(R) A'' R =

C2/a2+S2/b2     SC(1/a2-1/b2)
SC/(1/a2-1/b2)  S2/a2 + C2/b2

根据 T( x )A x将这些乘以 x 和 y ，你就得到了。

于 2012-04-26T16:18:50.827 回答
5

本文提出的快速 Bresenham 类型算法运行良好。这是我为它编写的一个OpenGL 实现。

基本前提是您在一个象限上绘制曲线，我们可以将其镜像到其他三个象限。这些顶点是使用误差函数计算的，类似于您在圆的中点圆算法中使用的。我在上面链接的论文为该方程提供了一个非常漂亮的证明，并且该算法简化为仅检查给定顶点是否在椭圆内，只需将其值替换为误差函数即可。该算法还跟踪我们在第一象限中绘制的曲线的切线斜率，并根据斜率值增加 x 或 y - 这进一步有助于算法的性能。这是一张显示正在发生的事情的图像：

在此处输入图像描述

至于填充椭圆，一旦我们知道每个象限中的顶点（本质上是跨 x 和 y 轴的镜像反射），我们计算的每个顶点都会得到 4 个顶点 - 这足以绘制一个四边形（无论如何在 OpenGL 中） . 一旦我们为所有这些顶点绘制四边形，我们就会得到一个实心椭圆。出于性能原因，我给出的实现使用了 VBO，但您并不严格需要它。

该实现还向您展示了如何使用三角形和线而不是绘制四边形来实现填充椭圆 - 虽然四边形显然更好，因为它是一个原始的并且我们只为 4 个顶点绘制一个四边形，而不是每个顶点一个三角形三角形的实现。

于 2015-01-06T20:25:19.013 回答