# Circles, Ellipses, and General Implicit Functions

### Circles

A brute force algorithm would be to use the circle equation:
r2 = (x - xc)2 + (y - yc)2 or y = yc ± (r2 - (x - xc)2)1/2

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

Note integer Addition/Subtraction, multiplication by power of 2. The aspect ratio for monitors is usually 4/3 = 1.33. If the pixels are not "square" then a correction must be made, else the circle will look like an ellipse. For example, in the CGA Mode 6, the pixel resolution is 640/200 = 3.2, so the correction = 3.2/1.33= 2.40.

### Ellipses

Look at ellipse - use same method but equation is ay^2 + bx^2 - ab = 0. Ellipse has 4 fold symmetry so use 1st quadrant so x1 = 0 , xf = a½

>Must determine pixel choices from slope:

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.

Last changed May 13, 1998, G. Scott Owen, owen@siggraph.org