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:

- Plot initial pts (0,R) ¬ 8 pts
- P1 = 3 - 2r
- if P1 0 then next pt. is (x1 + 1, y1) else next pt. is (x1 + 1, y 1 1)
- if P1 0 p2="P1" + 4x1 + 6 else p2="P1" + 4(x1 y1) + 10
- 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.

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.

Output Primitives menu

HyperGraph
Table of Contents.

HyperGraph Home
page.