Circles

But this is very expensive and gives nonuniform pixel spacing.
Second try: use Polar Coordinates:

x = xc + r cos q    step q
y = yc + r sin q

Could set step size yr and get uniform density about 1 pixel apart. But this is still computationally expensive ( computing sin, cos ). Use the Decision Variable Method (Bresenham). We can compute in one octant then use symmetry. So can compute 1 point then plot 8 points as below:

Assume xc = yc = 0 (simple offset) so x2 + y2 = R2
use the 2nd octant and go from x = 0 to x = y = (R / 2)1/2.
so will step x by 1 and choose y. In general have

Can discard points 1, 4, 6 since x increases. Also, discard 1, 2, 3 since y decreases, so we need to choose between 5, 7, 8. The slope of the circle must lie between the slope of the lines defined as pi -> x with x = 5, 7, 8. The slope of pi -> 5 = 0, pi -> 8 = -1, pi -> 7 = undefined. The slope of a circle in the second octant: dy / dx = -x / y so at x = 0, slope = 0 and at x = y, slope = -1. Hence use points. 5, 8 and reject 7.

so have

y2 = r2 - (xi + 1)2
d1 = y i2 - y2 = yi2 - r2 + (xi + 1)2 
d2 = y2 - (y i - 1)2 = r2 - (xi + 1)2 - (yi - 1)2

(1) pi = d1 - d2   = 2(xi + 1) 2 + yi2 + (yi - 1)2 - 2r2
if pi < 0 choose yi  {d2 > d1}
else choose yi - 1  {d2 < d1, pi > 0}

Now, as before (with the line equation), we can derive

Pi+1 = Pi  + 4x i + 6 + 2(yi+12 - yi2) - 2(yi+1 - yi)

so if Pi < 0, {choose yi}    {yi+1 = yi}  
Pi+1 = Pi + 4xi + 6

else  {Pi ³ 0, choose yi-1}   {yi+1 = yi-1} 
Pi+1 = P i + 4(xi - yi) + 10

Now  compute  P1 from (1): 
At  x1, y1	x1 = 0, y1 = r    so P 1 = 3 - 2r 

Circle Algorithm:

1. Plot initial pts (0,R) ¬ 8 pts
2. .P1 = 3 - 2r
3. if P1 < 0 then next pt. is (x1 + 1, y1) else next pt. is (x1 + 1, y 1 - 1)
4. if P1 < 0 P2 = P1 + 4x1 + 6 else P2 = P1 + 4(x1 - y1) + 10
5. .Repeat 3,4 until x = y

Ellipses

So initially choice is between 5 & 8 and then between 7 & 8.

Find change over point.
Slope = dy / dx = -bx/ay (x, y both positive in 1st quadrant)
so when ay < bx then slope < -1 and choose between 7, 8
{Note: complete derivation for ellipse in Dr. Dobb's Journal, May 1985 p.40-48}
We can use the Decision variable method to display any function of form y = f(x). (Remember: changes in slope) Generally easier to use Line segments but not as pretty or fast.

May want to plot ARCS or part of curve. Can do as above just compute initial, final pts. Example: Start at x1 and only use 1st and 2nd octant symmetry.