C/C++中绘制填充椭圆的简单算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/10322341/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Simple algorithm for drawing filled ellipse in C/C++
提问by Roger Dahl
On SO, found the following simple algorithm for drawing filled circles:
在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);
Is there an equally simple algorithm for drawing filled ellipses?
是否有同样简单的算法来绘制填充椭圆？
回答by cvoinescu
Simpler, with no doubleand no division (but be careful of integer overflow):
更简单，没有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);
}
}
We can take advantage of two facts to optimize this significantly:
我们可以利用两个事实来显着优化这一点：
- Ellipses have vertical and horizontal symmetry;
- As you progress away from an axis, the contour of the ellipse slopes more and more.
- 椭圆具有垂直和水平对称；
- 随着您远离轴，椭圆的轮廓越来越倾斜。
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);
}
}
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.
这是有效的，因为每条扫描线都比前一条短，至少与前一条相比短。由于四舍五入到整数像素坐标，这并不完全准确——线可以短一个像素。
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 dxin the code, decreases by at most one, stays the same, or increases. The first inner forfinds the exact amount by which the current scan line is shorter than the previous one, starting at dx - 1and up, until we land just inside the ellipse.
换句话说，从最长的扫描线（水平直径）开始，每条线比前一条线短的量，dx在代码中表示，最多减少一，保持不变，或增加。第一个内部for查找当前扫描线比前一个扫描线短的确切数量，从 开始dx - 1并向上，直到我们刚好落在椭圆内。
| 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:
为了比较内部椭圆测试的数量，每个星号都是在 naive 版本中测试的一对坐标：
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
*********************************************
... and in the improved version:
...并在改进版本中：
*
**
****
***
***
***
**
**
回答by DarenW
Replace
代替
x*x+y*y <= radius*radius
with
和
Axx*x*x + 2*Axy*x*y + Ayy*y*y < radius*radius
where you have three constants, Axx, Axy, Ayy. When Axy=0, the ellipse will have its axes straight horizontal and vertical. Axx=Ayy=1 makes a circle. The bigger Axx, the smaller the width. Similar for Ayy and height. For an arbitrary ellipse tilted at any given angle, it takes a bit of algebra to figure out the constants.
你有三个常数，Axx，Axy，Ayy。当 Axy=0 时，椭圆的轴将是水平和垂直的直线。Axx=Ayy=1 构成一个圆。Axx 越大，宽度越小。AYY 和高度类似。对于以任何给定角度倾斜的任意椭圆，需要一些代数来计算常数。
Mathematically Axx, Axy, Ayy are a "tensor" but perhaps you don't want to get into that stuff.
从数学上讲，Axx、Axy、Ayy 是一个“张量”，但也许您不想深入研究这些东西。
UPDATE - detailed math. I don't think S.O. can make nice math like Math S.E. so this will look crude.
You want to draw (or do whatever) with an ellipse in x,y coordinates. The ellipse is tilted. We create an alternative coordinate system x',y' aligned with the ellipse. Clearly, points on the ellipse satisfy
更新 - 详细的数学。我不认为 SO 可以像 Math SE 那样做出漂亮的数学，所以这看起来很粗糙。
你想用 x,y 坐标中的椭圆绘制（或做任何事情）。椭圆是倾斜的。我们创建了一个与椭圆对齐的替代坐标系 x',y'。显然，椭圆上的点满足
(x'/a)^2 + (y'/b)^2 = 1
By contemplating some well-chosen random points we see that
通过考虑一些精心挑选的随机点，我们看到
x' = C*x + S*y
y' = -S*x + C*y
where S, C are sin(θ) and cos(θ), θ being the angle of the x' axis w.r.t. the x axis. We can shorten this with notation x= (x,y) and similar for primed, and R a 2x2 matrix involving C and S:
其中 S、C 是 sin(θ) 和 cos(θ)，θ 是 x' 轴与 x 轴的夹角。我们可以用符号x= (x,y) 和类似的符号来缩短它 ，而 R 是一个包含 C 和 S 的 2x2 矩阵：
x'= R x
x'= R x
The ellipse equation can be written
椭圆方程可以写成
T(x') A'' x'= 1
T( x') A'' x'= 1
where 'T' to indicates transpose and, dropping '^' to avoid poking everyone in the eyes, so that "a2" really means a^2,
其中“T”表示转置，并去掉“^”以避免戳到每个人的眼睛，因此“a2”实际上表示a^2，
A'' =
A'' =
1/a2 0
0 1/b2
Using x'= Rxwe find
使用x'= R x我们发现
T(Rx) A'' Rx= 1
T(R x) A'' R x= 1
T(x) T(R) A'' R x=1
T( x) T(R) A'' R x=1
T(x) A x= 1
T( x) A x= 1
where A, the thing you need to know to make your tilted drawing scan line algorithm work, is
其中 A 是使倾斜绘图扫描线算法工作所需的知识，是
A = T(R) A'' R =
A = T(R) A'' R =
C2/a2+S2/b2 SC(1/a2-1/b2)
SC/(1/a2-1/b2) S2/a2 + C2/b2
Multiply these by x and y according to T(x)Axand you've got it.
根据 T( x)A x将这些乘以 x 和 y就可以了。
回答by Greg Hewgill
An ellipse (about the origin) is a circle that has been linearly stretched along the xor yaxes. So you can modify your loop like this:
椭圆（关于原点）是一个沿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);
}
}
You can see that if width == height == radius, then this is equivalent to your code for drawing a circle.
您可以看到，如果width == height == radius，则这相当于您绘制圆的代码。
回答by Prathap
A fast Bresenham type algorithm, as proposed by this paper, works really well. Here's an OpenGL implementationthat I wrote for the same.
本文提出的快速 Bresenham 类型算法效果非常好。这是我为此编写的OpenGL 实现。
The basic premise is that you plot the curve on one quadrant, which we can mirror on to the other three quadrants. These vertices are computed using an error function, similar to what you use in the midpoint circle algorithm for circles. The paper I have linked above has a pretty nifty proof for the equation, and the algorithm distills down to just checking if a given vertex is within an ellipse or not, just by substituting its values in the error function. The algorithm also tracks the tangent line slope of the curve we are drawing in the first quadrant, and increments x or y depending on the slope value - which contributes further to the performance of the algorithm. Here's an image that shows what's going on:
基本前提是您在一个象限上绘制曲线，我们可以将其映射到其他三个象限。这些顶点是使用误差函数计算的，类似于您在圆的中点圆算法中使用的函数。我在上面链接的论文对方程有一个非常漂亮的证明，该算法简化为仅检查给定的顶点是否在椭圆内，只需将其值代入误差函数即可。该算法还跟踪我们在第一象限中绘制的曲线的切线斜率，并根据斜率值递增 x 或 y - 这进一步有助于算法的性能。这是一张显示正在发生的事情的图像：
As for filling the ellipse, once we know the vertices in each quadrant (which is essentially mirror reflections across x and y axes), we get 4 vertices for every vertex that we compute - which is sufficient to draw a quad (in OpenGL anyway). Once we draw quads for all such vertices, we get a filled ellipse. The implementation I have given employs VBO for performance reasons, but you don't strictly need it.
至于填充椭圆，一旦我们知道每个象限中的顶点（本质上是跨 x 和 y 轴的镜像反射），我们计算的每个顶点都有 4 个顶点 - 这足以绘制四边形（无论如何在 OpenGL 中） . 一旦我们为所有这些顶点绘制四边形，我们就会得到一个填充的椭圆。出于性能原因，我给出的实现使用 VBO，但您并不严格需要它。
The implementation also shows you how to achieve a filled ellipse using triangles and lines instead of drawing quads - the quads are clearly better though, as it is a primitive and we only draw one quad for 4 vertices, as opposed to one triangle per vertex in the triangle implementation.
该实现还向您展示了如何使用三角形和直线而不是绘制四边形来实现填充的椭圆——四边形显然更好，因为它是一个基元，我们只为 4 个顶点绘制一个四边形，而不是每个顶点绘制一个三角形三角执行。
