Simple algorithm for drawing filled ellipse in C/C++

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:

• 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 diameterfor (int x = -width; x <= width; x++)    setpixel(origin.x + x, origin.y);// now do both halves at the same time, away from the diameterfor (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 muchas 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 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 dxprevious 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:

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

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.

Mathematically Axx, Axy, Ayy are a "tensor" but perhaps you don't want to get into that stuff.

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

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

By contemplating some well-chosen random points we see that

x' =  C*x + S*yy' = -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:

x' = R x

The ellipse equation can be written

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,

A'' =

1/a2     0   0     1/b2

Using x' = Rx we find

T(Rx) A'' Rx = 1

T(x) T(R) A'' R 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 = 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)Ax and you've got it.

An ellipse (about the origin) is a circle that has been linearly stretched along the x or y axes. So you can modify your loop like this:

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.