Easy ellipse algorithm using Algebra.

[Ex]

So, I'm in my third semester of Algebra, hopefully my last, and we're dealing a lot with circles and ellipses. Every time I'm dealing with these, I always notice how different they look from every circle and ellipse drawing algorithm I've seen. Because of this, I thought I might post here a bit about how to draw an ellipse using algebra. It's pretty simple.

The equation for an ellipse is this:
(x-centerx)^2        (y-centery)^2
  ----------      +     -----------
 (width/2)^2          (height/2)^2

Here's the more boring formal version, ignore the stuff in the image below the top equation:


So, if you loop over an area, this equation will yield different values:
0 = The center of the circle
<1 = inside the circle
1 = The exact edge of the circle
>1 = The outside of the circle

The easy way to draw a circle is to loop in a square from x-(width/2) and y-(height/2) to x+(width/2) and y+(height/2). You can of course loop over more area or less depending on how you set up your if statement. Next, you'll calculate your circle's value for the given x and y, which will be in the range above. Then, you'll use this in an if statement depending on how you want to draw your circle. Here's an example in C using pdcurses:

int i,j;
float width,height,CenterX,CenterY;
float Circle;
width=20;
height=10;
CenterX=40;
CenterY=12;
clear();
  for(i=0;i<80;i++)
     for(j=0;j<25;j++)
     {
        Circle = (((i-CenterX)*(i-CenterX))/((width/2)*(width/2)))+((((j-CenterY)*(j-CenterY))/((height/2)*(height/2))));
        if(Circle>0&&Circle<1.1f)
           mvprintw(j,i,"#");
     };
  refresh();
  getch();

//Easy huh?

[Z]

I thought that's the standard way... what complicated circle and ellipse drawing algorithms do you speak of? Maybe there are better algorithms when you want to create some software for rendering graphics really fast, but I think it is the best one for most uses that happen in roguelikes, and it is simple.

But if you want to draw a circle (only the boundary, without inside), you can also use e.g.
  for(int alpha=0; alpha<200; alpha++) putpixel(100+50*sin(alpha), 100+50*cos(alpha))

That's even shorter. (For ellipses, rescale one coordinate.)

I also like the following algorithm for drawing circles, it is just very cool: here (see point 149)

I also don't know why RL devs seem to think they should use the Bresenham algorithm to draw lines. It is fast, but not the simplest to implement, IMO.

[Fenrir]

I also don't know why RL devs seem to think they should use the Bresenham algorithm to draw lines. It is fast, but not the simplest to implement, IMO.

There are simpler algorithms? What are they?

[Ex]

I thought that's the standard way... what complicated circle and ellipse drawing algorithms do you speak of? Maybe there are better algorithms when you want to create some software for rendering graphics really fast, but I think it is the best one for most uses that happen in roguelikes, and it is simple.

But if you want to draw a circle (only the boundary, without inside), you can also use e.g.
  for(int alpha=0; alpha<200; alpha++) putpixel(100+50*sin(alpha), 100+50*cos(alpha))

That's even shorter. (For ellipses, rescale one coordinate.)

I also like the following algorithm for drawing circles, it is just very cool: here (see point 149)

I also don't know why RL devs seem to think they should use the Bresenham algorithm to draw lines. It is fast, but not the simplest to implement, IMO.

Because a long, long time ago floating point math was more expensive than integer math, and thusly bresenham wrote a line algorithm using only integers and we've been using it ever since? But really, I don't know why people don't use simpler algorithms these days anyway. Floating point math is practically cheaper than integer math these days...

[Z]

There are simpler algorithms? What are they?

I think this one is the simplest:

Code: [Select]

int d = max(abs(x1-x2), abs(y1-y2));

for(int i=0; i<=d; i++)
  putpixel(x1 + (x2-x1) * i/d, y1 + (y2-y1) * i/d);

(And it also does not use floats. The point of Bresenham is that it does not even use multiplication, IIRC)

[Etinarg]

Floating point math is practically cheaper than integer math these days...

Are you sure about that? I have the "floating point math is evily slow, use integers wherever possible" very much internalized, still. But maybe time really has surpassed those days.

And yes, Bresenham was particularly cool at times when machines only had 'fast' add operations, and multiply was done by a lot of shifts and adding.

The above sketched "simple line" algorithm uses divides, which were painfully slow even of good processors, not too long ago (e.g. pre-pentium era).

Edit: I guess my choice to use Java nowadays already invalidated all the talk above