How to make a 2D array resembling an ellipse

Question

I need a function that creates a 2D array resembling an ellipse where each cell is a pixel that can either be on (1) or off (0). For example, if you ran circlearray(5,8), it would return something like:

[[0, 1, 1, 1, 0],
 [0, 1, 1, 1, 0],
 [1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1],
 [0, 1, 1, 1, 0],
 [0, 1, 1, 1, 0]];

I have tried this before, but can't seem to get the rounding (decimal to integer, not making it elliptical) right. The formula that I'm using is: f(x) = h/w * sqrt(w^2 - x^2), where h is the length of the radius at the top of the ellipse and w is the length of the radius at the side of the ellipse. It gives you how many columns you should have for the circle given row, but with circles, I notice that it is different turned on its side that upright, which I know shouldn't be. I can't seem to get the circle right with Math.round(f(x)), Math.floor(f(x)), nor Math.ceil(f(x)). I also don't want to use jQuery.

Here is a the jsFiddle shows my findings: http://jsfiddle.net/r7cH5/

And here is an example of how to use the formula: http://www.desmos.com/calculator/v5qbcd1jkm

Answer 1

I assume you mean an ellipse with major and minor axes aligned horizontally and vertically. (Plotting an ellipse in general orientation is a much more difficult problem.)

You want a generalization of the Bresenham circle algorithm for ellipses. A nice description of the theory and an implementation is described in this paper. Simple code can be found here for using Bresenham's algorithm for lines, circles, ellipses and Bézier curves. From the latter site, here's the code for plotting an ellipse inside a specified rectangle:

void plotEllipseRect(int x0, int y0, int x1, int y1)
{
   int a = abs(x1-x0), b = abs(y1-y0), b1 = b&1; /* values of diameter */
   long dx = 4*(1-a)*b*b, dy = 4*(b1+1)*a*a; /* error increment */
   long err = dx+dy+b1*a*a, e2; /* error of 1.step */

   if (x0 > x1) { x0 = x1; x1 += a; } /* if called with swapped points */
   if (y0 > y1) y0 = y1; /* .. exchange them */
   y0 += (b+1)/2; y1 = y0-b1;   /* starting pixel */
   a *= 8*a; b1 = 8*b*b;

   do {
       setPixel(x1, y0); /*   I. Quadrant */
       setPixel(x0, y0); /*  II. Quadrant */
       setPixel(x0, y1); /* III. Quadrant */
       setPixel(x1, y1); /*  IV. Quadrant */
       e2 = 2*err;
       if (e2 <= dy) { y0++; y1--; err += dy += a; }  /* y step */ 
       if (e2 >= dx || 2*err > dy) { x0++; x1--; err += dx += b1; } /* x step */
   } while (x0 <= x1);

   while (y0-y1 < b) {  /* too early stop of flat ellipses a=1 */
       setPixel(x0-1, y0); /* -> finish tip of ellipse */
       setPixel(x1+1, y0++); 
       setPixel(x0-1, y1);
       setPixel(x1+1, y1--); 
   }
}

This isn't JavaScript, of course, but it should be straightforward to convert. (Since no integer division is involved, you don't need to worry about the fact that JavaScript doesn't have integer division.) Instead of setPixel, of course, you would simply set the array element to 1.

Note that this plots a one-pixel thick ellipse boundary. If you want a filled ellipse, just apply a scan line fill: iterate row by row and fill between the two columns that are set to 1 by the above (or leave the row alone if you don't find two distinct columns set). Alternatively, you could follow up the above with a flood fill algorithm starting at the center of the rectangle.

Answer 2

var width = 100,
    height = 160,
    span = document.createElement('span'),
    output = document.getElementById("output");

function ellipse(x) {
    return Math.floor((height / width) * Math.sqrt((width * width) - (x * x))); // Times itself doesn't give NaN as often as squared.
}

for (var i = -1 * width; i <= width; i++) {
    var s = span.cloneNode(false);
    s.style.height = ellipse(i) + 'px';
    output.appendChild(s)
}

Demo