algorithm - How do I draw an ellipse with arbitrary orientation pixel by pixel?


Keywords:algorithm 


Question: 

I have to draw an ellipse of arbitrary size and orientation pixel by pixel. It seems pretty easy to draw an ellipse whose major and minor axes align with the x and y axes, but rotating the ellipse by an arbitrary angle seems trickier. Initially I though it might work to draw the unrotated ellipse and apply a rotation matrix to each point, but it seems as though that could cause errors do to rounding, and I need rather high precision.

Is my suspicion about this method correct? How could I accomplish this task more precisely?

I'm programming in C++ (although that shouldn't really matter since this is a more algorithm-oriented question).

Edit: as David pointed out, I guess I may really be wondering how to do pixel interpolation.


3 Answers: 

Use:

x = X cos(a) - Y sin(a)
y = Y cos(a) + X sin(a)

Where a is the angle of anticlockwise rotation, (x, y) are the new coordinates, and (X, Y) are the old.

You should use floats to preserve precision. Just go through every point, apply the transformation, and voilà.

Edit: after some searching, here's some code from Microsoft: that draws rastered conic sections.

 

Bresenham (famous for his line drawing algorithm) also has an algorithm for drawing an ellipse. You can try to google bresenham ellipse.

 

Use the Bresenham method of drawing axis-aligned ellipses, but apply a shear to the drawn ellipse. You will also need to modify the lengths of the axes. A sheared ellipse is also an ellipse. This method preserves the Bresenham advantage of drawing filled ellipses using horizontal line segments. What you need in order to do this is the function which maps a specification of an ellipse in terms of axes and rotation into a different set of axes and a shear. A solution is available online at with a discussion about the method and a description of the math involved at

The mapping was discovered by Nathan Dinsmore (user nXIII at the MIT Scratch site)